Tag Archives: Fibonacci numbers

Bi-Bell Basics

by in Arithmetic, Base Behavior, Binary numbers, Blancmange Curves, Fibonacci Sequence, Fractals, Geometry, Mathematics, Powers and tagged , , , , , , , , , , , , , , , , , | Leave a comment

Here’s what you might call a Sisyphean sequence. It struggles upward, then slips back, over and over again:

1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2...


The struggle goes on for ever. Every time it reaches a new maximum, it will fall back to 1 at the next step. And in fact 1, 2, 3 and all other integers occur infinitely often in the sequence, because it represents the digit-sums of binary numbers:

1 ← 1
1 = 1+0 ← 10 in binary = 2 in base ten
2 = 1+1 ← 11 = 3
1 = 1+0+0 ← 100 = 4
2 = 1+0+1 ← 101 = 5
2 = 1+1+0 ← 110 = 6
3 = 1+1+1 ← 111 = 7
1 = 1+0+0+0 ← 1000 = 8
2 = 1+0+0+1 ← 1001 = 9
2 = 1+0+1+0 ← 1010 = 10
3 = 1+0+1+1 ← 1011 = 11
2 = 1+1+0+0 ← 1100 = 12
3 = 1+1+0+1 ← 1101 = 13
3 = 1+1+1+0 ← 1110 = 14
4 = 1+1+1+1 ← 1111 = 15
1 = 1+0+0+0+0 ← 10000 = 16
2 = 1+0+0+0+1 ← 10001 = 17
2 = 1+0+0+1+0 ← 10010 = 18
3 = 1+0+0+1+1 ← 10011 = 19
2 = 1+0+1+0+0 ← 10100 = 20


Now here’s a related sequence in which all integers do not occur infinitely often:

1, 2, 3, 3, 4, 5, 6, 4, 5, 6, 7, 7, 8, 9, 10, 5, 6, 7, 8, 8, 9, 10, 11, 9, 10, 11, 12, 12, 13, 14, 15, 6, 7, 8, 9, 9, 10, 11, 12, 10, 11, 12, 13, 13, 14, 15, 16, 11, 12, 13, 14, 14, 15, 16, 17, 15, 16, 17, 18, 18, 19, 20, 21, 7, 8, 9, 10, 10, 11, 12, 13, 11, 12, 13, 14, 14, 15, 16, 17, 12, 13, 14, 15, 15, 16, 17, 18, 16, 17, 18, 19, 19, 20, 21, 22, 13, 14, 15, 16, 16, 17, 18, 19, 17, 18, 19, 20, 20, 21, 22, 23, 18, 19, 20, 21, 21, 22, 23, 24, 22, 23, 24, 25, 25, 26, 27, 28, 8, 9, 10, 11, 11, 12, 13, 14, 12, 13, 14, 15, 15...


The sequence represents the sum of the values of occupied columns in the binary numbers, reading from right to left:

10 in binary = 2 in base ten
21 (column values from right to left)
2*1 + 1*0 = 2

11 = 3
21
2*1 + 1*1 = 3

100 = 4
321 (column values from right to left)
3*1 + 2*0 + 1*0 = 3

101 = 5
321
3*1 + 2*0 + 1*1 = 4

110 = 6
321
3*1 + 2*1 + 1*0 = 5

111 = 7
321
3*1 + 2*1 + 1*1 = 6

1000 = 8
4321
4*1 + 3*0 + 2*0 + 1*0 = 4

1001 = 9
4321
4*1 + 3*0 + 2*0 + 1*1 = 5

1010 = 10
4321
4*1 + 3*0 + 2*1 + 1*0 = 6

1011 = 11
4321
4*1 + 3*0 + 2*1 + 1*1 = 7

1100 = 12
4321
4*1 + 3*1 + 2*0 + 1*0 = 7

1101 = 13
4321
4*1 + 3*1 + 2*0 + 1*1 = 8

1110 = 14
4321
4*1 + 3*1 + 2*1 + 1*0 = 9

1111 = 15
4321
4*1 + 3*1 + 2*1 + 1*1 = 10

10000 = 16
54321
5*1 + 4*0 + 3*0 + 2*0 + 1*0 = 5


In that sequence, although no number occurs infinitely often, some numbers occur more often than others. If you represent the count of sums up to a certain digit-length as a graph, you get a famous shape:

Bell curve formed by the count of column-sums in base 2

Bi-bell curves for 1 to 16 binary digits (animated)

In “Pi in the Bi”, I looked at that way of forming the bell curve and called it the bi-bell curve. Now I want to go further. Suppose that you assign varying values to the columns and try other bases. For example, what happens if you assign the values 2^p + 1 to the columns, reading from right to left, then use base 3 to generate the sums? These are the values of 2^p + 1:

2, 3, 5, 9, 17, 33, 65, 129, 257, 513, 1025...


And here’s an example of how you generate a column-sum in base 3:

2102 in base 3 = 65 in base ten
9532 (column values from right to left)
2*9 + 1*5 + 0*3 + 2*2 = 27


The graphs for these column-sums using base 3 look like this as the digit-length rises. They’re no longer bell-curves (and please note that widths and heights have been normalized so that all graphs fit the same space):

Graph for the count of column-sums in base 3 using 2^p + 1 (digit-length <= 7)

(width and height are normalized)

Graph for base 3 and 2^p + 1 (dl<=8)

Graph for base 3 and 2^p + 1 (dl<=9)

Graph for base 3 and 2^p + 1 (dl<=10)

Graph for base 3 and 2^p + 1 (dl<=11)

