Root Pursuit

Roots are hard, powers are easy. For example, the square root of 2, or √2, is the mysterious and never-ending number that is equal to 2 when multiplied by itself:

• √2 = 1·414213562373095048801688724209698078569671875376948073...

It’s hard to calculate √2. But the powers of 2, or 2^p, are the straightforward numbers that you get by multiplying 2 repeatedly by itself. It’s easy to calculate 2^p:

• 2 = 2^1
• 4 = 2^2
• 8 = 2^3
• 16 = 2^4
• 32 = 2^5
• 64 = 2^6
• 128 = 2^7
• 256 = 2^8
• 512 = 2^9
• 1024 = 2^10
• 2048 = 2^11
• 4096 = 2^12
• 8192 = 2^13
• 16384 = 2^14
• 32768 = 2^15
• 65536 = 2^16
• 131072 = 2^17
• 262144 = 2^18
• 524288 = 2^19
• 1048576 = 2^20
[...]

But there is a way to find √2 by finding 2^p, as I discovered after I asked a simple question about 2^p and 3^p. What are the longest runs of matching digits at the beginning of each power?

131072 = 2^17
129140163 = 3^17
1255420347077336152767157884641... = 2^193
1214512980685298442335534165687... = 3^193
2175541218577478036232553294038... = 2^619
2177993962169082260270654106078... = 3^619
7524389324549354450012295667238... = 2^2016
7524012611682575322123383229826... = 3^2016

There’s no obvious pattern. Then I asked the same question about 2^p and 5^p. And an interesting pattern appeared:

32 = 2^5
3125 = 5^5
316912650057057350374175801344 = 2^98
3155443620884047221646914261131... = 5^98
3162535207926728411757739792483... = 2^1068
3162020133383977882730040274356... = 5^1068
3162266908803418110961625404267... = 2^127185
3162288411569894029343799063611... = 5^127185

The digits 31622 rang a bell. Isn’t that the start of √10? Yes, it is:

• √10 = 3·1622776601683793319988935444327185337195551393252168268575...

I wrote a fast machine-code program to find even longer runs of matching initial digits. Sure enough, the pattern continued:

• 316227... = 2^2728361
• 316227... = 5^2728361
• 3162277... = 2^15917834
• 3162277... = 5^15917834
• 31622776... = 2^73482154
• 31622776... = 5^73482154
• 3162277660... = 2^961700165
• 3162277660... = 5^961700165

But why are powers of 2 and 5 generating the digits of √10? If you’re good at math, that’s a trivial question about a trivial discovery. Here’s the answer: We use base ten and 10 = 2 * 5, 10^2 = 100 = 2^2 * 5^2 = 4 * 25, 10^3 = 1000 = 2^3 * 5^3 = 8 * 125, and so on. When the initial digits of 2^p and 5^p match, those matching digits must come from the digits of √10. Otherwise the product of 2^p * 5^p would be too large or too small. Here are the records for matching initial digits multiplied by themselves:

32 = 2^5
3125 = 5^5
• 3^2 = 9

316912650057057350374175801344 = 2^98
3155443620884047221646914261131... = 5^98
• 31^2 = 961

3162535207926728411757739792483... = 2^1068
3162020133383977882730040274356... = 5^1068
• 3162^2 = 9998244

3162266908803418110961625404267... = 2^127185
3162288411569894029343799063611... = 5^127185
• 31622^2 = 999950884

• 316227... = 2^2728361
• 316227... = 5^2728361
• 316227^2 = 99999515529

• 3162277... = 2^15917834
• 3162277... = 5^15917834
• 3162277^2 = 9999995824729

• 31622776... = 2^73482154
• 31622776... = 5^73482154
• 31622776^2 = 999999961946176

• 3162277660... = 2^961700165
• 3162277660... = 5^961700165
• 3162277660^2 = 9999999998935075600

The square of each matching run falls short of 10^p. And so when the digits of 2^p and 5^p stop matching, one power must fall below √10, as it were, and one must rise above:

3 162266908803418110961625404267... = 2^127185
3·162277660168379331998893544432... = √10
3 162288411569894029343799063611... = 5^127185

In this way, 2^p * 5^p = 10^p. And that’s why matching initial digits of 2^p and 5^p generate the digits of √10. The same thing, mutatis mutandis, happens in base 6 with 2^p and 3^p, because 6 = 2 * 3:

• 2.24103122055214532500432040411... = √6 (in base 6)

24 = 2^4
213 = 3^4
225522024 = 2^34 in base 6 = 2^22 in base 10
22225525003213 = 3^34 (3^22)
2241525132535231233233555114533... = 2^1303 (2^327)
2240133444421105112410441102423... = 3^1303 (3^327)
2241055222343212030022044325420... = 2^153251 (2^15007)
2241003215453455515322105001310... = 3^153251 (3^15007)
2241032233315203525544525150530... = 2^233204 (2^20164)
2241030204225410320250422435321... = 3^233204 (3^20164)
2241031334114245140003252435303... = 2^2110415 (2^102539)
2241031103430053425141014505442... = 3^2110415 (3^102539)

