```On 13 Jul 2008, at 16:35, James Gray wrote:
>
> Mine was similar to this:
>
>  def symbolify(n)
>    "??-??" + "--(?)-?()" * n
>  end

I came up with something along those lines.
The version that produces shorter output worked along these lines:

1. Express the number as a sum of powers of 63 (eg 250174 = 63^3 +
2*63 +1)
2. Rewrite that polynomial to reduce the number of operations required
(ie 3x^4+2x^2+x is written as x(x(3x^2+2)+1)
3. write that out. the exponents are dealt with by calling itself.
Coefficients (which by definition are < 63) are dealt with by a
function that deals with that.
Initially I just hardcoded numbers 1 to 5 (?( - ?) etc...) and dealt
with others by dividing out by 5 and calling itself recursively. Later
on I added special cases for most of the numbers to produce shorter
output. Some other parts of the program can be simplified/eliminated
as all they do is produce slightly more compact output. This forms the
bulk of the program. Off the top of my head I'd assume that the
approach taken results in O(ln n) complexity.

Fred

def strip_parens x
x.gsub(/^\(/,'').gsub(/\)\$/,'')
end

INVERTIBLE = [1,2,3,4,5,18,21,22,23,46,47,48,49,50]
def small_symbolify x
case x
when 0: return '(?*-?*)'
when 1: return '(?)-?()'
when -1: return '(?(-?))'
when 2: return '(?*-?()'
when -2: return '(?(-?*)'
when 3: return '(?--?*)'
when -3: return '(?*-?-)'
when 4: return '(?--?))'
when -4: return '(?)-?-)'
when 5: return '(?--?()'
when -5: return '(?(-?-)'
when 6: return '('+small_symbolify(3)+'*'+small_symbolify(2)+')'
when 8: return '('+small_symbolify(2)+'*'+small_symbolify(4)+')'
when 9: return '('+small_symbolify(3)+'*'+small_symbolify(3)+')'
when 10: return '(?--?(-(?(-?-))'
when 12: return '('+small_symbolify(3)+'*'+small_symbolify(4)+')'
when 13: return '(??-?--(?--?())'
when 14: return '('+strip_parens(small_symbolify(18))
+'-'+small_symbolify(4)+')'
when 16: return small_symbolify(2)+'**'+small_symbolify(4)
when 17: return '('+strip_parens(small_symbolify(18))
+'-'+small_symbolify(1)+')'
when 18: return '(??-?-)'
when -18: return '(?--??)'
when 19: return '('+strip_parens(small_symbolify(21))
+'-'+small_symbolify(2)+')'
when 21: return '(??-?*)'
when -21: return '(?*-??)'
when 22: return '(??-?))'
when -22: return '(?)-??)'
when 23: return '(??-?()'
when -23: return '(?(-??)'
when 24: return '('+strip_parens(small_symbolify(23))
+'-'+small_symbolify(-1)+')'
when 25: return small_symbolify(5)+'**'+small_symbolify(2)
when 26: return '('+strip_parens(small_symbolify(23))
+'-'+small_symbolify(-3)+')'
when 27: return small_symbolify(3)+'**'+small_symbolify(3)
when 28: return '('+strip_parens(small_symbolify(23))
+'-'+small_symbolify(-5)+')'
when 32: return small_symbolify(2)+'**'+small_symbolify(5)
when 36: return '('+small_symbolify(18)+'*'+small_symbolify(2)+')'
when 38: return '('+strip_parens(small_symbolify(40))
+'-'+small_symbolify(2)+')'
when 39: return '('+small_symbolify(3)+'*'+small_symbolify(13)+')'
when 40: return '?('
when 41: return '?)'
when 42: return '?*'
when 45: return '?-'
when 46: return '('+small_symbolify(45)+'-'+small_symbolify(-1)+')'
when -46: return '('+strip_parens(small_symbolify(-1))
+'-'+small_symbolify(45)+')'
when 47: return '('+small_symbolify(45)+'-'+small_symbolify(-2)+')'
when -47: return '('+strip_parens(small_symbolify(-2))
+'-'+small_symbolify(45)+')'
when 48: return '('+small_symbolify(45)+'-'+small_symbolify(-3)+')'
when -48: return '('+strip_parens(small_symbolify(-3))
+'-'+small_symbolify(45)+')'
when 49: return '('+small_symbolify(45)+'-'+small_symbolify(-4)+')'
when -49: return '('+strip_parens(small_symbolify(-4))
+'-'+small_symbolify(45)+')'
when 50: return '('+small_symbolify(45)+'-'+small_symbolify(-5)+')'
when -50: return '('+strip_parens(small_symbolify(-5))
+'-'+small_symbolify(45)+')'
when 52: return '('+small_symbolify(4)+'*'+small_symbolify(13)+')'
when 54: return '('+small_symbolify(3)+'*'+small_symbolify(18)+')'
end
if x > 31
return '(??-'+small_symbolify(63-x)+')'
end
quotient = x/5
rem = x - quotient * 5
if quotient==0
small_symbolify rem
else
if quotient == 1
quotient_string = ''
else
quotient_string = small_symbolify(quotient)+'*'
end
'('+quotient_string+small_symbolify(5)+(rem > 0 ? '-' +
small_symbolify(-rem) : '') + ')'
end
end

def log63(x)
power=0
value=1
x=-x if x < 0
while value <= x
value*=63
power+=1
end
power-1
end

def convert_to_base_63 x
return [] if x == 0
[[x,0]]
else

quotient = x/v
remainder = x - quotient*v
end
end

def symbolify x
return '(?*-?*)' if x == 0
transform_polynomial(convert_to_base_63(x))
end

def transform_polynomial p
return '' if p.empty?
last = p.pop

m_power_term = (['??']*last[1]).join('*')
p_power_term = "??**#{symbolify last[1]}"

power_term = m_power_term.length > p_power_term.length ?
p_power_term : m_power_term
if p.empty?
if last[1]==0
result = small_symbolify(last[0])
elsif last[0] == 1
result = power_term
else
result = small_symbolify(last[0]) + '*'+power_term
end
else
remainder = transform_polynomial(p.collect {|t| [t[0], t[1] -
last[1]]})
if INVERTIBLE.include?(last[0])
remainder += '-'
remainder +=small_symbolify -last[0]
else
remainder += '--'
remainder +=small_symbolify last[0]
end
if last[1]==0
result = remainder
else
result = power_term + "*(#{remainder})"
end
end
result
end

```