Graph for base 3 and 2^p + 1 (dl<=12)

Graph for base 3 and 2^p + 1 (animated)

Now try base 3 and column-values of 2^p + 2 = 3, 4, 6, 10, 18, 34, 66, 130, 258, 514, 1026…

Graph for base 3 and 2^p + 2 (dl<=7)

Graph for base 3 and 2^p + 2 (dl<=8)

Graph for base 3 and 2^p + 2 (dl<=9)

Graph for base 3 and 2^p + 2 (dl<=10)

Graph for base 3 and 2^p + 2 (animated)

Now try base 5 and 2^p + 1 for the columns. The original bell curve has become like a fractal called the blancmange curve:

Graph for base 5 and 2^p + 1 (dl<=7)

Graph for base 5 and 2^p + 1 (dl<=8)

Graph for base 5 and 2^p + 1 (dl<=9)

Graph for base 5 and 2^p + 1 (dl<=10)

Graph for base 5 and 2^p + 1 (animated)

And finally, return to base 2 and try the Fibonacci numbers for the columns:

Graph for base 2 and Fibonacci numbers = 1,1,2,3,5… (dl<=7)

Graph for base 2 and Fibonacci numbers (dl<=9)

Graph for base 2 and Fibonacci numbers (dl<=11)

Graph for base 2 and Fibonacci numbers (dl<=13)

Graph for base 2 and Fibonacci numbers (dl<=15)

Graph for base 2 and Fibonacci numbers (animated)

Previously Pre-Posted…

• Pi in the Bi — bell curves generated by binary digits

Sphiral Architect

by in Fibonacci Sequence, Geometry, φ, Mathematics and tagged , , , , , , | Leave a comment

If you’re a fan of Black Sabbath, you may have misread the title of this blog-post. But it’s not “Spiral Architect”, it’s “Sphiral Architect”. And this is a sphiral:

A sphiral
(the red square is the center)

But why do I call it a sphiral? The answer starts with the Fibonacci sequence, which is at once a perfectly simple and profoundly complex sequence of numbers. It’s very easy to create, yet yields endless riches. Simply seed the sequence with 1s, then add the previous two numbers in the sequence to get the next:


1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025...

Each pair of numbers provides a better and better approximation to phi or φ, an irrational number whose decimal digits never end and never fall into a repeating pattern. It satisfies the equations 1/x = x-1 and x^2 = x+1:


1.6180339887498948482045868343656381177203091798... = φ

1 / 1.6180339887498948482045868343656381177203091798... = 0.6180339887498948482045868343656381177203091798...

1.6180339887498948482045868343656381177203091798...^2 = 2.6180339887498948482045868343656381177203091798...

Here are the approximations to φ supplied by successive pairs of numbers in the Fibonacci sequence:


1 = 1/1
2 = 2/1
1.5 = 3/2
1.666... = 5/3
1.6 = 8/5
1.625 = 13/8
1.6153846153846... = 21/13
1.619047619047619047619047... = 34/21
1.6176470588235294117647... = 55/34
1.6181818... = 89/55
1.617977528... = 144/89
1.6180555... = 233/144
1.618025751... = 377/233
1.6180371352785... = 610/377
1.6180327868852459... = 987/610
1.618034447821681864235... = 1597/987
1.6180338134... = 2584/1597
1.61803405572755... = 4181/2584
1.6180339631667... = 6765/4181
1.6180339985218... = 10946/6765
1.618033985... = 17711/10946
1.61803399... = 28657/17711
1.6180339882... = 46368/28657
1.6180339889579... = 75025/46368
1.61803398867... = 121393/75025
1.61803398878... = 196418/121393
1.6180339887383... = 317811/196418
1.6180339887543225376... = 514229/317811
1.6180339887482... = 832040/514229
1.61803398875... = 1346269/832040
1.6180339887496481... = 2178309/1346269
1.618033988749989... = 3524578/2178309
1.61803398874985884835... = 5702887/3524578
1.6180339887499... = 9227465/5702887
1.6180339887498895958965978... = 14930352/9227465
1.6180339887498968544... = 24157817/14930352
1.618033988749894... = 39088169/24157817
1.61803398874989514... = 63245986/39088169
1.6180339887498947364... = 102334155/63245986
1.61803398874989489... = 165580141/102334155
1.618033988749894831892914... = 267914296/165580141
1.618033988749894854435... = 433494437/267914296
1.618033988749894845824745843278261031063704284629608753202985163 = 701408733/433494437
1.6180339887498948491136... = 1134903170/701408733
1.618033988749894847857... = 1836311903/1134903170
1.61803398874989484833721... = 2971215073/1836311903
1.6180339887498948481... = 4807526976/2971215073
1.61803398874989484822... = 7778742049/4807526976
1.618033988749894848197... = 12586269025/7778742049
1.6180339887498948482... = 20365011074/12586269025
1.6180339887498948482045868343656381177203091798... = φ

I decided to look at how integers could be the partial sums of unique Fibonacci numbers. For example:


Using 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

