Count up with Zeckendorf's theorem!

For all your silly time-killing forum games.

Moderators: jestingrabbit, Prelates, Moderators General

Re: Count up with Zeckendorf's theorem!

Postby Sean Quixote » Wed Nov 09, 2011 4:10 am UTC

204 = 10100001000
User avatar
Sean Quixote
 
Posts: 219
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

Re: Count up with Zeckendorf's theorem!

Postby Anonymously Famous » Wed Nov 09, 2011 5:38 am UTC

205 = 10100001001
Anonymously Famous
 
Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

Re: Count up with Zeckendorf's theorem!

Postby Sean Quixote » Wed Nov 09, 2011 6:32 am UTC

206 = 10100001010
User avatar
Sean Quixote
 
Posts: 219
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

Re: Count up with Zeckendorf's theorem!

Postby Anonymously Famous » Wed Nov 09, 2011 7:22 am UTC

207 = 10100010000
Anonymously Famous
 
Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

Re: Count up with Zeckendorf's theorem!

Postby Sean Quixote » Wed Nov 09, 2011 3:16 pm UTC

208 = 10100010001
User avatar
Sean Quixote
 
Posts: 219
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

Re: Count up with Zeckendorf's theorem!

Postby Anonymously Famous » Wed Nov 09, 2011 3:29 pm UTC

209 = 10100010010
Anonymously Famous
 
Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

Re: Count up with Zeckendorf's theorem!

Postby Sean Quixote » Wed Nov 09, 2011 5:33 pm UTC

210 = 10100010100
User avatar
Sean Quixote
 
Posts: 219
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

Re: Count up with Zeckendorf's theorem!

Postby Anonymously Famous » Wed Nov 09, 2011 9:52 pm UTC

211 = 10100010101
Anonymously Famous
 
Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

Re: Count up with Zeckendorf's theorem!

Postby Sean Quixote » Thu Nov 10, 2011 12:11 am UTC

212 = 10100100000
User avatar
Sean Quixote
 
Posts: 219
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

Re: Count up with Zeckendorf's theorem!

Postby cemper93 » Thu Nov 10, 2011 12:42 am UTC

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.
Hello good friend.<br>Thank you for the kind insight. To gain free XBOX, please click this link <a href="http://forums.xkcd.com/viewtopic.php?f=53&t=37971">for m&ouml;re information visit our website.</a><br>Also more can be found.<br>Best regard
User avatar
cemper93
 
Posts: 181
Joined: Sun Feb 20, 2011 2:35 pm UTC
Location: `pwd`

Re: Count up with Zeckendorf's theorem!

Postby Sean Quixote » Thu Nov 10, 2011 2:32 am UTC

214 : 10100100010
User avatar
Sean Quixote
 
Posts: 219
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

Re: Count up with Zeckendorf's theorem!

Postby Anonymously Famous » Thu Nov 10, 2011 3:23 am UTC

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
Anonymously Famous
 
Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

Re: Count up with Zeckendorf's theorem!

Postby cemper93 » Thu Nov 10, 2011 10:13 am UTC

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
Hello good friend.<br>Thank you for the kind insight. To gain free XBOX, please click this link <a href="http://forums.xkcd.com/viewtopic.php?f=53&t=37971">for m&ouml;re information visit our website.</a><br>Also more can be found.<br>Best regard
User avatar
cemper93
 
Posts: 181
Joined: Sun Feb 20, 2011 2:35 pm UTC
Location: `pwd`

Re: Count up with Zeckendorf's theorem!

Postby Anonymously Famous » Thu Nov 10, 2011 2:49 pm UTC

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.
Anonymously Famous
 
Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

Re: Count up with Zeckendorf's theorem!

Postby cemper93 » Thu Nov 10, 2011 5:35 pm UTC

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? ;)
Hello good friend.<br>Thank you for the kind insight. To gain free XBOX, please click this link <a href="http://forums.xkcd.com/viewtopic.php?f=53&t=37971">for m&ouml;re information visit our website.</a><br>Also more can be found.<br>Best regard
User avatar
cemper93
 
Posts: 181
Joined: Sun Feb 20, 2011 2:35 pm UTC
Location: `pwd`

Re: Count up with Zeckendorf's theorem!

Postby Anonymously Famous » Fri Nov 11, 2011 12:54 am UTC

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. :)
Anonymously Famous
 
Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

Re: Count up with Zeckendorf's theorem!

Postby Sean Quixote » Fri Nov 11, 2011 5:00 pm UTC

220 = 10101000000
User avatar
Sean Quixote
 
Posts: 219
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

Re: Count up with Zeckendorf's theorem!

Postby cemper93 » Fri Nov 11, 2011 8:16 pm UTC

221: 10101000001
219: 10100101010
Hello good friend.<br>Thank you for the kind insight. To gain free XBOX, please click this link <a href="http://forums.xkcd.com/viewtopic.php?f=53&t=37971">for m&ouml;re information visit our website.</a><br>Also more can be found.<br>Best regard
User avatar
cemper93
 