And in base 30, where 30 = 2 * 3 * 5, you can find the digits of √30 in three different ways, because 30 = 2 * 15 = 3 * 10 = 5 * 6:

• 5·E9F2LE6BBPBF0F52B7385PE6E5CLN... = √30 (in base 30)

55AA4 = 2^M in base 30 = 2^22 in base 10
5NO6CQN69C3Q0E1Q7F = F^M = 15^22
5E63NMOAO4JPQD6996F3HPLIMLIRL6F... = 2^K6 (2^606)
5ECQDMIOCIAIR0DGJ4O4H8EN10AQ2GR... = F^K6 (15^606)
5E9DTE7BO41HIQDDO0NB1MFNEE4QJRF... = 2^B14 (2^9934)
5E9G5SL7KBNKFLKSG89J9J9NT17KHHO... = F^B14 (15^9934)
[...]
5R4C9 = 3^E in base 30 = 3^14 in base 10
52CE6A3L3A = A^E = 10^14
5E6SOQE5II5A8IRCH9HFBGO7835KL8A = 3^3N (3^113)
5EC1BLQHNJLTGD00SLBEDQ73AH465E3... = A^3N (10^113)
5E9FI455MQI4KOJM0HSBP3GG6OL9T8P... = 3^EJH (3^13187)
5E9EH8N8D9TR1AH48MT7OR3MHAGFNFQ... = A^EJH (10^13187)
[...]
5OCNCNRAP = 5^I in base 30 = 5^18 in base 10
54NO22GI76 = 6^I (6^18)
5EG4RAMD1IGGHQ8QS2QR0S0EH09DK16... = 5^1M7 (5^1567)
5E2PG4Q2G63DOBIJ54E4O035Q9TEJGH... = 6^1M7 (6^1567)
5E96DB9T6TBIM1FCCK8A8J7IDRCTM71... = 5^F9G (5^13786)
5E9NM222PN9Q9TEFTJ94261NRBB8FCH... = 6^F9G (6^13786)
[...]

So that’s √10, √6 and √30. But I said at the beginning that you can find √2 by finding 2^p. How do you do that? By offsetting the powers, as it were. With 2^p and 5^p, you can find the digits of √10. With 2^(p+1) and 5^p, you can find the digits of √2 and √20, because 2^(p+1) * 5^p = 2 * 2^p * 5^p = 2 * 10^p:

•  √2 = 1·414213562373095048801688724209698078569671875376948073...
• √20 = 4·472135954999579392818347337462552470881236719223051448...

16 = 2^4
125 = 5^3
140737488355328 = 2^47
142108547152020037174224853515625 = 5^46
1413... = 2^243
1414... = 5^242
14141... = 2^6651
14142... = 5^6650
141421... = 2^35389
141420... = 5^35388
4472136... = 2^162574
4472135... = 5^162573
141421359... = 2^3216082
141421352... = 5^3216081
447213595... = 2^172530387
447213595... = 5^172530386
[...]

God Give Me Benf’

In “Wake the Snake”, I looked at the digits of powers of 2 and mentioned a fascinating mathematical phenomenon known as Benford’s law, which governs — in a not-yet-fully-explained way — the leading digits of a wide variety of natural and human statistics, from the lengths of rivers to the votes cast in elections. Benford’s law also governs a lot of mathematical data. It states, for example, that the first digit, d, of a power of 2 in base b (except b = 2, 4, 8, 16…) will occur with the frequency logb(1 + 1/d). In base 10, therefore, Benford’s law states that the digits 1..9 will occur with the following frequencies at the beginning of 2^p:

1: 30.102999%
2: 17.609125%
3: 12.493873%
4: 09.691001%
5: 07.918124%
6: 06.694678%
7: 05.799194%
8: 05.115252%
9: 04.575749%

Here’s a graph of the actual relative frequencies of 1..9 as the leading digit of 2^p (open images in a new window if they appear distorted):


And here’s a graph for the predicted frequencies of 1..9 as the leading digit of 2^p, as calculated by the log(1+1/d) of Benford’s law:


The two graphs agree very well. But Benford’s law applies to more than one leading digit. Here are actual and predicted graphs for the first two leading digits of 2^p, 10..99:



And actual and predicted graphs for the first three leading digits of 2^p, 100..999:



But you can represent the leading digit of 2^p in another way: using an adaptation of the famous Ulam spiral. Suppose powers of 2 are represented as a spiral of squares that begins like this, with 2^0 in the center, 2^1 to the right of center, 2^2 above 2^1, and so on:

←←←⮲
432↑
501↑
6789

If the digits of 2^p start with 1, fill the square in question; if the digits of 2^p don’t start with 1, leave the square empty. When you do this, you get this interesting pattern (the purple square at the very center represents 2^0):

Ulam-like power-spiral for 2^p where 1 is the leading digit


Here’s a higher-resolution power-spiral for 1 as the leading digit:

Power-spiral for 2^p, leading-digit = 1 (higher resolution)


