Count up with Zeckendorf's theorem!
Moderators: jestingrabbit, Moderators General, Prelates
 Sean Quixote
 Posts: 229
 Joined: Tue Sep 14, 2010 1:20 am UTC
 Location: Ubekibekibekibekistanstan
Re: Count up with Zeckendorf's theorem!
204 = 10100001000

 Posts: 240
 Joined: Thu Nov 18, 2010 4:01 am UTC
Re: Count up with Zeckendorf's theorem!
205 = 10100001001
 Sean Quixote
 Posts: 229
 Joined: Tue Sep 14, 2010 1:20 am UTC
 Location: Ubekibekibekibekistanstan
Re: Count up with Zeckendorf's theorem!
206 = 10100001010

 Posts: 240
 Joined: Thu Nov 18, 2010 4:01 am UTC
Re: Count up with Zeckendorf's theorem!
207 = 10100010000
 Sean Quixote
 Posts: 229
 Joined: Tue Sep 14, 2010 1:20 am UTC
 Location: Ubekibekibekibekistanstan
Re: Count up with Zeckendorf's theorem!
208 = 10100010001

 Posts: 240
 Joined: Thu Nov 18, 2010 4:01 am UTC
Re: Count up with Zeckendorf's theorem!
209 = 10100010010
 Sean Quixote
 Posts: 229
 Joined: Tue Sep 14, 2010 1:20 am UTC
 Location: Ubekibekibekibekistanstan
Re: Count up with Zeckendorf's theorem!
210 = 10100010100

 Posts: 240
 Joined: Thu Nov 18, 2010 4:01 am UTC
Re: Count up with Zeckendorf's theorem!
211 = 10100010101
 Sean Quixote
 Posts: 229
 Joined: Tue Sep 14, 2010 1:20 am UTC
 Location: Ubekibekibekibekistanstan