Posts: 181
Joined: Sun Feb 20, 2011 2:35 pm UTC
Location: `pwd`

Re: Count up with Zeckendorf's theorem!

Postby Sean Quixote » Sat Nov 12, 2011 2:18 am UTC

222: 10101000010
User avatar
Sean Quixote
 
Posts: 219
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

Re: Count up with Zeckendorf's theorem!

Postby Anonymously Famous » Sat Nov 12, 2011 7:06 am UTC

223: 10101000100
Anonymously Famous
 
Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

Re: Count up with Zeckendorf's theorem!

Postby Sean Quixote » Sat Nov 12, 2011 3:21 pm UTC

224: 10101000101
User avatar
Sean Quixote
 
Posts: 219
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

Re: Count up with Zeckendorf's theorem!

Postby Anonymously Famous » Sat Nov 12, 2011 4:31 pm UTC

225: 10101001000
Anonymously Famous
 
Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

Re: Count up with Zeckendorf's theorem!

Postby Sean Quixote » Sat Nov 12, 2011 6:06 pm UTC

226: 10101001001
User avatar
Sean Quixote
 
Posts: 219
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

Re: Count up with Zeckendorf's theorem!

Postby Anonymously Famous » Sat Nov 12, 2011 9:06 pm UTC

227: 10101001010
Anonymously Famous
 
Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

Re: Count up with Zeckendorf's theorem!

Postby Sean Quixote » Sun Nov 13, 2011 12:51 am UTC

228 = 10101010000
User avatar
Sean Quixote
 
Posts: 219
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

Re: Count up with Zeckendorf's theorem!

Postby Anonymously Famous » Fri Nov 18, 2011 10:09 pm UTC

229 = 10101010001
Anonymously Famous
 
Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

Re: Count up with Zeckendorf's theorem!

Postby Sean Quixote » Sat Nov 19, 2011 2:03 am UTC

230 = 10101010010
User avatar
Sean Quixote
 
Posts: 219
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

Re: Count up with Zeckendorf's theorem!

Postby Anonymously Famous » Sun Nov 20, 2011 4:16 am UTC

231 = 10101010100
Anonymously Famous
 
Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

Re: Count up with Zeckendorf's theorem!

Postby Sean Quixote » Sun Nov 20, 2011 7:36 pm UTC

232 = 10101010101

Hey, lookee there! Both palindromes. :D
User avatar
Sean Quixote
 
Posts: 219
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

Re: Count up with Zeckendorf's theorem!

Postby Anonymously Famous » Mon Nov 21, 2011 4:47 am UTC

That's nifty.

233 = 100000000000
Anonymously Famous
 
Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

Re: Count up with Zeckendorf's theorem!

Postby Sean Quixote » Mon Nov 21, 2011 9:34 pm UTC

234 = 100000000001
User avatar
Sean Quixote
 
Posts: 219
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

Re: Count up with Zeckendorf's theorem!

Postby Anonymously Famous » Mon Nov 21, 2011 10:02 pm UTC

235 = 100000000010
Anonymously Famous
 
Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

Re: Count up with Zeckendorf's theorem!

Postby Sean Quixote » Mon Nov 21, 2011 10:13 pm UTC

236 = 100000000100
User avatar
Sean Quixote
 
Posts: 219
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

Re: Count up with Zeckendorf's theorem!

Postby Anonymously Famous » Tue Nov 22, 2011 2:36 am UTC

237 = 100000000101
Anonymously Famous
 
Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

Re: Count up with Zeckendorf's theorem!

Postby Sean Quixote » Tue Nov 22, 2011 2:51 am UTC

238 = 100000001000
User avatar
Sean Quixote
 
Posts: 219
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

Re: Count up with Zeckendorf's theorem!

Postby Anonymously Famous » Tue Nov 22, 2011 8:57 pm UTC

239 = 100000001001
Anonymously Famous
 
Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

Re: Count up with Zeckendorf's theorem!

Postby Sean Quixote » Tue Nov 22, 2011 11:28 pm UTC

240 = 100000001010
User avatar
Sean Quixote
 
Posts: 219
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

Re: Count up with Zeckendorf's theorem!

Postby Anonymously Famous » Wed Nov 23, 2011 2:56 pm UTC

241 = 100000010000
Anonymously Famous
 
Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

Re: Count up with Zeckendorf's theorem!

Postby Sean Quixote » Wed Nov 23, 2011 3:13 pm UTC

242 = 100000010001
User avatar
Sean Quixote
 
Posts: 219
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

Re: Count up with Zeckendorf's theorem!

Postby Anonymously Famous » Wed Nov 23, 2011 7:24 pm UTC

243 = 100000010010
Anonymously Famous
 
Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

PreviousNext

Return to Forum Games

Who is online

Users browsing this forum: ShortChelsea and 1 guest