And here, at higher resolution still, are power-spirals for all the possible leading digits of 2^p, 1..9 (some spirals look very similar, so you have to compare those ones carefully):

Power-spiral for 2^p, leading-digit = 1 (very high resolution)


Power-spiral for 2^p, leading-digit = 2


Power-spiral for 2^p, ld = 3


Power-spiral for 2^p, ld = 4


Power-spiral for 2^p, ld = 5


Power-spiral for 2^p, ld = 6


Power-spiral for 2^p, ld = 7


Power-spiral for 2^p, ld = 8


Power-spiral for 2^p, ld = 9


Power-spiral for 2^p, ld = 1..9 (animated)


Now try the power-spiral of 2^p, ld = 1, in some other bases:

Power-spiral for 2^p, leading-digit = 1, base = 9


Power-spiral for 2^p, ld = 1, b = 15


You can also try power-spirals for other n^p. Here’s 3^p:

Power-spiral for 3^p, ld = 1, b = 10


Power-spiral for 3^p, ld = 2, b = 10


Power-spiral for 3^p, ld = 1, b = 4


Power-spiral for 3^p, ld = 1, b = 7


Power-spiral for 3^p, ld = 1, b = 18


Elsewhere Other-Accessible…

Wake the Snake — an earlier look at the digits of 2^p

Wake the Snake

In my story “Kopfwurmkundalini”, I imagined the square root of 2 as an infinitely long worm or snake whose endlessly varying digit-segments contained all stories ever (and never) written:

• √2 = 1·414213562373095048801688724209698078569671875376948073…

But there’s another way to get all stories ever written from the number 2. You don’t look at the root(s) of 2, but at the powers of 2:

• 2 = 2^1 = 2
• 4 = 2^2 = 2*2
• 8 = 2^3 = 2*2*2
• 16 = 2^4 = 2*2*2*2
• 32 = 2^5 = 2*2*2*2*2
• 64 = 2^6 = 2*2*2*2*2*2
• 128 = 2^7 = 2*2*2*2*2*2*2
• 256 = 2^8 = 2*2*2*2*2*2*2*2
• 512 = 2^9 = 2*2*2*2*2*2*2*2*2
• 1024 = 2^10
• 2048 = 2^11
• 4096 = 2^12
• 8192 = 2^13
• 16384 = 2^14
• 32768 = 2^15
• 65536 = 2^16
• 131072 = 2^17
• 262144 = 2^18
• 524288 = 2^19
• 1048576 = 2^20
• 2097152 = 2^21
• 4194304 = 2^22
• 8388608 = 2^23
• 16777216 = 2^24
• 33554432 = 2^25
• 67108864 = 2^26
• 134217728 = 2^27
• 268435456 = 2^28
• 536870912 = 2^29
• 1073741824 = 2^30
[...]

The powers of 2 are like an ever-lengthening snake swimming across a pool. The snake has an endlessly mutating head and a rhythmically waving tail with a regular but ever-more complex wake. That is, the leading digits of 2^p don’t repeat but the trailing digits do. Look at the single final digit of 2^p, for example:

• 02 = 2^1
• 04 = 2^2
• 08 = 2^3
• 16 = 2^4
• 32 = 2^5
• 64 = 2^6
• 128 = 2^7
• 256 = 2^8
• 512 = 2^9
• 1024 = 2^10
• 2048 = 2^11
• 4096 = 2^12
• 8192 = 2^13
• 16384 = 2^14
• 32768 = 2^15
• 65536 = 2^16
• 131072 = 2^17
• 262144 = 2^18
• 524288 = 2^19
• 1048576 = 2^20
• 2097152 = 2^21
• 4194304 = 2^22
[...]

The final digit of 2^p falls into a loop: 2 → 4 → 8 → 6 → 2 → 4→ 8…

Now try the final two digits of 2^p:

02 = 2^1
04 = 2^2
08 = 2^3
16 = 2^4
32 = 2^5
64 = 2^6
• 128 = 2^7
• 256 = 2^8
• 512 = 2^9
• 1024 = 2^10
• 2048 = 2^11
• 4096 = 2^12
• 8192 = 2^13
• 16384 = 2^14
• 32768 = 2^15
• 65536 = 2^16
• 131072 = 2^17
• 262144 = 2^18
• 524288 = 2^19
• 1048576 = 2^20
• 2097152 = 2^21
• 4194304 = 2^22
• 8388608 = 2^23
• 16777216 = 2^24
• 33554432 = 2^25
• 67108864 = 2^26
• 134217728 = 2^27
• 268435456 = 2^28
• 536870912 = 2^29
• 1073741824 = 2^30
[...]

Now there’s a longer loop: 02 → 04 → 08 → 16 → 32 → 64 → 28 → 56 → 12 → 24 → 48 → 96 → 92 → 84 → 68 → 36 → 72 → 44 → 88 → 76 → 52 → 04 → 08 → 16 → 32 → 64 → 28… Any number of trailing digits, 1 or 2 or one trillion, falls into a loop. It just takes longer as the number of trailing digits increases.