1 = 1
2 = 2
3 = 1+2 = 3
4 = 1+3
5 = 2+3 = 5
6 = 1+2+3 = 1+5
7 = 2+5
8 = 1+2+5 = 3+5 = 8
9 = 1+3+5 = 1+8
10 = 2+3+5 = 2+8
11 = 1+2+3+5 = 1+2+8 = 3+8
12 = 1+3+8
13 = 2+3+8 = 5+8 = 13
14 = 1+2+3+8 = 1+5+8 = 1+13
15 = 2+5+8 = 2+13
16 = 1+2+5+8 = 3+5+8 = 1+2+13 = 3+13
17 = 1+3+5+8 = 1+3+13
18 = 2+3+5+8 = 2+3+13 = 5+13
19 = 1+2+3+5+8 = 1+2+3+13 = 1+5+13
20 = 2+5+13
21 = 1+2+5+13 = 3+5+13 = 8+13 = 21
22 = 1+3+5+13 = 1+8+13 = 1+21
23 = 2+3+5+13 = 2+8+13 = 2+21
24 = 1+2+3+5+13 = 1+2+8+13 = 3+8+13 = 1+2+21 = 3+21
25 = 1+3+8+13 = 1+3+21
26 = 2+3+8+13 = 5+8+13 = 2+3+21 = 5+21
27 = 1+2+3+8+13 = 1+5+8+13 = 1+2+3+21 = 1+5+21
28 = 2+5+8+13 = 2+5+21
29 = 1+2+5+8+13 = 3+5+8+13 = 1+2+5+21 = 3+5+21 = 8+21
30 = 1+3+5+8+13 = 1+3+5+21 = 1+8+21
31 = 2+3+5+8+13 = 2+3+5+21 = 2+8+21

All integers can be represented as partial sums of unique Fibonacci numbers. But what happens when you start removing numbers from the beginning of the Fibonacci sequence, then trying to find partial sums of the integers? Some integers are sumless:


Using 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...

1 has no sum
2 = 2
3 = 3
4 has no sum
5 = 2+3 = 5
6 has no sum
7 = 2+5
8 = 3+5 = 8
9 has no sum
10 = 2+3+5 = 2+8
11 = 3+8
12 has no sum
13 = 2+3+8 = 5+8 = 13
14 has no sum
15 = 2+5+8 = 2+13
16 = 3+5+8 = 3+13
17 has no sum
18 = 2+3+5+8 = 2+3+13 = 5+13
19 has no sum
20 = 2+5+13
21 = 3+5+13 = 8+13 = 21
22 has no sum
23 = 2+3+5+13 = 2+8+13 = 2+21
24 = 3+8+13 = 3+21
25 has no sum
26 = 2+3+8+13 = 5+8+13 = 2+3+21 = 5+21
27 has no sum
28 = 2+5+8+13 = 2+5+21
29 = 3+5+8+13 = 3+5+21 = 8+21
30 has no sum
31 = 2+3+5+8+13 = 2+3+5+21 = 2+8+21

Now try removing more Fibonacci numbers from the sequence:


Using 3, 5, 8, 13, 21, 34, 55, 89, 144, 233...

1 to 2 have no sums
3 = 3
4 has no sum
5 = 5
6 to 7 have no sums
8 = 3+5 = 8
9 to 10 have no sums
11 = 3+8
12 has no sum
13 = 5+8 = 13
14 to 15 have no sums
16 = 3+5+8 = 3+13
17 has no sum
18 = 5+13
19 to 20 have no sums
21 = 3+5+13 = 8+13 = 21
22 to 23 have no sums
24 = 3+8+13 = 3+21
25 has no sum
26 = 5+8+13 = 5+21
27 to 28 have no sums
29 = 3+5+8+13 = 3+5+21 = 8+21
30 to 31 have no sums
32 = 3+8+21

Using 5, 8, 13, 21, 34, 55, 89, 144, 233, 377...

1 to 4 have no sums
5 = 5
6 to 7 have no sums
8 = 8
9 to 12 have no sums
13 = 5+8 = 13
14 to 17 have no sums
18 = 5+13
19 to 20 have no sums
21 = 8+13 = 21
22 to 25 have no sums
26 = 5+8+13 = 5+21
27 to 28 have no sums
29 = 8+21
30 to 33 have no sums
34 = 5+8+21 = 13+21 = 34
35 to 38 have no sums
39 = 5+13+21 = 5+34
40 to 41 have no sums
42 = 8+13+21 = 8+34
43 to 46 have no sums
47 = 5+8+13+21 = 5+8+34 = 13+34
48 to 51 have no sums
52 = 5+13+34

Using 8, 13, 21, 34, 55, 89, 144, 233, 377, 610...

1 to 7 have no sums
8 = 8
9 to 12 have no sums
13 = 13
14 to 20 have no sums
21 = 8+13 = 21
22 to 28 have no sums
29 = 8+21
30 to 33 have no sums
34 = 13+21 = 34
35 to 41 have no sums
42 = 8+13+21 = 8+34
43 to 46 have no sums
47 = 13+34
48 to 54 have no sums
55 = 8+13+34 = 21+34 = 55

Now ask: what fraction of integers can’t be represented as sums as you remove 1,2,3,5… from the Fibonacci sequence? Let’s approach the answer visually and represent the sums on a spiral created in the same way as an Ulam spiral. When the Fib-sums can’t use 1, you get this spiral:

2,3,5-sphiral
(integers that are the partial sums of unique Fibonacci numbers from 2, 3, 5, 8, 13, 21, 34, 55, 89…)

I call it a sphiral, because φ appears in the ratio of white-to-black space in the spiral, as we shall see. Phi also appears in these sphirals:

3,5,8,13-sphiral

5,8,13,21-sphiral

8,13,21,34-sphiral

Sum sphirals from 1,2,3,5 to 8,13,21,34(animated)

How does φ appear in the sphirals? Well, I think it must appear in lots more ways than I’m able to see. But one simple way, as remarked above, is that φ governs the ratio of white-to-black space in each sphiral. When all Fibonacci numbers can be used, there’s no black space, because all integers can be represented as sums of 1, 2, 3, 5, 8, 13, 21, 34, 55, 89… But that changes as numbers are dropped from the beginning of the Fibonacci sequence:


0.6180339887... of integers can be represented as partial sums of 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...
0.6180339887... = 1/φ^1
0.3819660112... of integers can be represented as partial sums of 3, 5, 8, 13, 21, 34, 55, 89, 144, 233...
0.3819660112... = 1/φ^2
0.2360679774... of integers can be represented as partial sums of 5, 8, 13, 21, 34, 55, 89, 144, 233, 377...
0.2360679774... = 1/φ^3
0.1458980337... of integers can be represented as partial sums of 8, 13, 21, 34, 55, 89, 144, 233, 377, 610...
0.1458980337... = 1/φ^4
0.0901699437... of integers can be represented as partial sums of 13, 21, 34, 55, 89, 144, 233, 377, 610, 987...
0.0901699437... = 1/φ^5
0.05572809... of integers can be represented as partial sums of 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597...
0.05572809... = 1/φ^6
0.0344418537... of integers can be represented as partial sums of 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584...
0.0344418537... = 1/φ^7
0.0212862362... of integers can be represented as partial sums of 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181...
0.0212862362... = 1/φ^8
0.0131556174... of integers can be represented as partial sums of 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765...
0.0131556174... = 1/φ^9
0.0081306187... of integers can be represented as partial sums of 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946...
0.0081306187... = 1/φ^10

But why stick to the standard Fibonacci sequence? If you seed a Fibonacci-like sequence with 2s instead of 1s, you get these numbers:


2, 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 288, 466, 754, 1220, 1974, 3194, 5168, 8362, 13530, 21892, 35422, 57314, 92736, 150050, 242786, 392836, 635622, 1028458, 1664080, 2692538, 4356618, 7049156, 11405774, 18454930, 29860704, 48315634, 78176338, 126491972, 204668310...

Obviously, all numbers in the 2,2,4-sequence are even, so no odd number is the partial sum of unique numbers in the sequence. But all even numbers are partial sums of the sequence. In other words:


0.5 of integers can be represented as partial sums of 2, 2, 4, 6, 10, 16, 26, 42, 68, 110...

So what happens when you drop the 2s and represent the sums graphically? You get this attractive sphiral:

4,6,10,16-sphiral (lo-res)

4,6,10,16-sphiral (hi-res)

In the 4,6,10,16-sphiral, the ratio of white-to-black space is 0.3090169943749474241… This is because:


0.3090169943749474241... of integers can be represented as partial sums of 4, 6, 10, 16, 26, 42, 68, 110, 178, 288...
0.3090169943749474241... = φ^1 * 0.5

Now try the 6,10,16,26-sphiral and 10,16,26,42-sphiral:

6,10,16,26-sphiral

10,16,26,42-sphiral

In the 4,6,10,16-sphiral, the ratio of white-to-black space is 0.190983005625… This is because:


0.190983005625... of integers can be represented as partial sums of 6, 10, 16, 26, 42, 68, 110, 178, 288, 466...
0.190983005625... = φ^2 * 0.5

And so on:


0.1180339887498948482... of integers can be represented as partial sums of 10, 16, 26, 42, 68, 110, 178, 288, 466, 754...
0.1180339887498948482... = φ^3 * 0.5
0.072949016875... of integers can be represented as partial sums of 16, 26, 42, 68, 110, 178, 288, 466, 754, 1220...
0.072949016875... = φ^4 * 0.5

Two be Continued…

by in Base Behavior, Digit-sums, Fibonacci Sequence, Integer Sequences, Mathematics, Phi and tagged , , , , , , , , , , , | Leave a comment

Here’s a useless fact that nobody interested in mathematics would ever forget: digsum(fib(2222)) = 2222. That is, if you add the digits of the 2222nd Fibonacci number, you get 2222:


fib(2222) = 104,966,721,620,282,584,734,867,037,988,863,914,269,721,309,244,628,258,918,225,835,217,264,239,539,186,480,867,849,267,122,885,365,019,934,494,625,410,255,045,832,359,715,759,649,385,824,745,506,982,513,773,397,742,803,445,080,995,617,047,976,796,168,678,756,479,470,761,439,513,575,962,955,568,645,505,845,492,393,360,201,582,183,610,207,447,528,637,825,187,188,815,786,270,477,935,419,631,184,553,635,981,047,057,037,341,800,837,414,913,595,584,426,355,208,257,232,868,908,837,817,478,483,039,310,790,967,631,454,123,105,472,742,221,897,397,857,677,674,619,381,961,429,837,434,434,636,098,678,708,225,493,682,469,561

