## Count up with Zeckendorf's theorem!

For all your silly time-killing forum games.

Moderators: jestingrabbit, Moderators General, Prelates

### Count up with Zeckendorf's theorem!

Wikipedia wrote:Zeckendorf's theorem states that every positive integer can be represented uniquely as the sum of one or more distinct Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers.

1 = 1
2 = 10
3 = 100
4 = 101
5 = 1000
6 = ...?

Just for reference, and those unfamiliar with the Fibonacci sequence who want to play, the first few Fibonacci numbers are:

1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711

That should do us just fine, for now...
Last edited by Sean Quixote on Wed Sep 28, 2011 8:29 pm UTC, edited 1 time in total.

Sean Quixote

Posts: 212
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

### Re: Count up with Zeckendorf's theorem!

6 = 111
Mighty Jalapeno wrote:
Tyndmyr wrote:
Роберт wrote:Sure, but at least they hit the intended target that time.

Well, if you shoot enough people, you're bound to get the right one eventually.

Thats the best description of the USA ever.
curtis95112

Posts: 607
Joined: Thu Jan 27, 2011 5:23 pm UTC

### Re: Count up with Zeckendorf's theorem!

7 = 1010, if I'm understanding this correctly.
Anonymously Famous

Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

### Re: Count up with Zeckendorf's theorem!

Looks like 6 should have been 1001 since the Fibonacci numbers cannot be consecutive (i.e. your number should never have 2 ones next to each other).

8 = 10000

a-wan

Posts: 5
Joined: Thu Jun 09, 2011 3:51 pm UTC

### Re: Count up with Zeckendorf's theorem!

9 = 10001

That's right, a-wan. Basically the way I see it, what's going to go on here is we're gonna pretend like we're translating Zeckendorf's representation into a base system that resembles binary, in that it will contain only ones and zeros. The Fibonacci numbers will be our "orders of magnitude" or place values: from the rightmost digit, just go in your head, "1, 2, 3, 5, 8, 13, 21, 34, 55, etc..."

Sean Quixote

Posts: 212
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

### Re: Count up with Zeckendorf's theorem!

10 = 10010

This doesn't look like a very efficient number system for small numbers. I'm sure it gets better for larger ones.
Anonymously Famous

Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

### Re: Count up with Zeckendorf's theorem!

11 = 10100

Yeah, not really. Never even though of that before, but yeah, not really. I guess, every time we reach another Fibonacci number, the efficiency ratio will improve by approximately a factor of phi?

Sean Quixote

Posts: 212
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

### Re: Count up with Zeckendorf's theorem!

12 = 10101

a-wan

Posts: 5
Joined: Thu Jun 09, 2011 3:51 pm UTC

### Re: Count up with Zeckendorf's theorem!

13 = 100000

Sean Quixote

Posts: 212
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

### Re: Count up with Zeckendorf's theorem!

14 = 100001

a-wan

Posts: 5
Joined: Thu Jun 09, 2011 3:51 pm UTC

### Re: Count up with Zeckendorf's theorem!

15 = 100010

Sean Quixote

Posts: 212
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

### Re: Count up with Zeckendorf's theorem!

16 = 100100

a-wan

Posts: 5
Joined: Thu Jun 09, 2011 3:51 pm UTC

### Re: Count up with Zeckendorf's theorem!

17 = 100101

Ah, 17... Anyone wanna take a gander as to what it has in common with 72, 305, 1292, 5473, et cetera?

Sean Quixote

Posts: 212
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

### Re: Count up with Zeckendorf's theorem!

18 = 101000

At a guess and a look at a couple of them, it looks like they're all 100...101
Anonymously Famous

Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

### Re: Count up with Zeckendorf's theorem!

19 = 101001

Eh.. maybe. I dunno actually, because the answer I was looking for technically has little if anything to do with the Zeckendorf's representation. It has more to do with another thing that I came up with, but I never was sure what I should call it...

Sean Quixote

Posts: 212
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

### Re: Count up with Zeckendorf's theorem!

20 = 101010

a-wan

Posts: 5
Joined: Thu Jun 09, 2011 3:51 pm UTC

### Re: Count up with Zeckendorf's theorem!

21 = 1000000

Sean Quixote wrote:Ah, 17... Anyone wanna take a gander as to what it has in common with 72, 305, 1292, 5473, et cetera?

If you don't want a spoiler alert: You might not want to read my thread over in the math forum.

Sean Quixote

Posts: 212
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

### Re: Count up with Zeckendorf's theorem!

22 = 1000001
Anonymously Famous

Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

### Re: Count up with Zeckendorf's theorem!

23 = 1000010

Sean Quixote

Posts: 212
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

### Re: Count up with Zeckendorf's theorem!

24 = 1000100
Anonymously Famous

Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

### Re: Count up with Zeckendorf's theorem!

25 = 1000101

Sean Quixote

Posts: 212
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

### Re: Count up with Zeckendorf's theorem!

26 = 1001000
Anonymously Famous

Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

### Re: Count up with Zeckendorf's theorem!

27 = 1001001

Sean Quixote

Posts: 212
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

### Re: Count up with Zeckendorf's theorem!

28 = 1001010
Anonymously Famous

Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

### Re: Count up with Zeckendorf's theorem!

29 = 1010000

I've never actually written this stuff out before (and now I guess I shouldn't have to ) so I just realized another thing that's going on here: if someone came along one day and said, "I want to create a base system that only has two symbols (1 and 0), but let's say that numbers can only be written in such a way that the 1s never touch eachother..." This is also what you would come up with.

Sean Quixote

Posts: 212
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

### Re: Count up with Zeckendorf's theorem!

30 = 1010001
Anonymously Famous

Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

### Re: Count up with Zeckendorf's theorem!

31 = 1010010

Sean Quixote

Posts: 212
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

### Re: Count up with Zeckendorf's theorem!

32 = 1010100
Anonymously Famous

Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

### Re: Count up with Zeckendorf's theorem!

33 = 1010101

Sean Quixote

Posts: 212
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

### Re: Count up with Zeckendorf's theorem!

34 = 10000000
Anonymously Famous

Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

### Re: Count up with Zeckendorf's theorem!

35 = 10000001

a-wan

Posts: 5
Joined: Thu Jun 09, 2011 3:51 pm UTC

### Re: Count up with Zeckendorf's theorem!

36 = 10000010

Sean Quixote

Posts: 212
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

### Re: Count up with Zeckendorf's theorem!

37 = 10000100
Anonymously Famous

Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

### Re: Count up with Zeckendorf's theorem!

38 = 10000101

Sean Quixote

Posts: 212
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

### Re: Count up with Zeckendorf's theorem!

39 = 10001000
Anonymously Famous

Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

### Re: Count up with Zeckendorf's theorem!

40 = 10001001

Sean Quixote

Posts: 212
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

### Re: Count up with Zeckendorf's theorem!

41 = 10001010
Anonymously Famous

Posts: 240
Joined: Thu Nov 18, 2010 4:01 am UTC

### Re: Count up with Zeckendorf's theorem!

42 = 10010000

Sean Quixote

Posts: 212
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

### Re: Count up with Zeckendorf's theorem!

43 = 10010001
gaga654

Posts: 12
Joined: Tue Mar 01, 2011 1:37 am UTC

### Re: Count up with Zeckendorf's theorem!

44 = 10010010

Sean Quixote

Posts: 212
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

Next