That’s the tail of the snake. At the other end, the head of the snake, the digits don’t fall into a loop (because of the carries from the lower digits). So, while you can get only 2, 4, 8 and 6 as the final digits of 2^p, you can get any digit but 0 as the first digit of 2^p. Indeed, I conjecture (but can’t prove) that not only will all integers eventually appear as the leading digits of 2^p, but they will do so infinitely often. Think of a number and it will appear as the leading digits of 2^p. Let’s try the numbers 1, 12, 123, 1234, 12345…:

16 = 2^4
128 = 2^7
12379400392853802748... = 2^90
12340799625835686853... = 2^1545
12345257952011458590... = 2^34555
12345695478410965346... = 2^63293
12345673811591269861... = 2^4869721
12345678260232358911... = 2^5194868
12345678999199154389... = 2^62759188

But what about the numbers 9, 98, 987, 986, 98765… as leading digits of 2^p? They don’t appear as quickly:

9007199254740992 = 2^53
98079714615416886934... = 2^186
98726397006685494828... = 2^1548
98768356967522174395... = 2^21257
98765563827287722773... = 2^63296
98765426081858871289... = 2^5194871
98765430693066680199... = 2^11627034
98765432584491513519... = 2^260855656
98765432109571471006... = 2^1641098748

Why do fragments of 123456789 appear much sooner than fragments of 987654321? Well, even though all integers occur infinitely often as leading digits of 2^p, some integers occur more often than others, as it were. The leading digits of 2^p are actually governed by a fascinating mathematical phenomenon known as Benford’s law, which states, for example, that the single first digit, d, will occur with the frequency log10(1 + 1/d). Here are the actual frequencies of 1..9 for all powers of 2 up to 2^101000, compared with the estimate by Benford’s law:

1: 30% of leading digits ↔ 30.1% estimated
2: 17.55% ↔ 17.6%
3: 12.45% ↔ 12.49%
4: 09.65% ↔ 9.69%
5: 07.89% ↔ 7.92%
6: 06.67% ↔ 6.69%
7: 05.77% ↔ 5.79%
8: 05.09% ↔ 5.11%
9: 04.56% ↔ 4.57%

Because (inter alia) 1 appears as the first digit of 2^p far more often than 9 does, the fragments of 123456789 appear faster than the fragments of 987654321. Mutatis mutandis, the same applies in all other bases (apart from bases that are powers of 2, where there’s a single leading digit, 1, 2, 4, 8…, followed by 0s). But although a number like 123456789 occurs much frequently than 987654321 in 2^p expressed in base 10 (and higher), both integers occur infinitely often.

As do all other integers. And because stories can be expressed as numbers, all stories ever (and never) written appear in the powers of 2. Infinitely often. You’ll just have to trim the tail of the story-snake.

Magiciprocal


A021023 Decimal expansion of 1/19.

0, 5, 2, 6, 3, 1, 5, 7, 8, 9, 4, 7, 3, 6, 8, 4, 2, 1, 0, 5, 2, 6, 3, 1, 5, 7, 8, 9, 4, 7, 3, 6, 8, 4, 2, 1, 0, 5, 2, 6, 3, 1, 5, 7, 8, 9, 4, 7, 3, 6, 8, 4, 2, 1, 0, 5, 2, 6, 3, 1, 5, 7, 8, 9, 4, 7, 3, 6, 8, 4, 2, 1, 0, 5, 2, 6, 3, 1, 5, 7, 8, 9, 4, 7, 3, 6, 8, 4, 2, 1, 0, 5, 2, 6, 3, 1, 5, 7, 8 [...] The magic square that uses the decimals of 1/19 is fully magic. — A021023 at the Online Encyclopedia of Integer Sequences

Tri Num Sum

The Sum of ten consecutive Triangular Numbers:

Starting with T0 = 0, in base 10,

The sum of the first 10 triangular numbers from T0 to T9 = 165
The sum of the next 10 triangular numbers from T10 to T19 = 1165
The sum of the next 10 triangular numbers from T20 to T29 = 3165
The sum of the next 10 triangular numbers from T30 to T39 = 6165
The sum of the next 10 triangular numbers from T40 to T49 = 10165
The sum of the next 10 triangular numbers from T50 to T59 = 15165

and so on.

The same pattern is evident in other bases [when summing T0 to Tbase-1 and so on].


• As submitted by Julian Beauchamp, 9v19, to Shyam Sunder Gupta’s “Fascinating Triangular Numbers”.

1nf1nity

Here are the natural numbers or counting numbers:

• 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77... — A000027 at the Online Encyclopedia of Integer Sequences (OEIS)


Here are the prime numbers, or numbers divisible only by themselves and 1:

• 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271... — A000040 at the OEIS


Here are the palindromic prime numbers, or prime numbers that read the same both forwards and backwards:

• 2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929, 10301, 10501, 10601, 11311, 11411, 12421, 12721, 12821, 13331, 13831, 13931, 14341, 14741, 15451, 15551, 16061, 16361, 16561, 16661, 17471, 17971, 18181... — A002385 at the OEIS