2222 = 1 + 0 + 4 + 9 + 6 + 6 + 7 + 2 + 1 + 6 + 2 + 0 + 2 + 8 + 2 + 5 + 8 + 4 + 7 + 3 + 4 + 8 + 6 + 7 + 0 + 3 + 7 + 9 + 8 + 8 + 8 + 6 + 3 + 9 + 1 + 4 + 2 + 6 + 9 + 7 + 2 + 1 + 3 + 0 + 9 + 2 + 4 + 4 + 6 + 2 + 8 + 2 + 5 + 8 + 9 + 1 + 8 + 2 + 2 + 5 + 8 + 3 + 5 + 2 + 1 + 7 + 2 + 6 + 4 + 2 + 3 + 9 + 5 + 3 + 9 + 1 + 8 + 6 + 4 + 8 + 0 + 8 + 6 + 7 + 8 + 4 + 9 + 2 + 6 + 7 + 1 + 2 + 2 + 8 + 8 + 5 + 3 + 6 + 5 + 0 + 1 + 9 + 9 + 3 + 4 + 4 + 9 + 4 + 6 + 2 + 5 + 4 + 1 + 0 + 2 + 5 + 5 + 0 + 4 + 5 + 8 + 3 + 2 + 3 + 5 + 9 + 7 + 1 + 5 + 7 + 5 + 9 + 6 + 4 + 9 + 3 + 8 + 5 + 8 + 2 + 4 + 7 + 4 + 5 + 5 + 0 + 6 + 9 + 8 + 2 + 5 + 1 + 3 + 7 + 7 + 3 + 3 + 9 + 7 + 7 + 4 + 2 + 8 + 0 + 3 + 4 + 4 + 5 + 0 + 8 + 0 + 9 + 9 + 5 + 6 + 1 + 7 + 0 + 4 + 7 + 9 + 7 + 6 + 7 + 9 + 6 + 1 + 6 + 8 + 6 + 7 + 8 + 7 + 5 + 6 + 4 + 7 + 9 + 4 + 7 + 0 + 7 + 6 + 1 + 4 + 3 + 9 + 5 + 1 + 3 + 5 + 7 + 5 + 9 + 6 + 2 + 9 + 5 + 5 + 5 + 6 + 8 + 6 + 4 + 5 + 5 + 0 + 5 + 8 + 4 + 5 + 4 + 9 + 2 + 3 + 9 + 3 + 3 + 6 + 0 + 2 + 0 + 1 + 5 + 8 + 2 + 1 + 8 + 3 + 6 + 1 + 0 + 2 + 0 + 7 + 4 + 4 + 7 + 5 + 2 + 8 + 6 + 3 + 7 + 8 + 2 + 5 + 1 + 8 + 7 + 1 + 8 + 8 + 8 + 1 + 5 + 7 + 8 + 6 + 2 + 7 + 0 + 4 + 7 + 7 + 9 + 3 + 5 + 4 + 1 + 9 + 6 + 3 + 1 + 1 + 8 + 4 + 5 + 5 + 3 + 6 + 3 + 5 + 9 + 8 + 1 + 0 + 4 + 7 + 0 + 5 + 7 + 0 + 3 + 7 + 3 + 4 + 1 + 8 + 0 + 0 + 8 + 3 + 7 + 4 + 1 + 4 + 9 + 1 + 3 + 5 + 9 + 5 + 5 + 8 + 4 + 4 + 2 + 6 + 3 + 5 + 5 + 2 + 0 + 8 + 2 + 5 + 7 + 2 + 3 + 2 + 8 + 6 + 8 + 9 + 0 + 8 + 8 + 3 + 7 + 8 + 1 + 7 + 4 + 7 + 8 + 4 + 8 + 3 + 0 + 3 + 9 + 3 + 1 + 0 + 7 + 9 + 0 + 9 + 6 + 7 + 6 + 3 + 1 + 4 + 5 + 4 + 1 + 2 + 3 + 1 + 0 + 5 + 4 + 7 + 2 + 7 + 4 + 2 + 2 + 2 + 1 + 8 + 9 + 7 + 3 + 9 + 7 + 8 + 5 + 7 + 6 + 7 + 7 + 6 + 7 + 4 + 6 + 1 + 9 + 3 + 8 + 1 + 9 + 6 + 1 + 4 + 2 + 9 + 8 + 3 + 7 + 4 + 3 + 4 + 4 + 3 + 4 + 6 + 3 + 6 + 0 + 9 + 8 + 6 + 7 + 8 + 7 + 0 + 8 + 2 + 2 + 5 + 4 + 9 + 3 + 6 + 8 + 2 + 4 + 6 + 9 + 5 + 6 + 1

Numbers like this, where k = digsum(fib(k)), are rare. And 2222 is almost certainly the last of them. These are the relevant listings at the Online Encyclopedia of Integer Sequences:


0, 1, 5, 10, 31, 35, 62, 72, 175, 180, 216, 251, 252, 360, 494, 504, 540, 946, 1188, 2222 — A020995, Numbers k such that the sum of the digits of Fibonacci(k) is k.

0, 1, 5, 55, 1346269, 9227465, 4052739537881, 498454011879264, 1672445759041379840132227567949787325, 18547707689471986212190138521399707760, 619220451666590135228675387863297874269396512... — A067515, Fibonacci numbers with index = digit sum.

At least, they’re rare in base 10. What about other bases? Well, they’re rare in all other bases except one: base 11. When I looked there, I quickly found more than 450 numbers where digsum(fib(k),b=11) = k. So here’s an interesting little problem: Why is base 11 so productive? Or maybe I should say: Φ is base 11 so productive?

Mötley Vüe

by in Base Behavior, Digit-sums, Fibonacci Sequence, Integer Sequences, φ, Mathematics and tagged , , , , , , , , , , , , , , , , , , , , | Leave a comment

Here’s the Fibonacci sequence, where each term (after the first two) is created by adding the two previous numbers:


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

In “Fib and Let Tri”, I described how my eye was caught by 55, which is a palindrome, reading the same backwards and forwards. “Were there any other Fibonacci palindromes?” I wondered. So I looked to see. Now my eye has been caught by 55 again, but for another reason. It should be easy to spot another interesting aspect to 55 when the Fibonacci numbers are set out like this:


fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34
fib(10) = 55
fib(11) = 89
fib(12) = 144
fib(13) = 233
fib(14) = 377
fib(15) = 610
fib(16) = 987
fib(17) = 1597
fib(18) = 2584
fib(19) = 4181
fib(20) = 6765
[...]

