Count up with Zeckendorf's theorem!

[Sean Quixote]

204 = 10100001000

[Anonymously Famous]

205 = 10100001001

[Sean Quixote]

206 = 10100001010

[Anonymously Famous]

207 = 10100010000

[Sean Quixote]

208 = 10100010001

[Anonymously Famous]

209 = 10100010010

[Sean Quixote]

210 = 10100010100

[Anonymously Famous]

211 = 10100010101

[Sean Quixote]

212 = 10100100000

[cemper93]

213 : 10100100001

BTW:

Code: Select all

f,m,a,g,h=lambda n:int(n<2)or m.get(n)or m.update({n:f(n-1)+f(n-2)})or m.get(n),{},input(),lambda a,l:filter(lambda i:h(a,i,l),l),lambda a,i,l:a==f(i)and i or g(a-f(i),l-set([i,i-1,i+1]))
print g(a,set(filter(lambda x:f(x)<=a,range(1,a))))

EDIT: Maybe I should add that this is Python. It may not be evident.

[Sean Quixote]

214 : 10100100010

[Anonymously Famous]

215 : 10100100100

Code: Select all

Traceback (most recent call last):
  File "<pyshell#37>", line 1, in <module>
    f,m,a,g,h=lambda n:int(n<2)or m.get(n)or m.update({n:f(n-1)+f(n-2)})or m.get(n),{},input(),lambda a,l:filter(lambda i:h(a,i,l),l),lambda a,i,l:a==f(i)and i or g(a-f(i),l-set([i,i-1,i+1]))
  File "<string>", line 0
   
   ^
SyntaxError: unexpected EOF while parsing

What version of Python?

Edit:

Code: Select all

def zeck(n):
   n=int(n)
   #Create reverse Fibonacci sequence of more than what we need...
   a=range(2*len(bin(n)),0,-1)
   for i in range(len(a)-3,-1,-1):
      a[i]=a[i+1]+a[i+2]
   #Find the starting point
   for i in range(len(a)):
      if a[i]<=n:
         break
   #Initiate total as a "counter" of sorts and retval as a return string
   total = 0
   retval = ''
   while i < len(a):
      if(total+a[i]<=n):
         total += a[i]
         if(i == len(a)-1):
            retval += '1'
         else:
            retval += '10'
         #add one to skip the next number in the sequence
         i+=1
      else:
         retval+='0'
      i+=1
   return retval

It's not as elegant as yours, but it does the job.

Also:

Code: Select all

def reverse_zeck(n):
   n=str(n)
   a=range(len(n),0,-1)
   for i in range(len(a)-3,-1,-1):
      a[i]=a[i+1]+a[i+2]
   total=0
   for i in range(len(n)):
      if(n[i]=='1'):
         total += a[i]
      elif(n[i] != '0'):
         raise Exception("Invalid String")
   return total

[cemper93]

216: 10100100101

This should work in any Python >=2.2 or so and <3.0. I think you get the error because the forum software messed with my code - what appears as two lines here actually has to be a single line, like so:
http://pastebin.com/1Vh10spM

[Anonymously Famous]

217: 10100101000

Oh, I got it as one line. I tried copying from the link just now and it did the same thing. Python 2.7, by the way. Maybe 2.7 is just too close to 3?

Mine can get 10**100 in no noticeable time, though, so I'm okay with it.

[cemper93]

217: 10100101000

I run it with Python 2.7, too, and it works fine. I runs in Ideone, too: http://ideone.com/NrOjA
Is it possible that your text editor has a limit on line length or such?

Oh, and yes, your version is by far more efficient (and in many ways far more elegant) than mine, which is, to be honest, not even properly golfed (I think I would have been better off without all those lambdas and functional programming stuff). I'm just brute-forcing: To find a Fibonacci number i that fits into a (the number that I want in base Zeckendorf), try every Fibonacci number between 0 and a that was not yet used or consecutive to a number that was already used, and then return any such Fibonacci number that equals a or for that a number is returned if you recurse and repeat with it (try to find a-i). That's grossly inefficient.
I'm thinking: As the Zeckendorf base system turns out to be so systematically, shouldn't there be a O(1) algorithm? May try this later, too busy right now

BTW I'm somewhat staggered by this magic of yours:

Code: Select all

a=range(2*len(bin(n)),0,-1)

What are you doing here, great master?

[Anonymously Famous]

218: 10100101001

I still can't get your lambdas to work... Unfortunately, I don't really have time to debug it right now. I'm pasting it into Idle. Maybe it's the Windows version of Python that's doing something funky? I also tried saving it and running the Python interpreter on it. Is there any prep work (other than setting a)?

a=range(2*len(bin(n)),0,-1)

^ is setting up a Fibonacci series that's at least as long as I need. I'm trying to estimate the number of digits that I need. It turns out that twice the digits of a binary representation of a number is more than enough, but not by an extraordinary amount. "bin" adds on "0b" at the beginning, but that's just 4 extra Fibonacci numbers to calculate, so I don't bother creating the substring. Then I have [..., 3, 2, 1], and since 1 and 2 are the first Fibonacci numbers, I use those to fill in the rest. I could insert numbers as I go, but I figure that it's probably more efficient to create an array that's slightly big than to insert that many times. Of course, it really isn't all that many times... Oh well. It works. Good enough for me.

[Sean Quixote]

220 = 10101000000

[cemper93]

221: 10101000001
219: 10100101010

[Sean Quixote]

222: 10101000010

[Anonymously Famous]

223: 10101000100

[Sean Quixote]

224: 10101000101

[Anonymously Famous]

225: 10101001000

[Sean Quixote]

226: 10101001001

[Anonymously Famous]

227: 10101001010

[Sean Quixote]

228 = 10101010000

[Anonymously Famous]

229 = 10101010001

[Sean Quixote]

230 = 10101010010

[Anonymously Famous]

231 = 10101010100

[Sean Quixote]

232 = 10101010101

Hey, lookee there! Both palindromes.

[Anonymously Famous]

That's nifty.

233 = 100000000000

[Sean Quixote]

234 = 100000000001

[Anonymously Famous]

235 = 100000000010

[Sean Quixote]

236 = 100000000100

[Anonymously Famous]

237 = 100000000101

[Sean Quixote]

238 = 100000001000

[Anonymously Famous]

239 = 100000001001

[Sean Quixote]

240 = 100000001010

[Anonymously Famous]

241 = 100000010000

[Sean Quixote]

242 = 100000010001

[Anonymously Famous]

243 = 100000010010