Finally, here are the repunit primes, or palindromic primes consisting only of 1s:

• 11, 1111111111111111111, 11111111111111111111111, 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111, 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111... — A004022 at the OEIS (see A004023 for numbers of 1s in each repunit prime)


It’s obvious that there are more counting numbers than primes, isn’t it? Well, no. There are in fact as many primes as counting numbers. And there may be as many palindromic primes as primes. And as many repunit primes as palindromic primes.

The Viscount of Bi-Count

Today is 22/2/22 and, as I hoped on 2/2/22, I can say more about an interesting little palindromic-pattern problem. For each set of integers <= 1[0]1 in base 10, I looked at the count of palindromes exactly divisible by 1, 2, 3, 4, 5, 6, 7, 8 and 9. For example, 2, 4, 6 and 8 are the 4 palindromes divisible by 2 that are less than 11, so countdiv(2) = 4 for pal <= 11; 3, 6 and 9 are the 3 palindromes divisible by 3, so countdiv(3) = 3; and so on. Here are the counts — and some interesting patterns — for palindromes <= (powers-of-10 + 1) up to 1,000,000,000,001:

count for palindromes <= 101 (prime)

countdiv(1) = 19
countdiv(2) = 8
countdiv(3) = 6
countdiv(4) = 4
countdiv(5) = 2
countdiv(6) = 2
countdiv(7) = 2
countdiv(8) = 2
countdiv(9) = 2


count for palindromes <= 1001 = 7 * 11 * 13

countdiv(1) = 109
countdiv(2) = 48
countdiv(3) = 36
countdiv(4) = 24
countdiv(5) = 12
countdiv(6) = 15
countdiv(7) = 15
countdiv(8) = 12
countdiv(9) = 12


count for palindromes <= 10001 = 73 * 137

countdiv(1) = 199
countdiv(2) = 88
countdiv(3) = 66
countdiv(4) = 44
countdiv(5) = 22
countdiv(6) = 28
countdiv(7) = 32
countdiv(8) = 22
countdiv(9) = 22


count for palindromes <= 100001 = 11 * 9091

countdiv(1) = 1099
countdiv(2) = 488
countdiv(3) = 366
countdiv(4) = 244
countdiv(5) = 122
countdiv(6) = 161
countdiv(7) = 163
countdiv(8) = 122
countdiv(9) = 122


count for palindromes <= 1000001 = 101 * 9901

countdiv(1) = 1999
countdiv(2) = 888
countdiv(3) = 666
countdiv(4) = 444
countdiv(5) = 222
countdiv(6) = 294
countdiv(7) = 303
countdiv(8) = 222
countdiv(9) = 222


count for palindromes <= 10000001 = 11 * 909091

countdiv(1) = 10999
countdiv(2) = 4888
countdiv(3) = 3666
countdiv(4) = 2444
countdiv(5) = 1222
countdiv(6) = 1627
countdiv(7) = 1588
countdiv(8) = 1222
countdiv(9) = 1222


count for palindromes <= 100000001 = 17 * 5882353

countdiv(1) = 19999
countdiv(2) = 8888
countdiv(3) = 6666
countdiv(4) = 4444
countdiv(5) = 2222
countdiv(6) = 2960
countdiv(7) = 2878
countdiv(8) = 2222
countdiv(9) = 2222


count for palindromes <= 1000000001 = 7 * 11 * 13 * 19 * 52579

countdiv(1) = 109999
countdiv(2) = 48888
countdiv(3) = 36666
countdiv(4) = 24444
countdiv(5) = 12222
countdiv(6) = 16293
countdiv(7) = 15734
countdiv(8) = 12222
countdiv(9) = 12222


count for palindromes <= 10000000001 = 101 * 3541 * 27961

countdiv(1) = 199999
countdiv(2) = 88888
countdiv(3) = 66666
countdiv(4) = 44444
countdiv(5) = 22222
countdiv(6) = 29626
countdiv(7) = 28783
countdiv(8) = 22222
countdiv(9) = 22222


count for palindromes <= 100000000001 = 11^2 * 23 * 4093 * 8779

countdiv(1) = 1099999
countdiv(2) = 488888
countdiv(3) = 366666
countdiv(4) = 244444
countdiv(5) = 122222
countdiv(6) = 162959
countdiv(7) = 157361
countdiv(8) = 122222
countdiv(9) = 122222


count for palindromes <= 1000000000001 = 73 * 137 * 99990001

countdiv(1) = 1999999
countdiv(2) = 888888
countdiv(3) = 666666
countdiv(4) = 444444
countdiv(5) = 222222
countdiv(6) = 296292
countdiv(7) = 286461
countdiv(8) = 222222
countdiv(9) = 222222


As you can see, the counts for some numbers alternate between rep-digits (all digits the same) and nearly rep-digits. For example, the counts for palindromes exactly divisible by 5, 8 and 9 are alternately all 2s or 1 followed by all 2s. And you get counts of 2, 12, 22, 122, 222, 1222, 2222 in other even bases greater than base 2 when the counts are represented in that base. Here’s base 8:

count for palindromes <= 101 in b8 = 65 in b10 = 5 * 13

countdiv(1) = 17 in b8 (15 in b10)
countdiv(2) = 6
countdiv(3) = 11 in b8 (9)
countdiv(4) = 2
countdiv(5) = 3
countdiv(6) = 4
countdiv(7) = 2


count for palindromes <= 1001 in b8 = 513 in b10 = 3^3 * 19

countdiv(1) = 107 in b8 (71 in b10)
countdiv(2) = 36 in b8 (30)
countdiv(3) = 34 in b8 (28)
countdiv(4) = 12 in b8 (10)
countdiv(5) = 20 in b8 (16)
countdiv(6) = 14 in b8 (12)
countdiv(7) = 12 in b8 (10)


count for palindromes <= 10001 in b8 = 4097 in b10 = 17 * 241

countdiv(1) = 177 in b8 (127 in b10)
countdiv(2) = 66 in b8 (54)
countdiv(3) = 123 in b8 (83)
countdiv(4) = 22 in b8 (18)
countdiv(5) = 34 in b8 (28)
countdiv(6) = 44 in b8 (36)
countdiv(7) = 22 in b8 (18)


count for palindromes <= 100001 in b8 = 32769 in b10 = 3^2 * 11 * 331

countdiv(1) = 1077 in b8 (575 in b10)
countdiv(2) = 366 in b8 (246)
countdiv(3) = 352 in b8 (234)
countdiv(4) = 122 in b8 (82)
countdiv(5) = 164 in b8 (116)
countdiv(6) = 144 in b8 (100)
countdiv(7) = 122 in b8 (82)


count for palindromes <= 1000001 in b8 = 262145 in b10 = 5 * 13 * 37 * 109

countdiv(1) = 1777 in b8 (1023 in b10)
countdiv(2) = 666 in b8 (438)
countdiv(3) = 1251 in b8 (681)
countdiv(4) = 222 in b8 (146)
countdiv(5) = 316 in b8 (206)
countdiv(6) = 444 in b8 (292)
countdiv(7) = 222 in b8 (146)


count for palindromes <= 10000001 in b8 = 2097153 in b10 = 3^2 * 43 * 5419

countdiv(1) = 10777 in b8 (4607 in b10)
countdiv(2) = 3666 in b8 (1974)
countdiv(3) = 3524 in b8 (1876)
countdiv(4) = 1222 in b8 (658)
countdiv(5) = 1645 in b8 (933)
countdiv(6) = 1444 in b8 (804)
countdiv(7) = 1222 in b8 (658)


count for palindromes <= 100000001 in b8 = 16777217 in b10 = 97 * 257 * 673

countdiv(1) = 17777 in b8 (8191 in b10)
countdiv(2) = 6666 in b8 (3510)
countdiv(3) = 12523 in b8 (5459)
countdiv(4) = 2222 in b8 (1170)
countdiv(5) = 3164 in b8 (1652)
countdiv(6) = 4444 in b8 (2340)
countdiv(7) = 2222 in b8 (1170)


The counts for 4-palindromes and 7-palindromes in base 8 run: 1, 12, 22, 122, 222, 1222, 2222…, just like the counts for 5-palindromes, 8-palindromes and 9-palindromes in base 10. Here’s base 14:

count for palindromes <= 101 in b14 = 197 in b10 (prime)

countdiv(1) = 1D in b14 (27 in b10)
countdiv(2) = C in b14 (12)
countdiv(3) = 13 in b14 (17)
countdiv(4) = 6
countdiv(5) = 11 in b14 (15)
countdiv(6) = 8
countdiv(7) = 2
countdiv(8) = 2
countdiv(9) = 5
countdiv(A) = 7
countdiv(B) = 2
countdiv(C) = 4
countdiv(D) = 2


count for palindromes <= 1001 in b14 = 2745 in b10 = 3^2 * 5 * 61

countdiv(1) = 10D in b14 (209 in b10)
countdiv(2) = 6C in b14 (96)
countdiv(3) = 58 in b14 (78)
countdiv(4) = 36 in b14 (48)
countdiv(5) = 3A in b14 (52)
countdiv(6) = 28 in b14 (36)
countdiv(7) = 12 in b14 (16)
countdiv(8) = 19 in b14 (23)
countdiv(9) = 1C in b14 (26)
countdiv(A) = 19 in b14 (23)
countdiv(B) = 14 in b14 (18)
countdiv(C) = 14 in b14 (18)
countdiv(D) = 12 in b14 (16)


count for palindromes <= 10001 in b14 = 38417 in b10 = 41 * 937

countdiv(1) = 1DD in b14 (391 in b10)
countdiv(2) = CC in b14 (180)
countdiv(3) = 147 in b14 (259)
countdiv(4) = 66 in b14 (90)
countdiv(5) = 129 in b14 (233)
countdiv(6) = 88 in b14 (120)
countdiv(7) = 22 in b14 (30)
countdiv(8) = 31 in b14 (43)
countdiv(9) = 66 in b14 (90)
countdiv(A) = 79 in b14 (107)
countdiv(B) = 26 in b14 (34)
countdiv(C) = 44 in b14 (60)
countdiv(D) = 22 in b14 (30)