55 is fib(10), the 10th Fibonacci number, and 5+5 = 10. That is, digsum(fib(10)) = 10. What other Fibonacci numbers work like that? I soon found some and confirmed my answer at the Online Encyclopedia of Integer Sequences:


1, 5, 10, 31, 35, 62, 72, 175, 180, 216, 251, 252, 360, 494, 504, 540, 946, 1188, 2222 — A020995 at OEIS

And that seems to be the lot, according to the OEIS. In base 10, at least, but why stop at base 10? When I looked at base 11, the numbers of digsum(fib(k)) = k didn’t stop coming, because I couldn’t take the Fibonacci numbers very high on my computer. But the OEIS gives a much longer list, starting like this:


1, 5, 13, 41, 53, 55, 60, 61, 90, 97, 169, 185, 193, 215, 265, 269, 353, 355, 385, 397, 437, 481, 493, 617, 629, 630, 653, 713, 750, 769, 780, 889, 905, 960, 1013, 1025, 1045, 1205, 1320, 1405, 1435, 1501, 1620, 1650, 1657, 1705, 1735, 1769, 1793, 1913, 1981, 2125, 2153, 2280, 2297, 2389, 2413, 2460, 2465, 2509, 2533, 2549, 2609, 2610, 2633, 2730, 2749, 2845, 2893, 2915, 3041, 3055, 3155, 3209, 3360, 3475, 3485, 3521, 3641, 3721, 3749, 3757, 3761, 3840, 3865, 3929, 3941, 4075, 4273, 4301, 4650, 4937, 5195, 5209, 5435, 5489, 5490, 5700, 5917, 6169, 6253, 6335, 6361, 6373, 6401, 6581, 6593, 6701, 6750, 6941, 7021, 7349, 7577, 7595, 7693, 7740, 7805, 7873, 8009, 8017, 8215, 8341, 8495, 8737, 8861, 8970, 8995, 9120, 9133, 9181, 9269, 9277, 9535, 9541, 9737, 9935, 9953, 10297, 10609, 10789, 10855, 11317, 11809, 12029, 12175... — A025490 at OEIS

The list ends with 1636597 = A18666[b11] and the OEIS says that 1636597 almost certainly completes the list. According to David C. Terr’s paper “On the Sums of Fibonacci Numbers” (pdf), published in the Fibonacci Quarterly in 1996, the estimated digit-sum for the k-th Fibonacci number in base b is given by the formula (b-1)/2 * k * log(b,φ), where log(b,φ) is the logarithm in base b of the golden ratio, 1·61803398874… Terr then notes that the simplified formula (b-1)/2 * log(b,φ) gives the estimated average ratio digsum(fib(k)) / k in base b. Here are the estimates for bases 2 to 20:


b02 = 0.3471209568153086...
b03 = 0.4380178794859424...
b04 = 0.5206814352229629...
b05 = 0.5979874356654401...
b06 = 0.6714235829697111...
b07 = 0.7418818776805580...
b08 = 0.8099488992357201...
b09 = 0.8760357589718848...
b10 = 0.9404443811249043...
b11 = 1.0034045909311624...
b12 = 1.0650963641043091...
b13 = 1.1256639207937723...
b14 = 1.1852250528196852...
b15 = 1.2438775226715552...
b16 = 1.3017035880574074...
b17 = 1.3587732842474014...
b18 = 1.4151468584732730...
b19 = 1.4708766105122322...
b20 = 1.5260083080264088...

In base 2, you can expect digsum(fib(k)) to be much smaller than k; in base 20, you can expect digsum(fib(k)) to be much larger. But as you can see, the estimate for base 11, 1.0034045909311624…, is very nearly 1. That’s why base 11 produces so many results for digsum(fib(k)) = k, because only a slight deviation from the estimate might create a perfect ratio of 1 for digsum(fib(k)) / k, i.e. digsum(fib(k)) = k. But in the end the results run out in base 11 too, because as k gets higher and fib(k) gets bigger, the estimate becomes more and more accurate and digsum(fib(k)) > k. With lower k, digsum(fib(k)) can easily fall below k or match k. That happens in other bases, but because their estimates are further from 1, results for digsum(fib(k)) = k run out much more quickly.

To see this base behavior represented visually, I’ve created Ulam-like spirals for k using three colors: blue for digsum(fib(k)) < k, yellow for digsum(fib(k)) > k, and red for digsum(fib(k)) = k (with the green square at the center representing fib(1) = 1). As you can see below, the spiral for base 11 immediately stands out. It’s motley, not dominated by blue or yellow like the other spirals:

Spiral for digsum(fib(k)) in base 9
(blue for digsum(fib(k)) < k, yellow for digsum(fib(k)) > k, red for digsum(fib(k)) = k, green for fib(1))

Spiral for digsum(fib(k)) in base 10

Spiral for digsum(fib(k)) in base 11 — a motley view of blue, yellow and red

Spiral for digsum(fib(k)) in base 12

Spiral for digsum(fib(k)) in base 13

Finally, here are spirals at higher and higher resolution for digsum(fib(k)) = k in base 11:

digsum(fib(k)) = k in base 11 (low resolution)
(green square is fib(1))

digsum(fib(k)) = k in base 11 (x2 resolution)

digsum(fib(k)) = k in base 11 (x4)

digsum(fib(k)) = k in base 11 (x8)

digsum(fib(k)) = k in base 11 (x16)

digsum(fib(k)) = k in base 11 (x32)

digsum(fib(k)) = k in base 11 (x64)

digsum(fib(k)) = k in base 11 (x128)

digsum(fib(k)) = k in base 11 (animated)