Re: Count up with Zeckendorf's theorem!
212 = 10100100000
Re: Count up with Zeckendorf's theorem!
213 : 10100100001
BTW:
EDIT: Maybe I should add that this is Python. It may not be evident.
BTW:
Code: Select all
f,m,a,g,h=lambda n:int(n<2)or m.get(n)or m.update({n:f(n1)+f(n2)})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(af(i),lset([i,i1,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
 Posts: 229
 Joined: Tue Sep 14, 2010 1:20 am UTC
 Location: Ubekibekibekibekistanstan
Re: Count up with Zeckendorf's theorem!
214 : 10100100010

 Posts: 240
 Joined: Thu Nov 18, 2010 4:01 am UTC
Re: Count up with Zeckendorf's theorem!
215 : 10100100100
What version of Python?
Edit:
It's not as elegant as yours, but it does the job.
Also:
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(n1)+f(n2)})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(af(i),lset([i,i1,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
Re: Count up with Zeckendorf's theorem!
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
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

 Posts: 240
 Joined: Thu Nov 18, 2010 4:01 am UTC
Re: Count up with Zeckendorf's theorem!
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.
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.
Re: Count up with Zeckendorf's theorem!
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 bruteforcing: 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 ai). 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:What are you doing here, great master?
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 bruteforcing: 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 ai). 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)

 Posts: 240
 Joined: Thu Nov 18, 2010 4:01 am UTC
Re: Count up with Zeckendorf's theorem!
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.
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
 Posts: 229
 Joined: Tue Sep 14, 2010 1:20 am UTC
 Location: Ubekibekibekibekistanstan
Re: Count up with Zeckendorf's theorem!
220 = 10101000000
Re: Count up with Zeckendorf's theorem!
221: 10101000001
219: 10100101010
219: 10100101010
 Sean Quixote
 Posts: 229
 Joined: Tue Sep 14, 2010 1:20 am UTC
 Location: Ubekibekibekibekistanstan
Re: Count up with Zeckendorf's theorem!
222: 10101000010

 Posts: 240
 Joined: Thu Nov 18, 2010 4:01 am UTC
Re: Count up with Zeckendorf's theorem!
223: 10101000100
 Sean Quixote
 Posts: 229
 Joined: Tue Sep 14, 2010 1:20 am UTC
 Location: Ubekibekibekibekistanstan
Re: Count up with Zeckendorf's theorem!
224: 10101000101

 Posts: 240
 Joined: Thu Nov 18, 2010 4:01 am UTC
Re: Count up with Zeckendorf's theorem!
225: 10101001000
 Sean Quixote
 Posts: 229
 Joined: Tue Sep 14, 2010 1:20 am UTC
 Location: Ubekibekibekibekistanstan
Re: Count up with Zeckendorf's theorem!
226: 10101001001

 Posts: 240
 Joined: Thu Nov 18, 2010 4:01 am UTC
Re: Count up with Zeckendorf's theorem!
227: 10101001010
 Sean Quixote
 Posts: 229
 Joined: Tue Sep 14, 2010 1:20 am UTC
 Location: Ubekibekibekibekistanstan
Re: Count up with Zeckendorf's theorem!
228 = 10101010000

 Posts: 240
 Joined: Thu Nov 18, 2010 4:01 am UTC
Re: Count up with Zeckendorf's theorem!
229 = 10101010001
 Sean Quixote
 Posts: 229
 Joined: Tue Sep 14, 2010 1:20 am UTC
 Location: Ubekibekibekibekistanstan
Re: Count up with Zeckendorf's theorem!
230 = 10101010010

 Posts: 240
 Joined: Thu Nov 18, 2010 4:01 am UTC
Re: Count up with Zeckendorf's theorem!
231 = 10101010100
 Sean Quixote
 Posts: 229
 Joined: Tue Sep 14, 2010 1:20 am UTC
 Location: Ubekibekibekibekistanstan
Re: Count up with Zeckendorf's theorem!
232 = 10101010101
Hey, lookee there! Both palindromes.
Hey, lookee there! Both palindromes.

 Posts: 240
 Joined: Thu Nov 18, 2010 4:01 am UTC
Re: Count up with Zeckendorf's theorem!
That's nifty.
233 = 100000000000
233 = 100000000000
 Sean Quixote
 Posts: 229
 Joined: Tue Sep 14, 2010 1:20 am UTC
 Location: Ubekibekibekibekistanstan
Re: Count up with Zeckendorf's theorem!
234 = 100000000001

 Posts: 240
 Joined: Thu Nov 18, 2010 4:01 am UTC
Re: Count up with Zeckendorf's theorem!
235 = 100000000010
 Sean Quixote
 Posts: 229
 Joined: Tue Sep 14, 2010 1:20 am UTC
 Location: Ubekibekibekibekistanstan
Re: Count up with Zeckendorf's theorem!
236 = 100000000100

 Posts: 240
 Joined: Thu Nov 18, 2010 4:01 am UTC
Re: Count up with Zeckendorf's theorem!
237 = 100000000101
 Sean Quixote
 Posts: 229
 Joined: Tue Sep 14, 2010 1:20 am UTC
 Location: Ubekibekibekibekistanstan
Re: Count up with Zeckendorf's theorem!
238 = 100000001000

 Posts: 240
 Joined: Thu Nov 18, 2010 4:01 am UTC
Re: Count up with Zeckendorf's theorem!
239 = 100000001001
 Sean Quixote
 Posts: 229
 Joined: Tue Sep 14, 2010 1:20 am UTC
 Location: Ubekibekibekibekistanstan
Re: Count up with Zeckendorf's theorem!
240 = 100000001010

 Posts: 240
 Joined: Thu Nov 18, 2010 4:01 am UTC
Re: Count up with Zeckendorf's theorem!
241 = 100000010000
 Sean Quixote
 Posts: 229
 Joined: Tue Sep 14, 2010 1:20 am UTC
 Location: Ubekibekibekibekistanstan
Re: Count up with Zeckendorf's theorem!
242 = 100000010001

 Posts: 240
 Joined: Thu Nov 18, 2010 4:01 am UTC
Re: Count up with Zeckendorf's theorem!
243 = 100000010010
Who is online
Users browsing this forum: Bing [Bot], Google [Bot], Sizik and 30 guests