count for palindromes <= 100001 in b14 = 537825 in b10 = 3 * 5^2 * 71 * 101

countdiv(1) = 10DD in b14 (2939 in b10)
countdiv(2) = 6CC in b14 (1356)
countdiv(3) = 594 in b14 (1110)
countdiv(4) = 366 in b14 (678)
countdiv(5) = 3B2 in b14 (744)
countdiv(6) = 288 in b14 (512)
countdiv(7) = 122 in b14 (226)
countdiv(8) = 1A1 in b14 (337)
countdiv(9) = 1CA in b14 (374)
countdiv(A) = 1A7 in b14 (343)
countdiv(B) = 150 in b14 (266)
countdiv(C) = 144 in b14 (256)
countdiv(D) = 122 in b14 (226)


count for palindromes <= 1000001 in b14 = 7529537 in b10 = 37 * 197 * 1033

countdiv(1) = 1DDD in b14 (5487 in b10)
countdiv(2) = CCC in b14 (2532)
countdiv(3) = 1493 in b14 (3657)
countdiv(4) = 666 in b14 (1266)
countdiv(5) = 12B1 in b14 (3291)
countdiv(6) = 888 in b14 (1688)
countdiv(7) = 222 in b14 (422)
countdiv(8) = 331 in b14 (631)
countdiv(9) = 63A in b14 (1228)
countdiv(A) = 7A7 in b14 (1519)
countdiv(B) = 278 in b14 (498)
countdiv(C) = 444 in b14 (844)
countdiv(D) = 222 in b14 (422)


count for palindromes <= 10000001 in b14 = 105413505 in b10 = 3 * 5 * 7027567

countdiv(1) = 10DDD in b14 (41159 in b10)
countdiv(2) = 6CCC in b14 (18996)
countdiv(3) = 5948 in b14 (15548)
countdiv(4) = 3666 in b14 (9498)
countdiv(5) = 3B2A in b14 (10426)
countdiv(6) = 2888 in b14 (7176)
countdiv(7) = 1222 in b14 (3166)
countdiv(8) = 1A31 in b14 (4747)
countdiv(9) = 1C6D in b14 (5193)
countdiv(A) = 1A79 in b14 (4811)
countdiv(B) = 1513 in b14 (3741)
countdiv(C) = 1444 in b14 (3588)
countdiv(D) = 1222 in b14 (3166)


count for palindromes <= 100000001 in b14 = 1475789057 in b10 = 17 * 5393 * 16097

countdiv(1) = 1DDDD in b14 (76831 in b10)
countdiv(2) = CCCC in b14 (35460)
countdiv(3) = 14947 in b14 (51219)
countdiv(4) = 6666 in b14 (17730)
countdiv(5) = 12B29 in b14 (46097)
countdiv(6) = 8888 in b14 (23640)
countdiv(7) = 2222 in b14 (5910)
countdiv(8) = 3331 in b14 (8863)
countdiv(9) = 631D in b14 (17079)
countdiv(A) = 7A79 in b14 (21275)
countdiv(B) = 278B in b14 (6983)
countdiv(C) = 4444 in b14 (11820)
countdiv(D) = 2222 in b14 (5910)


Now 7-palindromes and D-palindromes (D = 13 in base 10) are following the [1]2222… pattern. What explains it? If you’re good at math, you won’t need telling. But I’m not good at maths, so I’m going to tell myself and other members of the not-good-at-math community what’s going on. Let’s go back to base 10 and the counts for 5-palindromes, that is, palindromes exactly divisible by 5. In base 10, the only integers exactly divisible by 5 have to end in either 5 or 0. But a palindrome can’t end in 0, because then the leading digit would have to be 0 too. Therefore only palindromes ending in 5 are exactly divisible by 5 in base 10. And if the palindromes end in 5, they have to start with 5 too.

Once we know that, we can easily calculate, for a given number of digits, how many 5-palindromes there are. Take 5-palindromes with three digits. If the three-digit 5-palindromes end and start with 5, we have to consider only the middle digit, which can obviously range from 0 to 9: 505, 515, 525, 535, 545, 555, 565, 575, 585 and 595. So there are 10 3-digit 5-palindromes. We add that count to the count for the single one-digit 5-palindrome, 5, and the single two-digit 5-palindrome, 55. So the cumulative count for 5-palindromes < 1001 is: 10 + 1 + 1 = 12.

Now look at four-digit 5-palindromes. They start and end with 5, therefore we have to consider only the middle two digits. And those middle digits have to be identical: 5005, 5115, 5225, 5335, 5445, 5555, 5665, 5775, 5885, 5995. So there are also 10 four-digit 5-palindromes and count of 5-palindromes < 10001 is: 10 + 10 + 1 + 1 = 22.