Fib and Let Tri

by in Base Behavior, Fibonacci Sequence, Integer Sequences, Irrational numbers, φ, Mathematics, Palindromic numbers, Phi and tagged , , , , , , , , , , , , , , , , , , , , , , | Leave a comment

It’s a simple sequence with hidden depths:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155... — A000045 at OEIS

That’s the Fibonacci sequence, probably the most famous of all integer sequences after the integers themselves (1, 2, 3, 4, 5…) and the primes (2, 3, 5, 7, 11…). It has a very simple definition: if fib(fi) is the fi-th number in the Fibonacci sequence, then fib(fi) = fib(fi-1) + fib(fi-2). By definition, fib(1) = fib(2) = 1. After that, it’s easy to generate new numbers:

2 = fib(3) = fib(1) + fib(2) = 1 + 1
3 = fib(4) = fib(2) + fib(3) = 1 + 2
5 = fib(5) = fib(3) + fib(4) = 2 + 3
8 = fib(6) = fib(4) + fib(5) = 3 + 5
13 = fib(7) = fib(5) + fib(6) = 5 + 8
21 = fib(8) = fib(6) + fib(7) = 8 + 13
34 = fib(9) = fib(7) + fib(8) = 13 + 21
55 = fib(10) = fib(8) + fib(9) = 21 + 34
89 = fib(11) = fib(9) + fib(10) = 34 + 55
144 = fib(12) = fib(10) + fib(11) = 55 + 89
233 = fib(13) = fib(11) + fib(12) = 89 + 144
377 = fib(14) = fib(12) + fib(13) = 144 + 233
610 = fib(15) = fib(13) + fib(14) = 233 + 377
987 = fib(16) = fib(14) + fib(15) = 377 + 610
[...]

How to create the Fibonacci sequence is obvious. But it’s not obvious that fib(fi) / fib(fi-1) gives you ever-better approximations to a fascinating constant called φ, the golden ratio, which is 1.618033988749894…:

1/1 = 1
2/1 = 2
3/2 = 1.5
5/3 = 1.66666...
8/5 = 1.6
13/8 = 1.625
21/13 = 1.615384...
34/21 = 1.619047...
55/34 = 1.6176470588235294117647058823...
89/55 = 1.618181818...
144/89 = 1.617977528089887640...
233/144 = 1.6180555555...
377/233 = 1.618025751072961...
610/377 = 1.618037135278514...
987/610 = 1.618032786885245...
[...]

And that’s just the start of the hidden depths in the Fibonacci sequence. I stumbled across another interesting pattern for myself a few days ago. I was looking at the sequence and one of the numbers caught my eye:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597...

55 is a palindrome, reading the same forward and backwards. I wondered whether there were any other palindromes in the sequence (apart from the trivial single-digit palindromes 1, 1, 2, 3…). I couldn’t find any more. Nor can anyone else, apparently. But that’s in base 10. Other bases are more productive. For example, in bases 2, 3 and 4, you get this:

11 in b2 = 3
101 in b2 = 5
10101 in b2 = 21

22 in b3 = 8
111 in b3 = 13
22122 in b3 = 233

11 in b4 = 5
111 in b4 = 21
202 in b4 = 34
313 in b4 = 55

I decided to concentrate on tripals, or palindromes with three digits. I started looking at bases that set records for the greatest number of tripals. And there are some interesting patterns in the digits of the tripals in these bases (when a digit > 9, the digit is represented inside square brackets — see base-29 and higher). See how quickly you can spot the patterns:

Palindromic Fibonacci numbers in base-4

111 in b4 (fib=21, fi=8)
202 in b4 (fib=34, fi=9)
313 in b4 (fib=55, fi=10)

4 = 2^2 (pal=3)

Palindromic Fibonacci numbers in base-11

121 in b11 (fib=144, fi=12)
313 in b11 (fib=377, fi=14)
505 in b11 (fib=610, fi=15)
818 in b11 (fib=987, fi=16)

11 is prime (pal=4)

Palindromic Fibonacci numbers in base-29

151 in b29 (fib=987, fi=16)
323 in b29 (fib=2584, fi=18)
818 in b29 (fib=6765, fi=20)
[13]0[13] in b29 (fib=10946, fi=21)
[21]1[21] in b29 (fib=17711, fi=22)

29 is prime (pal=5)

Palindromic Fibonacci numbers in base-76

1[13]1 in b76 (fib=6765, fi=20)
353 in b76 (fib=17711, fi=22)
828 in b76 (fib=46368, fi=24)
[21]1[21] in b76 (fib=121393, fi=26)
[34]0[34] in b76 (fib=196418, fi=27)
[55]1[55] in b76 (fib=317811, fi=28)

76 = 2^2 * 19 (pal=6)

Palindromic Fibonacci numbers in base-199

1[34]1 in b199 (fib=46368, fi=24)
3[13]3 in b199 (fib=121393, fi=26)
858 in b199 (fib=317811, fi=28)
[21]2[21] in b199 (fib=832040, fi=30)
[55]1[55] in b199 (fib=2178309, fi=32)
[89]0[89] in b199 (fib=3524578, fi=33)
[144]1[144] in b199 (fib=5702887, fi=34)

199 is prime (pal=7)

Palindromic Fibonacci numbers in base-521

1[89]1 in b521 (fib=317811, fi=28)
3[34]3 in b521 (fib=832040, fi=30)
8[13]8 in b521 (fib=2178309, fi=32)
[21]5[21] in b521 (fib=5702887, fi=34)
[55]2[55] in b521 (fib=14930352, fi=36)
[144]1[144] in b521 (fib=39088169, fi=38)
[233]0[233] in b521 (fib=63245986, fi=39)
[377]1[377] in b521 (fib=102334155, fi=40)

521 is prime (pal=8)

Palindromic Fibonacci numbers in base-1364

1[233]1 in b1364 (fib=2178309, fi=32)
3[89]3 in b1364 (fib=5702887, fi=34)
8[34]8 in b1364 (fib=14930352, fi=36)
[21][13][21] in b1364 (fib=39088169, fi=38)
[55]5[55] in b1364 (fib=102334155, fi=40)
[144]2[144] in b1364 (fib=267914296, fi=42)
[377]1[377] in b1364 (fib=701408733, fi=44)
[610]0[610] in b1364 (fib=1134903170, fi=45)
[987]1[987] in b1364 (fib=1836311903, fi=46)

1364 = 2^2 * 11 * 31 (pal=9)

Two patterns are quickly obvious. Every digit in the tripals is a Fibonacci number. And the middle digit of one Fibonacci tripal, fib(fi), becomes fib(fi-2) in the next tripal, while fib(fi), the first and last digits (which are identical), becomes fib(fi+2) in the next tripal.

But what about the bases? If you’re an expert in the Fibonacci sequence, you’ll spot the pattern at work straight away. I’m not an expert, but I spotted it in the end. Here are the first few bases setting records for the numbers of Fibonacci tripals:

4, 11, 29, 76, 199, 521, 1364, 3571, 9349, 24476, 64079, 167761, 439204, 1149851, 3010349, 7881196...

These numbers come from the Lucas sequence, which is closely related to the Fibonacci sequence. But where fib(1) = fib(2) = 1, luc(1) = 1 and luc(2) = 3. After that, luc(li) = luc(li-2) + luc(li-1):

1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349, 15127, 24476, 39603, 64079, 103682, 167761, 271443, 439204, 710647, 1149851, 1860498, 3010349, 4870847, 7881196... — A000204 at OEIS

It seems that every second number from 4 in the Lucas sequence supplies a base in which 1) the number of Fibonacci tripals sets a new record; 2) every digit of the Fibonacci tripals is itself a Fibonacci number.

But can I prove that this is always true? No. And do I understand why these patterns exist? No. My simple search for palindromes in the Fibonacci sequence soon took me far out of my mathematical depth. But it’s been fun to find huge bases like this in which every digit of every Fibonacci tripal is itself a Fibonacci number:

Palindromic Fibonacci numbers in base-817138163596

1[139583862445]1 in b817138163596 (fib=781774079430987230203437, fi=116)
3[53316291173]3 in b817138163596 (fib=2046711111473984623691759, fi=118)
8[20365011074]8 in b817138163596 (fib=5358359254990966640871840, fi=120)
[21][7778742049][21] in b817138163596 (fib=14028366653498915298923761, fi=122)
[55][2971215073][55] in b817138163596 (fib=36726740705505779255899443, fi=124)
[144][1134903170][144] in b817138163596 (fib=96151855463018422468774568, fi=126)
[377][433494437][377] in b817138163596 (fib=251728825683549488150424261, fi=128)
[987][165580141][987] in b817138163596 (fib=659034621587630041982498215, fi=130)
[2584][63245986][2584] in b817138163596 (fib=1725375039079340637797070384, fi=132)
[6765][24157817][6765] in b817138163596 (fib=4517090495650391871408712937, fi=134)
[17711][9227465][17711] in b817138163596 (fib=11825896447871834976429068427, fi=136)
[46368][3524578][46368] in b817138163596 (fib=30960598847965113057878492344, fi=138)
[121393][1346269][121393] in b817138163596 (fib=81055900096023504197206408605, fi=140)
[317811][514229][317811] in b817138163596 (fib=212207101440105399533740733471, fi=142)
[832040][196418][832040] in b817138163596 (fib=555565404224292694404015791808, fi=144)
[2178309][75025][2178309] in b817138163596 (fib=1454489111232772683678306641953, fi=146)
[5702887][28657][5702887] in b817138163596 (fib=3807901929474025356630904134051, fi=148)
[14930352][10946][14930352] in b817138163596 (fib=9969216677189303386214405760200, fi=150)
[39088169][4181][39088169] in b817138163596 (fib=26099748102093884802012313146549, fi=152)
[102334155][1597][102334155] in b817138163596 (fib=68330027629092351019822533679447, fi=154)
[267914296][610][267914296] in b817138163596 (fib=178890334785183168257455287891792, fi=156)
[701408733][233][701408733] in b817138163596 (fib=468340976726457153752543329995929, fi=158)
[1836311903][89][1836311903] in b817138163596 (fib=1226132595394188293000174702095995, fi=160)
[4807526976][34][4807526976] in b817138163596 (fib=3210056809456107725247980776292056, fi=162)
[12586269025][13][12586269025] in b817138163596 (fib=8404037832974134882743767626780173, fi=164)
[32951280099]5[32951280099] in b817138163596 (fib=22002056689466296922983322104048463, fi=166)
[86267571272]2[86267571272] in b817138163596 (fib=57602132235424755886206198685365216, fi=168)
[225851433717]1[225851433717] in b817138163596 (fib=150804340016807970735635273952047185, fi=170)
[365435296162]0[365435296162] in b817138163596 (fib=244006547798191185585064349218729154, fi=171)
[591286729879]1[591286729879] in b817138163596 (fib=394810887814999156320699623170776339, fi=172)

817138163596 = 2^2 * 229 * 9349 * 95419 (pal=30)