Now look at five-digit 5-palindromes. Again we have consider only the middle digits, because the first and fifth digits have to be 5. The second digit of a five-digit 5-palindrome has to be the same as the fourth digit: 50005, 51715, 52425, 53135, and so on. And the second and fourth digits can obviously range from 0 to 9. And so can the third and middle digit of the 5-palindromes. But the third digit doesn’t have to be the same as the second and fourth digits: 50005, 50105, 50205, and so on. Therefore the number of five-digit 5-palindromes is 10 * 10 = 100. And the count of 5-palindromes < 100001 is: 100 + 10 + 10 + 1 + 1 = 122.

Now look at six-digit 5-palindromes. The second digit of a six-digit 5-palindrome has to be same as the fifth digit and the third digit has to be the same as the fourth digit. So once you have the second and third digits, you automatically have the fourth and fifth digits: 500005, 523325, 587785, and so on. Clearly, the second and third digits range from 00 to 99 (i.e., 00, 01, 02 … 97, 98, 99), so there must be 100 six-digit 6-palindromes. And the count of 5-palindromes < 1000001 is: 100 + 100 + 10 + 10 + 1 + 1 = 222.

It should be clear, then, that the count of 5-palindromes for an odd number of digits, d, will be always the same as the count of 5-palindromes for the even number of digits d+1. There is 1 one-digit 5-palindrome, namely 5, and 1 two-digit 5-palindrome, namely 55. There are 10 three-digit 5-palindromes, 505 to 595, and 10 four-digit 5-palindromes, 5005 to 5995. Now, the count of 5-palindromes with an odd number of digits, d, will be equal to 10^(d\2), where d\2 = (d-1)/2. And the count for 5-palindromes with the even number of digits d+1 will be the same, 10^(d\2). Therefore the count for both sets of 5-palindromes, d-digit palindromes and (d+1)-digit palindromes, will be 2 * 10^(d\2). And that’s why the cumulative count of 5-palindromes looks the way it does in base 10: 1, 2, 12, 22, 122, 222, 1222, 2222, 12222, 22222…

The same reasoning applies in other even bases greater than base 2. When a palindrome divisible by a particular number has to start and end with the same digit, s, in base b, the middle digits will dictate a count of b^(d\2) for both d-digit s-palindromes and (d+1)-digit s-palindromes. And you’ll get the same cumulative count for s-palindromes in that base: 1, 2, 12, 22, 122, 222, 1222, 2222, 12222, 22222…

Some other patterns in the palindrome-counts can be explained by extending the reasoning given above. For example, if an s-palindrome can begin and end with two possible numbers, you’ll get cumulative counts of 2, 4, 24, 44, 244, 444, 2444, 4444, 24444, 44444 and so on. If the s-palindrome can end with three possible numbers, you’ll get cumulative counts of 3, 6, 36, 66, 366, 666, 3666, 6666, 36666, 66666 and so on.


Post-Performative Post-Scriptum

The discussion above is of very simple mathematics, but that’s the only kind I can cope with. All the same, I’m pleased that I managed to work out why the count of 5-palindromes behaves like that in base 10. So I’ve decided to award myself a title. Remember that the count for 5-palindromes of length d and d+1 is 2 * 10^(d\2), where d is an odd number. And you could say that 2 * 10^(d\2) is a bi-count of 10^(d\2). So I’m calling myself the Viscount of Bi-Count.

To Wit: 2/2

Today is 2/2/22, so here’s a little problem about palindromes. For each set of integers <= 1[0…]1 in base 10, find the cumulative count of palindromes exactly divisible by 1, 2, 3, 4, 5, 6, 7, 8 and 9. For example, 2, 4, 6 and 8 are the 4 palindromes exactly divisible by 2 that are less than 11, so countdiv(2) = 4 for pal <= 11; 3, 6 and 9 are the 3 palindromes exactly divisible by 3, so countdiv(3) = 3; and so on:

count for palindromes <= 11 (prime)

countdiv(1) = 10
countdiv(2) = 4
countdiv(3) = 3
countdiv(4) = 2
countdiv(5) = 1
countdiv(6) = 1
countdiv(7) = 1
countdiv(8) = 1
countdiv(9) = 1


count for palindromes <= 101 (prime)

countdiv(1) = 19
countdiv(2) = 8
countdiv(3) = 6
countdiv(4) = 4
countdiv(5) = 2
countdiv(6) = 2
countdiv(7) = 2
countdiv(8) = 2
countdiv(9) = 2


count for palindromes <= 1001 = 7 * 11 * 13

countdiv(1) = 109
countdiv(2) = 48
countdiv(3) = 36
countdiv(4) = 24
countdiv(5) = 12
countdiv(6) = 15
countdiv(7) = 15
countdiv(8) = 12
countdiv(9) = 12


Some interesting patterns appear as the ceiling-palindromes reach 10001, 100001, 1000001… And one particular pattern doesn’t always disappear when you try the same problem in other bases. I hope to say more on 22/2/22.

Mötley Vüe

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... — A020995 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

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)