Pi and By

Here’s √2 in base 2:

√2 = 1.01101010000010011110... (base=2)

And in base 3:

√2 = 1.10201122122200121221... (base=3)

And in bases 4, 5, 6, 7, 8, 9 and 10:

√2 = 1.12220021321212133303... (b=4)
√2 = 1.20134202041300003420... (b=5)
√2 = 1.22524531420552332143... (b=6)
√2 = 1.26203454521123261061... (b=7)
√2 = 1.32404746317716746220... (b=8)
√2 = 1.36485805578615303608... (b=9)
√2 = 1.41421356237309504880... (b=10)

And here’s π in the same bases:

π = 11.00100100001111110110... (b=2)
π = 10.01021101222201021100... (b=3)
π = 03.02100333122220202011... (b=4)
π = 03.03232214303343241124... (b=5)
π = 03.05033005141512410523... (b=6)
π = 03.06636514320361341102... (b=7)
π = 03.11037552421026430215... (b=8)
π = 03.12418812407442788645... (b=9)
π = 03.14159265358979323846... (b=10)

Mathematicians know that in all standard bases, the digits of √2 and π go on for ever, without falling into any regular pattern. These numbers aren’t merely irrational but transcedental. But are they also normal? That is, in each base b, do the digits 0 to [b-1] occur with the same frequency 1/b? (In general, a sequence of length l will occur in a normal number with frequency 1/(b^l).) In base 2, are there as many 1s as 0s in the digits of √2 and π? In base 3, are there as many 2s as 1s and 0s? And so on.

It’s a simple question, but so far it’s proved impossible to answer. Another question starts very simple but quickly gets very difficult. Here are the answers so far at the Online Encyclopedia of Integer Sequences (OEIS):

2, 572, 8410815, 59609420837337474 – A049364

The sequence is defined as the “Smallest number that is digitally balanced in all bases 2, 3, … n”. In base 2, the number 2 is 10, which has one 1 and one 0. In bases 2 and 3, 572 = 1000111100 and 210012, respectively. 1000111100 has five 1s and five 0s; 210012 has two 2s, two 1s and two 0s. Here are the numbers of A049364 in the necessary bases:

10 (n=2)
1000111100, 210012 (n=572)
100000000101011010111111, 120211022110200, 200011122333 (n=8410815)
11010011110001100111001111010010010001101011100110000010, 101201112000102222102011202221201100, 3103301213033102101223212002, 1000001111222333324244344 (n=59609420837337474)

But what number, a(6), satisfies the definition for bases 2, 3, 4, 5 and 6? According to the notes at the OEIS, a(6) > 5^434. That means finding a(6) is way beyond the power of present-day computers. But I assume a quantum computer could crack it. And maybe someone will come up with a short-cut or even an algorithm that supplies a(b) for any base b. Either way, I think we’ll get there, π and by.

Gyp Cip

Abundance often overwhelms, but restriction reaps riches. That’s true in mathematics and science, where you can often understand the whole better by looking at only a part of it first — restriction reaps riches. Egyptian fractions are one example in maths. In ancient Egypt, you could have any kind of fraction you liked so long as it was a reciprocal like 1/2, 1/3, 1/4 or 1/5 (well, there were two exceptions: 2/3 and 3/4 were also allowed).

So when mathematicians speak of “Egyptian fractions”, they mean those fractions that can be represented as a sum of reciprocals. Egyptian fractions are restricted and that reaps riches. Here’s one example: how many ways can you add n distinct reciprocals to make 1? When n = 1, there’s one way to do it: 1/1. When n = 2, there’s no way to do it, because 1 – 1/2 = 1/2. Therefore the summed reciprocals aren’t distinct: 1/2 + 1/2 = 1. After that, 1 – 1/3 = 2/3, 1 – 1/4 = 3/4, and so on. By the modern meaning of “Egyptian fraction”, there’s no solution for n = 2.

However, when n = 3, there is a way to do it:

• 1/2 + 1/3 + 1/6 = 1

But that’s the only way. When n = 4, things get better:

• 1/2 + 1/4 + 1/6 + 1/12 = 1
• 1/2 + 1/3 + 1/10 + 1/15 = 1
• 1/2 + 1/3 + 1/9 + 1/18 = 1
• 1/2 + 1/4 + 1/5 + 1/20 = 1
• 1/2 + 1/3 + 1/8 + 1/24 = 1
• 1/2 + 1/3 + 1/7 + 1/42 = 1

What about n = 5, n = 6 and so on? You can find the answer at the Online Encyclopedia of Integer Sequences (OEIS), where sequence A006585 is described as “Egyptian fractions: number of solutions to 1 = 1/x1 + … + 1/xn in positive integers x1 < … < xn”. The sequence is one of the shortest and strangest at the OEIS:

• 1, 0, 1, 6, 72, 2320, 245765, 151182379

When n = 1, there’s one solution: 1/1. When n = 2, there’s no solution, as I showed above. When n = 3, there’s one solution again. When n = 4, there are six solutions. And the OEIS tells you how many solutions there are for n = 5, 6, 7, 8. But n >= 9 remains unknown at the time of writing.

To understand the problem, consider the three reciprocals, 1/2, 1/3 and 1/5. How do you sum them? They have different denominators, 2, 3 and 5, so you have to create a new denominator, 30 = 2 * 3 * 5. Then you have to adjust the numerators (the numbers above the fraction bar) so that the new fractions have the same value as the old:

• 1/2 = 15/30 = (2*3*5 / 2) / 30
• 1/3 = 10/30 = (2*3*5 / 3) / 30
• 1/5 = 06/30 = (2*3*5 / 5) / 30
• 15/30 + 10/30 + 06/30 = (15+10+6) / 30 = 31/30 = 1 + 1/30

Those three reciprocals don’t sum to 1. Now try 1/2, 1/3 and 1/6:

• 1/2 = 18/36 = (2*3*6 / 2) / 36
• 1/3 = 12/36 = (2*3*6 / 3) / 36
• 1/6 = 06/36 = (2*3*6 / 6) / 36
• 18/36 + 12/36 + 06/36 = (18+12+6) / 36 = 36/36 = 1

So when n = 3, the problem consists of finding three reciprocals, 1/a, 1/b and 1/c, such that for a, b, and c:

• a*b*c = a*b + a*c + b*c

There is only one solution: a = 2, b = 3 and c = 6. When n = 4, the problem consists of finding four reciprocals, 1/a, 1/b, 1/c and 1/d, such that for a, b, c and d:

• a*b*c*d = a*b*c + a*b*d + a*c*d + b*c*d

For example:

• 2*4*6*12 = 576
• 2*4*6 + 2*4*12 + 2*6*12 + 4*6*12 = 48 + 96 + 144 + 288 = 576
• 2*4*6*12 = 2*4*6 + 2*4*12 + 2*6*12 + 4*6*12 = 576

Therefore:

• 1/2 + 1/4 + 1/6 + 1/12 = 1

When n = 5, the problem consists of finding five reciprocals, 1/a, 1/b, 1/c, 1/d and 1/e, such that for a, b, c, d and e:

• a*b*c*d*e = a*b*c*d + a*b*c*e + a*b*d*e + a*c*d*e + b*c*d*e

There are 72 solutions and here they are:

• 1/2 + 1/4 + 1/10 + 1/12 + 1/15 = 1 (#1)
• 1/2 + 1/4 + 1/9 + 1/12 + 1/18 = 1 (#2)
• 1/2 + 1/5 + 1/6 + 1/12 + 1/20 = 1 (#3)
• 1/3 + 1/4 + 1/5 + 1/6 + 1/20 = 1 (#4)
• 1/2 + 1/4 + 1/8 + 1/12 + 1/24 = 1 (#5)
• 1/2 + 1/3 + 1/12 + 1/21 + 1/28 = 1 (#6)
• 1/2 + 1/4 + 1/6 + 1/21 + 1/28 = 1 (#7)
• 1/2 + 1/4 + 1/7 + 1/14 + 1/28 = 1 (#8)
• 1/2 + 1/3 + 1/12 + 1/20 + 1/30 = 1 (#9)
• 1/2 + 1/4 + 1/6 + 1/20 + 1/30 = 1 (#10)
• 1/2 + 1/5 + 1/6 + 1/10 + 1/30 = 1 (#11)
• 1/2 + 1/3 + 1/11 + 1/22 + 1/33 = 1 (#12)
• 1/2 + 1/3 + 1/14 + 1/15 + 1/35 = 1 (#13)
• 1/2 + 1/3 + 1/12 + 1/18 + 1/36 = 1 (#14)
• 1/2 + 1/4 + 1/6 + 1/18 + 1/36 = 1 (#15)
• 1/2 + 1/3 + 1/10 + 1/24 + 1/40 = 1 (#16)
• 1/2 + 1/4 + 1/8 + 1/10 + 1/40 = 1 (#17)
• 1/2 + 1/4 + 1/7 + 1/12 + 1/42 = 1 (#18)
• 1/2 + 1/3 + 1/9 + 1/30 + 1/45 = 1 (#19)
• 1/2 + 1/4 + 1/5 + 1/36 + 1/45 = 1 (#20)
• 1/2 + 1/5 + 1/6 + 1/9 + 1/45 = 1 (#21)
• 1/2 + 1/3 + 1/12 + 1/16 + 1/48 = 1 (#22)
• 1/2 + 1/4 + 1/6 + 1/16 + 1/48 = 1 (#23)
• 1/2 + 1/3 + 1/9 + 1/27 + 1/54 = 1 (#24)
• 1/2 + 1/3 + 1/8 + 1/42 + 1/56 = 1 (#25)
• 1/2 + 1/3 + 1/8 + 1/40 + 1/60 = 1 (#26)
• 1/2 + 1/3 + 1/10 + 1/20 + 1/60 = 1 (#27)
• 1/2 + 1/3 + 1/12 + 1/15 + 1/60 = 1 (#28)
• 1/2 + 1/4 + 1/5 + 1/30 + 1/60 = 1 (#29)
• 1/2 + 1/4 + 1/6 + 1/15 + 1/60 = 1 (#30)
• 1/2 + 1/4 + 1/5 + 1/28 + 1/70 = 1 (#31)
• 1/2 + 1/3 + 1/8 + 1/36 + 1/72 = 1 (#32)
• 1/2 + 1/3 + 1/9 + 1/24 + 1/72 = 1 (#33)
• 1/2 + 1/4 + 1/8 + 1/9 + 1/72 = 1 (#34)
• 1/2 + 1/3 + 1/12 + 1/14 + 1/84 = 1 (#35)
• 1/2 + 1/4 + 1/6 + 1/14 + 1/84 = 1 (#36)
• 1/2 + 1/3 + 1/8 + 1/33 + 1/88 = 1 (#37)
• 1/2 + 1/3 + 1/10 + 1/18 + 1/90 = 1 (#38)
• 1/2 + 1/3 + 1/7 + 1/78 + 1/91 = 1 (#39)
• 1/2 + 1/3 + 1/8 + 1/32 + 1/96 = 1 (#40)
• 1/2 + 1/3 + 1/9 + 1/22 + 1/99 = 1 (#41)
• 1/2 + 1/4 + 1/5 + 1/25 + 1/100 = 1 (#42)
• 1/2 + 1/3 + 1/7 + 1/70 + 1/105 = 1 (#43)
• 1/2 + 1/3 + 1/11 + 1/15 + 1/110 = 1 (#44)
• 1/2 + 1/3 + 1/8 + 1/30 + 1/120 = 1 (#45)
• 1/2 + 1/4 + 1/5 + 1/24 + 1/120 = 1 (#46)
• 1/2 + 1/5 + 1/6 + 1/8 + 1/120 = 1 (#47)
• 1/2 + 1/3 + 1/7 + 1/63 + 1/126 = 1 (#48)
• 1/2 + 1/3 + 1/9 + 1/21 + 1/126 = 1 (#49)
• 1/2 + 1/3 + 1/7 + 1/60 + 1/140 = 1 (#50)
• 1/2 + 1/4 + 1/7 + 1/10 + 1/140 = 1 (#51)
• 1/2 + 1/3 + 1/12 + 1/13 + 1/156 = 1 (#52)
• 1/2 + 1/4 + 1/6 + 1/13 + 1/156 = 1 (#53)
• 1/2 + 1/3 + 1/7 + 1/56 + 1/168 = 1 (#54)
• 1/2 + 1/3 + 1/8 + 1/28 + 1/168 = 1 (#55)
• 1/2 + 1/3 + 1/9 + 1/20 + 1/180 = 1 (#56)
• 1/2 + 1/3 + 1/7 + 1/54 + 1/189 = 1 (#57)
• 1/2 + 1/3 + 1/8 + 1/27 + 1/216 = 1 (#58)
• 1/2 + 1/4 + 1/5 + 1/22 + 1/220 = 1 (#59)
• 1/2 + 1/3 + 1/11 + 1/14 + 1/231 = 1 (#60)
• 1/2 + 1/3 + 1/7 + 1/51 + 1/238 = 1 (#61)
• 1/2 + 1/3 + 1/10 + 1/16 + 1/240 = 1 (#62)
• 1/2 + 1/3 + 1/7 + 1/49 + 1/294 = 1 (#63)
• 1/2 + 1/3 + 1/8 + 1/26 + 1/312 = 1 (#64)
• 1/2 + 1/3 + 1/7 + 1/48 + 1/336 = 1 (#65)
• 1/2 + 1/3 + 1/9 + 1/19 + 1/342 = 1 (#66)
• 1/2 + 1/4 + 1/5 + 1/21 + 1/420 = 1 (#67)
• 1/2 + 1/3 + 1/7 + 1/46 + 1/483 = 1 (#68)
• 1/2 + 1/3 + 1/8 + 1/25 + 1/600 = 1 (#69)
• 1/2 + 1/3 + 1/7 + 1/45 + 1/630 = 1 (#70)
• 1/2 + 1/3 + 1/7 + 1/44 + 1/924 = 1 (#71)
• 1/2 + 1/3 + 1/7 + 1/43 + 1/1806 = 1 (#72)

All the sums start with 1/2 except for one:

• 1/2 + 1/5 + 1/6 + 1/12 + 1/20 = 1 (#3)
• 1/3 + 1/4 + 1/5 + 1/6 + 1/20 = 1 (#4)

Here are the solutions in another format:

(2,4,10,12,15), (2,4,9,12,18), (2,5,6,12,20), (3,4,5,6,20), (2,4,8,12,24), (2,3,12,21,28), (2,4,6,21,28), (2,4,7,14,28), (2,3,12,20,30), (2,4,6,20,30), (2,5,6,10,30), (2,3,11,22,33), (2,3,14,15,35), (2,3,12,18,36), (2,4,6,18,36), (2,3,10,24,40), (2,4,8,10,40), (2,4,7,12,42), (2,3,9,30,45), (2,4,5,36,45), (2,5,6,9,45), (2,3,12,16,48), (2,4,6,16,48), (2,3,9,27,54), (2,3,8,42,56), (2,3,8,40,60), (2,3,10,20,60), (2,3,12,15,60), (2,4,5,30,60), (2,4,6,15,60), (2,4,5,28,70), (2,3,8,36,72), (2,3,9,24,72), (2,4,8,9,72), (2,3,12,14,84), (2,4,6,14,84), (2,3,8,33,88), (2,3,10,18,90), (2,3,7,78,91), (2,3,8,32,96), (2,3,9,22,99), (2,4,5,25,100), (2,3,7,70,105), (2,3,11,15,110), (2,3,8,30,120), (2,4,5,24,120), (2,5,6,8,120), (2,3,7,63,126), (2,3,9,21,126), (2,3,7,60,140), (2,4,7,10,140), (2,3,12,13,156), (2,4,6,13,156), (2,3,7,56,168), (2,3,8,28,168), (2,3,9,20,180), (2,3,7,54,189), (2,3,8,27,216), (2,4,5,22,220), (2,3,11,14,231), (2,3,7,51,238), (2,3,10,16,240), (2,3,7,49,294), (2,3,8,26,312), (2,3,7,48,336), (2,3,9,19,342), (2,4,5,21,420), (2,3,7,46,483), (2,3,8,25,600), (2,3,7,45,630), (2,3,7,44,924), (2,3,7,43,1806)


Note

Strictly speaking, there are two solutions for n = 2 in genuine Egyptian fractions, because 1/3 + 2/3 = 1 and 1/4 + 3/4 = 1. As noted above, 2/3 and 3/4 were permitted as fractions in ancient Egypt.

Block’n’Role

How low can you go? When it comes to standard bases in mathematics, you can’t go lower than 2. But base 2, or binary, is unsurpassable for simplicity and beauty. With only two digits, 1 and 0, you can capture any integer you like:

• 0, 1, 2, 3, 4, 5... -> 0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, 10000, 10001, 10010, 10011, 10100, 10101, 10110, 10111, 11000, 11001, 11010, 11011, 11100, 11101, 11110, 11111, 100000, 100001, 100010, 100011, 100100, 100101, 100110, 100111, 101000, 101001, 101010, 101011, 101100, 101101, 101110, 101111, 110000, 110001, 110010, 110011, 110100, 110101, 110110, 110111, 111000, 111001, 111010, 111011, 111100, 111101, 111110, 111111...


Here are a few famous decimal numbers in binary:

• 23 = 10111 in binary
• 666 = 1010011010 in binary
• 1492 = 10111010100 in binary
• 2001 = 11111010001 in binary

As you can see, there’s a problem with binary for human beings. It takes up a lot of space and doesn’t look very distinctive. But that’s easy to solve by converting binary into octal (base 8) or hexadecimal (base 16). One digit in octal is worth three digits in binary and one digit in hexadecimal is worth four digits in binary. So the conversion back and forth is very easy:

• 23 = 10111 → (010,111) → 27 in octal
• 23 = 10111 → (0001,0111) → 17 in hexadecimal
• 666 = 1010011010 → (001,010,011,010) → 1232 in octal
• 666 = 1010011010 → (0010,1001,1010) → 29A in hexademical
• 1492 = 10111010100 → (010,111,010,100) → 2724 in octal
• 1492 = 10111010100 → (0101,1101,0100) → 5D4 in hexademical
• 2001 = 11111010001 → (011,111,010,001) → 3721 in octal
• 2001 = 11111010001 → (0111,1101,0001) → 7D1 in hexademical

But there’s another way to compress a binary number: count the lengths of the runs of 1 and 0. For example, 23 = 10111 and 10111 → one 1, one 0, three 1s → (1,1,3) → 113. That’s not much of a compression, but it usually gets better as the numbers get bigger:

• 2001 = 11111010001 → (5,1,1,3,1) → 51131

From the compressed form you can easily re-create the binary number:

• 51131 → (5,1,1,3,1) → (11111,0,1,000,1) → 11111010001

This block-compression doesn’t work with any other standard base. For example, the compressed form (1,2) in ternary, or base 3, is ambiguous:

• (1,2) → (1,00) → 100 in base 3 = 09 in decimal
• (1,2) → (1,22) → 122 in base 3 = 17 in decimal
• (1,2) → (2,00) → 200 in base 3 = 18 in decimal
• (1,2) → (2,11) → 211 in base 3 = 22 in decimal

The higher the base, the bigger the ambiguity. But ambiguity exists with binary block-compressions too. Look at 51131 ← 11111010001 = 2001 in decimal. Out of context, 51131 is infinitely ambiguous. It could represent a number in any base higher than 5:

• 51131 in base 06 = 006751 in base 10
• 51131 in base 07 = 012419 in base 10
• 51131 in base 08 = 021081 in base 10
• 51131 in base 09 = 033643 in base 10
• 51131 in base 10 = 051131 in base 10
• 51131 in base 11 = 074691 in base 10
• 51131 in base 12 = 105589 in base 10
• 51131 in base 13 = 145211 in base 10
• 51131 in base 14 = 195063 in base 10
• 51131 in base 15 = 256771 in base 10
• 51131 in base 16 = 332081 in base 10
• 51131 in base 17 = 422859 in base 10
• 51131 in base 18 = 531091 in base 10
• 51131 in base 19 = 658883 in base 10
• 51131 in base 20 = 808461 in base 10...

But that ambiguity raises an interesting question. Does the binary block-compression of n ever match the digits of n in another base? Yes, it does:

• 23 = 10111 in base 2 → (1,1,3) and 113 in base 4 = 10111 in base 2 = 23 in base 10

113 in base 4 = 1*4^2 + 1*4 + 3*4^0 = 16+4+3 = 23. You could call this “Block’n’Role”, because the blocks of 1 and 0 allow a binary number to retain its identity but take on a different role, that is, represent a number in a different base. Here’s a list of binary block-numbers that match the digits of n in another base:

• 10111 → (1,1,3) = 113 in base 4 (n=23)
• 11001 → (2,2,1) = 221 in base 3 (n=25)
• 101100 → (1,1,2,2) = 1122 in base 3 (n=44)
• 111001 → (3,2,1) = 321 in base 4 (n=57)
• 1011111 → (1,1,5) = 115 in base 9 (n=95)
• 1100001 → (2,4,1) = 241 in base 6 (n=97)
• 11100001 → (3,4,1) = 341 in base 8 (n=225)
• 100110000 → (1,2,2,4) = 1224 in base 6 (n=304)
• 101110111 → (1,1,3,1,3) = 11313 in base 4 (n=375)
• 111111001 → (6,2,1) = 621 in base 9 (n=505)
• 1110010111 → (3,2,1,1,3) = 32113 in base 4 (n=919)
• 10000011111 → (1,5,5) = 155 in base 30 (n=1055)
• 11111100001 → (6,4,1) = 641 in base 18 (n=2017)
• 1011101110111 → (1,1,3,1,3,1,3) = 1131313 in base 4 (n=6007)
• 11100101110111 → (3,2,1,1,3,1,3) = 3211313 in base 4 (n=14711)
• 10111011101110111 → (1,1,3,1,3,1,3,1,3) = 113131313 in base 4 (n=96119)
• 111001011101110111 → (3,2,1,1,3,1,3,1,3) = 321131313 in base 4 (n=235383)
• 100000111111111000001 → (1,5,9,5,1) = 15951 in base 31 (n=1081281)
• 101110111011101110111 → 11313131313 in b4 = 1537911
• 1110010111011101110111 → 32113131313 in b4 = 3766135
• 1011101110111011101110111 → 1131313131313 in b4 = 24606583
• 11100101110111011101110111 → 3211313131313 in b4 = 60258167
• 10111011101110111011101110111 → 113131313131313 in b4 = 393705335
• 111001011101110111011101110111 → 321131313131313 in b4 = 964130679

The list of block-nums is incomplete, because I’ve skipped some trivial examples where, for all powers 2^p > 2^2, the block-num is “1P” in base b = (2^p – p). For example:

• 2^3 = 08 = 1000 in base 2 → (1,3) and 13 in base 5 = 8, where 5 = 2^3-3 = 8-3
• 2^4 = 16 = 10000 in base 2 → (1,4) and 14 in base 12 = 16, where 12 = 2^4-4 = 16-4
• 2^5 = 32 = 100000 in base 2 → (1,5) and 15 in base 27 = 32, where 27 = 2^5-5 = 32-5
• 2^6 = 64 = 1000000 in base 2 → (1,6) and 16 in base 58 = 64, where 58 = 2^6-6 = 64-6

And note that the block-num matches in base 4 continue for ever, because the pairs 113… and 321… generate their successors using simple formulae in base 4:

• 113... * 100 + 13
• 321... * 100 + 13

For example, 113 and 321 are the first pair of matches:

• 10111 → (1,1,3) = 113 in base 4 (n=23)
• 111001 → (3,2,1) = 321 in base 4 (n=57)

In base 4, 113 * 100 + 13 = 11313 and 321 * 100 + 13 = 32113:

• 101110111 → (1,1,3,1,3) = 11313 in base 4 (n=375)
• 1110010111 → (3,2,1,1,3) = 32113 in base 4 (n=919)

Next, 11313 * 100 + 13 = 1131313 and 32113 * 100 + 13 = 3211313:

• 1011101110111 → (1,1,3,1,3,1,3) = 1131313 in base 4 (n=6007)
• 11100101110111 → (3,2,1,1,3,1,3) = 3211313 in base 4 (n=14711)

And so on.

WhirlpUlam

Stanislaw Ulam (pronounced OO-lam) was an American mathematician who was doodling one day in 1963 and created what is now called the Ulam spiral. It’s a spiral of integers on a square grid with the prime squares filled in and the composite squares left empty. At the beginning it looks like this (the blue square is the integer 1, with 2 to the east, 3 to the north-east, 4 to the north, 5 to the north-west, 6 to the west, and so on):

Ulam spiral


And here’s an Ulam spiral with more integers:

Ulam spiral at higher resolution


The primes aren’t scattered at random over the spiral: they often fall into lines that are related to what are called polynomial functions, such as n2 + n + 1. To understand polynomial functions better, let’s look at how the Ulam spiral is made. Here is a text version with the primes underlined:


Here’s an animated version:


Here’s the true spiral again with 1 marked as a blue square:

Ulam spiral centred on 1


What happens when you try other numbers at the centre? Here’s 2 at the centre as a purple square, because it’s prime:

Ulam spiral centred on 2


And 3 at the centre, also purple because it’s also prime:

Ulam spiral centred on 3


And 4 at the centre, blue again because 4 = 2^2:

Ulam spiral centred on 4


And 5 at the centre, prime and purple:

Ulam spiral centred on 5


Each time the central number changes, the spiral shifts fractionally. Here’s an animation of the central number shifting from 1 to 41. If you watch, you’ll see patterns remaining stable, then breaking up as the numbers shift towards the center and disappear (the central number is purple if prime, blue if composite):

Ulam whirlpool, or WhirlpUlam


I think the animation looks like a whirlpool or whirlpUlam (prounced whirlpool-am), as numbers spiral towards the centre and disappear. You can see the whirlpUlam more clearly here:
An animated Ulam Spiral pausing at n=11, 17, 41


WhirlpUlam again


Note that something interesting happens when the central number is 41. The spiral is bisected by a long line of prime squares, like this:

Ulam spiral centred on 41


The line is actually a visual representation of something David Wells wrote about in The Penguin Dictionary of Curious and Interesting Numbers (1986):

Euler discovered the excellent and famous formula x2 + x + 41, which gives prime values for x = 0 to 39.

Here are the primes generated by the formula:

41, 43, 47, 53, 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251, 281, 313, 347, 383, 421, 461, 503, 547, 593, 641, 691, 743, 797, 853, 911, 971, 1033, 1097, 1163, 1231, 1301, 1373, 1447, 1523, 1601

You’ll see other lines appear and disappear as the whirlpUlam whirls:

Ulam spiral centred on 17


Primes in line: 17, 19, 23, 29, 37, 47, 59, 73, 89, 107, 127, 149, 173, 199, 227, 257 (n=0..15)


Ulam spiral centred on 59


Primes in line: 59, 67, 83, 107, 139, 179, 227, 283, 347, 419, 499, 587, 683, 787 (n=0..13)


Ulam spiral centred on 163


Primes in line: 163, 167, 179, 199, 227, 263, 307, 359, 419, 487, 563, 647, 739, 839, 947, 1063, 1187, 1319, 1459, 1607 (n=0..19)


Ulam spiral centred on 233


Primes in line: 233, 241, 257, 281, 313, 353, 401, 457, 521, 593, 673, 761, 857 ((n=0..12)


Ulam spiral centred on 653


Primes in line: 653, 661, 677, 701, 733, 773, 821, 877, 941, 1013, 1093, 1181, 1277, 1381, 1493, 1613, 1741, 1877 (n=0..17)


Ulam spiral centred on 409,333


Primes in line: 409,333, 409337, 409349, 409369, 409397, 409433, 409477, 409529, 409589, 409657, 409733, 409817, 409909, 410009, 410117, 410233 (n=0..15)


Some bisect the centre, some don’t, because you could say that the Ulam spiral has six diagonals, two that bisect the centre (top-left-to-bottom-right and bottom-left-to-top-right) and four that don’t. You could also call them spokes:


If you look at the integers in the spokes, you can see that they’re generated by polynomial functions in which c stands for the central number:

North-west spoke: 1, 5, 17, 37, 65, 101, 145, 197, 257, 325, 401, 485, 577, 677, 785, 901, 1025, 1157, 1297, 1445, 1601, 1765, 1937, 2117, 2305, 2501, 2705, 2917... = c + (2n)^2


South-east spoke: 1, 9, 25, 49, 81, 121, 169, 225, 289, 361, 441, 529, 625, 729, 841, 961, 1089, 1225, 1369, 1521, 1681, 1849, 2025, 2209, 2401, 2601, 2809, 3025, 3249, 3481, 3721, 3969, 4225, 4489, 4761, 5041, 5329, 5625... = c+(2n+1)^2-1


NW-SE diagonal: 1, 5, 9, 17, 25, 37, 49, 65, 81, 101, 121, 145, 169, 197, 225, 257, 289, 325, 361, 401, 441, 485, 529, 577, 625, 677, 729, 785, 841, 901, 961, 1025, 1089, 1157, 1225, 1297, 1369, 1445, 1521, 1601, 1681 = c + n^2 + 1 - (n mod 2)


North-east spoke: 1, 3, 13, 31, 57, 91, 133, 183, 241, 307, 381, 463, 553, 651, 757, 871, 993, 1123, 1261, 1407, 1561, 1723, 1893, 2071... = c + (n+1)^2 - n - 1


South-west spoke: 1, 7, 21, 43, 73, 111, 157, 211, 273, 343, 421, 507, 601, 703, 813, 931, 1057, 1191, 1333, 1483, 1641, 1807, 1981, 2163... = c + (2n)^2 + 2n


SW-NE diagonal: 1, 3, 7, 13, 21, 31, 43, 57, 73, 91, 111, 133, 157, 183, 211, 241, 273, 307, 343, 381, 421, 463, 507, 553, 601, 651, 703, 757, 813, 871, 931, 993, 1057, 1123, 1191, 1261, 1333, 1407, 1483, 1561, 1641... = c + n^2 + n



Elsewhere other-engageable:

All posts interrogating issues around the Ulam spiral

Zequality Now

Here are the numbers one to eight in base 2:

1, 10, 11, 100, 101, 110, 111, 1000…

Now see what happens when you count the zeroes:


1, 10[1], 11, 10[2]0[3], 10[4]1, 110[5], 111, 10[6]0[7]0[8]...

In base 2, the numbers one to eight contain exactly eight zeroes, that is, zerocount(1..8,b=2) = 8. But it doesn’t work out so exactly in base 3:


1, 2, 10[1], 11, 12, 20[2], 21, 22, 10[3]0[4], 10[5]1, 10[6]2, 110[7], 111, 112, 120[8], 121, 122, 20[9]0[10], 20[11]1, 20[12]2, 210[13], 211, 212, 220[14], 221, 222, 10[15]0[16]0[17], 10[18]0[19]1, 10[20]0[21]2, 10[22]10[23], 10[24]11, 10[25]12, 10[26]20[27], 10[28]21, 10[29]22, 110[30]0[31], 110[32]1, 110[33]2, 1110[34], 1111, 1112, 1120[35], 1121, 1122, 120[36]0[37], 120[38]1, 120[39]2, 1210[40], 1211, 1212, 1220[41], 1221, 1222, 20[42]0[43]0[44], 20[45]0[46]1, 20[47]0[48]2, 20[49]10[50], 20[51]11, 20[52]12, 20[53]20[54], 20[55]21, 20[56]22, 210[57]0[58], 210[59]1, 210[60]2, 2110[61], 2111, 2112, 2120[62], 2121, 2122, 220[63]0[64], 220[65]1, 220[66]2, 2210[67], 2211, 2212, 2220[68], 2221, 2222, 10[69]0[70]0[71]0[72], 10[73]0[74]0[75]1, 10[76]0[77]0[78]2, 10[79]0[80]10[81], 10[82]0[83]11, 10[84]0[85]12, 10[86]0[87]20[88]...

In base 3, 10020 = 87 and zerocount(1..87,b=3) = 88. And what about base 4? zerocount(1..1068,b=4) = 1069 (n=100,230 in base 4). After that, zerocount(1..16022,b=5) = 16023 (n=1,003,043 in base 5) and zerocount(1..284704,b=6) = 284,705 (n=10,034,024 in base 6).

The numbers are getting bigger fast and it’s becoming increasingly impractible to count the zeroes individually. What you need is an algorithm that will take any given n and work out how many zeroes are required to write the numbers 1 to n. The simplest way to do this is to work out how many times 0 has appeared in each position of the number. The 1s position is easy: you simply divide the number by the base and discard the remainder. For example, in base 10, take the number 25. The 0 must have appeared in the 1s position twice, for 10 and 20, so zerocount(1..25) = 25 \ 10 = 2. In 2017, the 0 must have appeared in the 1s position 201 times = 2017 \ 10. And so on.

It gets a little trickier for the higher positions, the 10s, 100s, 1000s and so on, but the same basic principle applies. And so you can easily create an algorithm that takes a number, n, and produces zerocount(1..n) in a particular base. With this algorithm, you can quickly find zerocount(1..n) >= n in higher bases:


zerocount(1..1000,b=2) = 1,000 (n=8)*
zerocount(1..10020,b=3) = 10,021 (n=87)
zerocount(1..100230,b=4) = 100,231 (n=1,068)
zerocount(1..1003042,b=5) = 1,003,043 (n=16,022)
zerocount(1..10034024,b=6) = 10,034,025 (n=284,704)
zerocount(1..100405550,b=7) = 100,405,551 (n=5,834,024)
zerocount(1..1004500236,b=8) = 1,004,500,237 (n=135,430,302)
zerocount(1..10050705366,b=9) = 10,050,705,367 (n=3,511,116,537)
zerocount(1..100559404366,b=10) = 100,559,404,367
zerocount(1..1006083A68919,b=11) = 1,006,083,A68,919 (n=3,152,738,985,031)*
zerocount(1..10066AA1430568,b=12) = 10,066,AA1,430,569 (n=107,400,330,425,888)
zerocount(1..1007098A8719B81,b=13) = 100,709,8A8,719,B81 (n=3,950,024,143,546,664)*
zerocount(1..10077C39805D81C7,b=14) = 1,007,7C3,980,5D8,1C8 (n=155,996,847,068,247,395)
zerocount(1..10080B0034AA5D16D,b=15) = 10,080,B00,34A,A5D,171 (n=6,584,073,072,068,125,453)
zerocount(1..10088DBE29597A6C77,b=16) = 100,88D,BE2,959,7A6,C77 (n=295,764,262,988,176,583,799)*
zerocount(1..10090C5309AG72CBB3F,b=17) = 1,009,0C5,309,AG7,2CB,B3G (n=14,088,968,131,538,370,019,982)
zerocount(1..10099F39070FC73C1G73,b=18) = 10,099,F39,070,FC7,3C1,G75 (n=709,394,716,006,812,244,474,473)
zerocount(1..100A0DC1258614CA334EB,b=19) = 100,A0D,C12,586,14C,A33,4EC (n=37,644,984,315,968,494,382,106,708)
zerocount(1..100AAGDEEB536IBHE87006,b=20) = 1,00A,AGD,EEB,536,IBH,E87,008 (n=2,099,915,447,874,594,268,014,136,006)

And you can also easily find the zequal numbers, that is, the numbers n for which, in some base, zerocount(1..n) exactly equals n:


zerocount(1..1000,b=2) = 1,000 (n=8)
zerocount(1..1006083A68919,b=11) = 1,006,083,A68,919 (n=3,152,738,985,031)
zerocount(1..1007098A8719B81,b=13) = 100,709,8A8,719,B81 (n=3,950,024,143,546,664)
zerocount(1..10088DBE29597A6C77,b=16) = 100,88D,BE2,959,7A6,C77 (n=295,764,262,988,176,583,799)
zerocount(1..100CCJFFAD4MI409MI0798CJB3,b=24) = 10,0CC,JFF,AD4,MI4,09M,I07,98C,JB3 (n=32,038,681,563,209,056,709,427,351,442,469,835)
zerocount(1..100DDL38CIO4P9K0AJ7HK74EMI7L,b=26) = 1,00D,DL3,8CI,O4P,9K0,AJ7,HK7,4EM,I7L (n=160,182,333,966,853,031,081,693,091,544,779,177,187)
zerocount(1..100EEMHG6OE8EQKO0BF17LCCIA7GPE,b=28) = 100,EEM,HG6,OE8,EQK,O0B,F17,LCC,IA7,GPE (n=928,688,890,453,756,699,447,122,559,347,771,300,777,482)
zerocount(1..100F0K7MQO6K9R1S616IEEL2JRI73PF,b=29) = 1,00F,0K7,MQO,6K9,R1S,616,IEE,L2J,RI7,3PF (n=74,508,769,042,363,852,559,476,397,161,338,769,391,145,562)
zerocount(1..100G0LIL0OQLF2O0KIFTK1Q4DC24HL7BR,b=31) = 100,G0L,IL0,OQL,F2O,0KI,FTK,1Q4,DC2,4HL,7BR (n=529,428,987,529,739,460,369,842,168,744,635,422,842,585,510,266)
zerocount(1..100H0MUTQU3A0I5005WL2PD7T1ASW7IV7NE,b=33) = 10,0H0,MUT,QU3,A0I,500,5WL,2PD,7T1,ASW,7IV,7NE (n=4,262,649,311,868,962,034,947,877,223,846,561,239,424,294,726,563,632)
zerocount(1..100HHR387RQHK9OP6EDBJEUDAK35N7MN96LB,b=34) = 100,HHR,387,RQH,K9O,P6E,DBJ,EUD,AK3,5N7,MN9,6LB (n=399,903,937,958,473,433,782,862,763,628,747,974,628,490,691,628,136,485)
zerocount(1..100IISLI0CYX2893G9E8T4I7JHKTV41U0BKRHT,b=36) = 10,0II,SLI,0CY,X28,93G,9E8,T4I,7JH,KTV,41U,0BK,RHT (n=3,831,465,379,323,568,772,890,827,210,355,149,992,132,716,389,119,437,755,185)
zerocount(1..100LLX383BPWE[40]ZL0G1M[40]1OX[39]67KOPUD5C[40]RGQ5S6W9[36],b=42) = 10,0LL,X38,3BP,WE[40],ZL0,G1M,[40]1O,X[39]6,7KO,PUD,5C[40],RGQ,5S6,W9[36] (n=6,307,330,799,917,244,669,565,360,008,241,590,852,337,124,982,231,464,556,869,653,913,711,854)
zerocount(1..100MMYPJ[38]14KDV[37]OG[39]4[42]X75BE[39][39]4[43]CK[39]K36H[41]M[37][43]5HIWNJ,b=44) = 1,00M,MYP,J[38]1,4KD,V[37]O,G[39]4,[42]X7,5BE,[39][39]4,[43]CK,[39]K3,6H[41],M[37][43],5HI,WNJ (n=90,257,901,046,284,988,692,468,444,260,851,559,856,553,889,199,511,017,124,021,440,877,333,751,943)
zerocount(1..100NN[36]3813[38][37]16F6MWV[41]UBNF5FQ48N0JRN[40]E76ZOHUNX2[42]3[43],b=46) = 100,NN[36],381,3[38][37],16F,6MW,V[41]U,BNF,5FQ,48N,0JR,N[40]E,76Z,OHU,NX2,[42]3[43] (n=1,411,636,908,622,223,745,851,790,772,948,051,467,006,489,552,352,013,745,000,752,115,904,961,213,172,605)
zerocount(1..100O0WBZO9PU6O29TM8Y0QE3I[37][39]A7E4YN[44][42]70[44]I[46]Z[45][37]Q2WYI6,b=47) = 1,00O,0WB,ZO9,PU6,O29,TM8,Y0Q,E3I,[37][39]A,7E4,YN[44],[42]70,[44]I[46],Z[45][37],Q2W,YI6 (n=182,304,598,281,321,725,937,412,348,242,305,189,665,300,088,639,063,301,010,710,450,793,661,266,208,306,996)
zerocount(1..100PP[39]37[49]NIYMN[43]YFE[44]TDTJ00EAEIP0BIDFAK[46][36]V6V[45]M[42]1M[46]SSZ[40],b=50) = 1,00P,P[39]3,7[49]N,IYM,N[43]Y,FE[44],TDT,J00,EAE,IP0,BID,FAK,[46][36]V,6V[45],M[42]1,M[46]S,SZ[40] (n=444,179,859,561,011,965,929,496,863,186,893,220,413,478,345,535,397,637,990,204,496,296,663,272,376,585,291,071,790)
zerocount(1..100Q0Y[46][44]K[49]CKG[45]A[47]Z[43]SPZKGVRN[37]2[41]ZPP[36]I[49][37]EZ[38]C[44]E[46]00CG[38][40][48]ROV,b=51) = 10,0Q0,Y[46][44],K[49]C,KG[45],A[47]Z,[43]SP,ZKG,VRN,[37]2[41],ZPP,[36]I[49],[37]EZ,[38]C[44],E[46]0,0CG,[38][40][48],ROV (n=62,191,970,278,446,971,531,566,522,791,454,395,351,613,891,150,548,291,266,262,575,754,206,359,828,753,062,692,619,547)
zerocount(1..100QQ[40]TL[39]ZA[49][41]J[41]7Q[46]4[41]66A1E6QHHTM9[44]8Z892FRUL6V[46]1[38][41]C[40][45]KB[39],b=52) = 100,QQ[40],TL[39],ZA[49],41]J[41],7Q[46],4[41]6,6A1,E6Q,HHT,M9[44],8Z8,92F,RUL,6V[46],1[38][41],C[40][45],KB[39] (n=8,876,854,501,927,007,077,802,489,292,131,402,136,556,544,697,945,824,257,389,527,114,587,644,068,732,794,430,403,381,731)
zerocount(1..100S0[37]V[53]Y6G[51]5J[42][38]X[40]XO[38]NSZ[42]XUD[47]1XVKS[52]R[39]JAHH[49][39][50][54]5PBU[42]H3[45][46]DEJ,b=55) = 100,S0[37],V[53]Y,6G[51],5J[42],[38]X[40],XO[38],NSZ,[42]XU,D[47]1,XVK,S[52]R,[39]JA,HH[49],[39][50][54],5PB,U[42]H,3[45][46],DEJ (n=28,865,808,580,366,629,824,612,818,017,012,809,163,332,327,132,687,722,294,521,718,120,736,868,268,650,080,765,802,786,141,387,114)

Autonomata

“Describe yourself.” You can say it to people. And you can say it to numbers too. For example, here’s the number 3412 describing the positions of its own digits, starting at 1 and working upward:


3412 – the 1 is in the 3rd position, the 2 is in the 4th position, the 3 is in the 1st position, and the 4 is in the 2nd position.

In other words, the positions of the digits 1 to 4 of 3412 recreate its own digits:


3412 → (3,4,1,2) → 3412

The number 3412 describes itself – it’s autonomatic (from Greek auto, “self” + onoma, “name”). So are these numbers:


1
21
132
2143
52341
215634
7243651
68573142
321654798

More precisely, they’re panautonomatic numbers, because they describe the positions of all their own digits (Greek pan or panto, “all”). But what if you use the positions of only, say, the 1s or the 3s in a number? In base ten, only one number describes itself like that: 1. But we’re not confined to base 10. In base 2, the positions of the 1s in 110 (= 6) are 1 and 10 (= 2). So 110 is monautonomatic in binary (Greek mono, “single”). 10 is also monautonomatic in binary, if the digit being described is 0: it’s in 2nd position or position 10 in binary. These numbers are monoautonomatic in binary too:


110100 = 52 (digit = 1)
10100101111 = 1327 (d=0)

In 110100, the 1s are in 1st, 2nd and 4th position, or positions 1, 10, 100 in binary. In 10100101111, the 0s are in 2nd, 4th, 5th and 7th position, or positions 10, 100, 101, 111 in binary. Here are more monautonomatic numbers in other bases:


21011 in base 4 = 581 (digit = 1)
11122122 in base 3 = 3392 (d=2)
131011 in base 5 = 5131 (d=1)
2101112 in base 4 = 9302 (d=1)
11122122102 in base 3 = 91595 (d=2)
13101112 in base 5 = 128282 (d=1)
210111221 in base 4 = 148841 (d=1)

For example, in 131011 the 1s are in 1st, 3rd, 5th and 6th position, or positions 1, 3, 10 and 11 in quinary. But these numbers run out quickly and the only monautonomatic number in bases 6 and higher is 1. However, there are infinitely long monoautonomatic integer sequences in all bases. For example, in binary this sequence at the Online Encyclopedia of Integer Sequences describes itself using the positions of its 1s:


A167502: 1, 10, 100, 111, 1000, 1001, 1010, 1110, 10001, 10010, 10100, 10110, 10111, 11000, 11010, 11110, 11111, 100010, 100100, 100110, 101001, 101011, 101100, 101110, 110000, 110001, 110010, 110011, 110100, 111000, 111001, 111011, 111101, 11111, …

In base 10, it looks like this:


A167500: 1, 2, 4, 7, 8, 9, 10, 14, 17, 18, 20, 22, 23, 24, 26, 30, 31, 34, 36, 38, 41, 43, 44, 46, 48, 49, 50, 51, 52, 56, 57, 59, 61, 62, 63, 64, 66, 67, 68, 69, 70, 71, 75, 77, 80, 83, 86, 87, 89, 91, 94, 95, 97, 99, 100, 101, 103, 104, 107, 109, 110, 111, 113, 114, 119, 120, 124, … (see A287515 for a similar sequence using 0s)

In any base, you can find some sequence of integers describing the positions of any of the digits in that base – for example, the 1s or the 7s. But the numbers in the sequence get very large very quickly in higher bases. For example, here are some opening sequences for the digits 0 to 9 in base 10:


3, 10, 1111110, … (d=0)
1, 3, 10, 200001, … (d=1)
3, 12, 100000002, … (d=2)
2, 3, 30, 10000000000000000000000003, … (d=3)
2, 4, 14, 1000000004, … (d=4)
2, 5, 105, … (d=5)
2, 6, 1006, … (d=6)
2, 7, 10007, … (d=7)
2, 8, 100008, … (d=8)
2, 9, 1000009, … (d=9)

In the sequence for d=0, the first 0 is in the 3rd position, the second 0 is in the 10th position, and the third 0 is in the 1111110th position. That’s why I’ve haven’t written the next number – it’s 1,111,100 digits long (= 1111110 – 10). But it’s theoretically possible to write the number. In the sequence for d=3, the next number is utterly impossible to write, because it’s 9,999,999,999,999,999,999,999,973 digits long (= 10000000000000000000000003 – 30). In the sequence for d=5, the next number is this:


1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005 (100 digits long = 105 – 5).

And in fact there are an infinite number of such sequences for any digit in any base – except for d=1 in binary. Why is binary different? Because 1 is the only digit that can start a number in that base. With 0, you can invent a sequence starting like this:


111, 1110, 1111110, …

Or like this:


1111, 11111111110, …

Or like this:


11111, 1111111111111111111111111111110, …

And so on. But with 1, there’s no room for manoeuvre.

T4K1NG S3LF13S

It’s like watching a seed grow. You take a number and count how many 0s it contains, then how many 1s, how many 2s, 3s, 4s and so on. Then you create a new number by writing the count of each digit followed by the digit itself. Then you repeat the process with the new number.

Here’s how it works if you start with the number 1:

1

The count of digits is one 1, so the new number is this:

→ 11

The count of digits for 11 is two 1s, so the next number is:

→ 21

The count of digits for 21 is one 1, one 2, so the next number is:

→ 1112

The count of digits for 1112 is three 1s, one 2, so the next number is:

→ 3112

The count of digits for 3112 is two 1s, one 2, one 3, so the next number is:

→ 211213

What happens after that? Here are the numbers as a sequence:

1 → 11 → 21 → 1112 → 3112 → 211213 → 312213 → 212223 → 114213 → 31121314 → 41122314 → 31221324 → 21322314

That’s all you need, because something interesting happens with 21322314. The digit count is two 1s, three 2s, two 3s, one 4, so the next number is:

→ 21322314

In other words, 21322314 is what might be called a self-descriptive number: it describes the count of its own digits. That’s why I think this procedure is like watching a seed grow. You start with the tiny seed of 1 and end in the giant oak of 21322314, whose factorization is 2 * 3^2 * 13 * 91121. But there are many more self-descriptive numbers in base ten and some of them are much bigger than 21322314. A047841 at the Online Encyclopedia of Integer Sequences lists all 109 of them (and calls them “autobiographical numbers”). Here are a few, starting with the simplest possible:

22 → two 2s → 22
10213223 → one 0, two 1s, three 2s, two 3s → 10213223
10311233 → one 0, three 1s, one 2, three 3s → 10311233
21322314 → two 1s, three 2s, two 3s, one 4 → 21322314
21322315 → two 1s, three 2s, two 3s, one 5 → 21322315
21322316 → two 1s, three 2s, two 3s, one 6 → 21322316*
1031223314 → one 0, three 1s, two 2s, three 3s, one 4 → 10
31223314
3122331415 → three 1s, two 2s, three 3s, one 4, one 5
→ 3122331415
3122331416 → three 1s, two 2s, three 3s, one 4, one 6
→ 3122331416*

*And for 21322317, 21322318, 21322319; 3122331417, 3122331418, 3122331419.


And here’s what happens when you seed a sequence with a number containing all possible digits in base ten:

1234567890 → 10111213141516171819 → 101111213141516171819 → 101211213141516171819 → 101112213141516171819

That final number is self-descriptive:

101112213141516171819 → one 0, eleven 1s, two 2s, one 3, one 4, one 5, one 6, one 7, one 8, one 9 → 101112213141516171819

So some numbers are self-descriptive and some start a sequence that ends in a self-descriptive number. But that doesn’t exhaust the possibilities. Some numbers are part of a loop:

103142132415 → 104122232415 → 103142132415
104122232415 → 103142132415 → 104122232415
1051421314152619 → 1061221324251619 → 1051421314152619…
5142131415261819 → 6122132425161819 → 5142131415261819
106142131416271819 → 107122132426171819 → 106142131416271819


10512223142518 → 10414213142518 → 10512213341518 → 10512223142518
51222314251718 → 41421314251718 → 51221334151718 →
51222314251718

But all that is base ten. What about other bases? In fact, nearly all self-descriptive numbers in base ten are also self-descriptive in other bases. An infinite number of other bases, in fact. 22 is a self-descriptive number for all b > 2. The sequence seeded with 1 is identical in all b > 4:

1 → 11 → 21 → 1112 → 3112 → 211213 → 312213 → 212223 → 114213 → 31121314 → 41122314 → 31221324 → 2132231421322314

In bases 2, 3 and 4, the sequence seeded with 1 looks like this:

1 → 11 → 101 → 10101 → 100111 → 1001001 → 1000111 → 11010011101001… (b=2) (1101001[2] = 105 in base 10)
1 → 11 → 21 → 1112 → 10112 → 1010112 → 2011112 → 10111221011122… (b=3) (1011122[3] = 854 in base 10)
1 → 11 → 21 → 1112 → 3112 → 211213 → 312213 → 212223 → 1110213 → 101011213 → 201111213 → 101112213101112213… (b=4) (101112213[4] = 71079 in base 10)

In base 2 there are only two self-descriptive numbers (and no loops):

111 → three 1s → 111… (b=2) (111 = 7 in base 10)
1101001 → three 0s, four 1s → 1101001… (b=2) (1101001 = 105 in base 10)

So if you apply the “count digits” procedure in base 2, all numbers, except 111, begin a sequence that ends in 1101001. Base 3 has a few more self-descriptive numbers and also some loops:

2222… (b >= 3)
10111 → one 0, four 1s → 10111… (b=3)
11112 → four 1s, one 2 → 11112
100101 → three 0s, three 1s → 100101… (b=3)
1011122 → one 0, four 1s, two 2s → 1011122… (b=3)
2021102 → two 0s, two 1s, three 2s → 2021102… (b=3)
10010122 → three 0s, three 1s, two 2s → 10010122


2012112 → 10101102 → 10011112 → 2012112
10011112 → 2012112 → 10101102 → 10011112
10101102 → 10011112 → 2012112 → 10101102

A question I haven’t been able to answer: Is there a base in which loops can be longer than these?

103142132415 → 104122232415 → 103142132415
10512223142518 → 10414213142518 → 10512213341518 → 10512223142518

A question I have been able to answer: What is the sequence when it’s seeded with the title of this blog-post? T4K1NGS3LF13S is a number in all bases >= 30 and its base-30 form equals 15,494,492,743,722,316,018 in base 10 (with the factorization 2 * 72704927 * 106557377767). If T4K1NGS3LF13S seeds a sequence in any b >= 30, the result looks like this:

T4K1NGS3LF13S → 2123141F1G1K1L1N2S1T → 813213141F1G1K1L1N1S1T → A1122314181F1G1K1L1N1S1T → B1221314181A1F1G1K1L1N1S1T → C1221314181A1B1F1G1K1L1N1S1T → D1221314181A1B1C1F1G1K1L1N1S1T → E1221314181A1B1C1D1F1G1K1L1N1S1T → F1221314181A1B1C1D1E1F1G1K1L1N1S1T → G1221314181A1B1C1D1E2F1G1K1L1N1S1T → F1321314181A1B1C1D1E1F2G1K1L1N1S1T → F1222314181A1B1C1D1E2F1G1K1L1N1S1T → E1421314181A1B1C1D1E2F1G1K1L1N1S1T → F1221324181A1B1C1D2E1F1G1K1L1N1S1T → E1421314181A1B1C1D1E2F1G1K1L1N1S1T

Can You Dij It? #2

It’s very simple, but I’m fascinated by it. I’m talking about something I call the digit-line, or the stream of digits you get when you split numbers in a particular base into individual digits. For example, here are the numbers one to ten in bases 2 and 3:

Base = 2: 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010…
Base = 3: 1, 2, 10, 11, 12, 20, 21, 22, 100, 101…


If you turn them into digit-lines, they look like this:

Base = 2: 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0… (A030190 in the Online Encyclopedia of Integer Sequences)
Base = 3: 1, 2, 1, 0, 1, 1, 1, 2, 2, 0, 2, 1, 2, 2, 1, 0, 0, 1, 0, 1… (A003137 in the OEIS)


At the tenth digit of the two digit-lines, both digits equal zero for the first time:

Base = 2: 1, 1, 0, 1, 1, 1, 0, 0, 1, 0
Base = 3: 1, 2, 1, 0, 1, 1, 1, 2, 2, 0


When the binary and ternary digits are represented together, the digit-lines look like this:

(1,1), (1,2), (0,1), (1,0), (1,1), (1,1), (0,1), (0,2), (1,2), (0,0)


But in base 4, the tenth digit of the digit-line is 1. So when do all the digits of the digit-line first equal zero for bases 2 to 4? Here the early integers in those bases:

Base 2: 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, 10000, 10001, 10010, 10011, 10100, 10101…

Base 3: 1, 2, 10, 11, 12, 20, 21, 22, 100, 101, 102, 110, 111, 112, 120, 121, 122, 200, 201, 202, 210, 211, 212, 220, 221, 222, 1000, 1001, 1002…

Base 4: 1, 2, 3, 10, 11, 12, 13, 20, 21, 22, 23, 30, 31, 32, 33, 100, 101, 102, 103, 110, 111, 112, 113, 120, 121, 122, 123, 130, 131, 132, 133, 200…


And here are the digits of the digit-line in bases 2 to 4 represented together:

(1,1,1), (1,2,2), (0,1,3), (1,0,1), (1,1,0), (1,1,1), (0,1,1), (0,2,1), (1,2,2), (0,0,1), (1,2,3), (1,1,2), (1,2,0), (0,2,2), (1,1,1), (1,0,2), (1,0,2), (1,1,2), (0,0,3), (0,1,3), (0,1,0), (1,0,3), (0,2,1), (0,1,3), (1,1,2), (1,0,3), (0,1,3), (1,1,1), (0,1,0), (1,1,0), (0,1,1), (1,2,0), (1,1,1), (1,2,1), (1,0,0), (0,1,2), (0,2,1), (1,1,0), (1,1,3), (0,2,1), (1,2,1), (1,2,0), (1,0,1), (1,0,1), (0,2,1), (1,0,1), (1,1,1), (1,2,2), (1,0,1), (1,2,1), (0,2,3), (0,1,1), (0,0,2), (0,2,0), (1,1,1), (0,1,2), (0,2,1), (0,1,1), (1,2,2), (1,2,2), (0,2,1), (0,0,2), (1,2,3), (0,2,1), (1,1,3), (0,2,0), (0,2,1), (1,2,3), (1,1,1), (1,0,1), (0,0,3), (1,0,2), (0,1,1), (0,0,3), (1,0,3), (0,1,2), (1,1,0), (0,0,0)

At the 78th digit, all three digits equal zero. But the 78th digit of the digit-line in base 5 is 1. So when are the digits first equal to zero in bases 2 to 5? It’s not difficult to find out, but the difficulty of the search increases fast as the bases get bigger. Here are the results up to base 13 (note that bases 11 and 12 both have zeroes at digit 103721663):

dig=0 in bases 2 to 3 at the 10th digit of the digit-line
dig=0 in bases 2 to 4 at the 78th digit of the digit-line
dig=0 in bases 2 to 5 at the 182nd digit of the digit-line
dig=0 in bases 2 to 6 at the 302nd digit of the digit-line
dig=0 in bases 2 to 7 at the 12149th digit of the digit-line
dig=0 in bases 2 to 8 at the 45243rd digit of the digit-line
dig=0 in bases 2 to 9 at the 255261st digit of the digit-line
dig=0 in bases 2 to 10 at the 8850623rd digit of the digit-line
dig=0 in bases 2 to 12 at the 103721663rd digit of the digit-line
dig=0 in bases 2 to 13 at the 807778264th digit of the digit-line


I assume that, for any base b > 2, you can find some point in the digit-line at which d = 0 for all bases 2 to b. Indeed, I assume that this happens infinitely often. But I don’t know any short-cut for finding the first digit at which this occurs.


Previously pre-posted:

Can You Dij It? #1

Get Your Ox Off

Boustrophedon (pronounced “bough-stra-FEE-dun” or “boo-stra-FEE-dun”) is an ancient Greek word literally meaning “as the ox turns (in ploughing)”, that is, moving left-right, right-left, and so on. The word is used of writing that runs down the page in the same way. To see what that means, examine two versions of the first paragraph of Clark Ashton Smith’s story “The Demon of the Flower” (1933). The first is written in the usual way, the second is written boustrophedon:

Not as the plants and flowers of Earth, growing peacefully beneath a simple sun, were the blossoms of the planet Lophai. Coiling and uncoiling in double dawns; tossing tumultuously under vast suns of jade green and balas-ruby orange; swaying and weltering in rich twilights, in aurora-curtained nights, they resembled fields of rooted servants that dance eternally to an other-worldly music.


Not as the plants and flowers of Earth, growing peacefully
.iahpoL tenalp eht fo smossolb eht erew ,nus elpmis a htaeneb
Coiling and uncoiling in double dawns; tossing tumultuously
;egnaro ybur-salab dna neerg edaj fo snus tsav rednu
swaying and weltering in rich twilights, in aurora-curtained
ecnad taht stnavres detoor fo sdleif delbmeser yeht ,sthgin
eternally to an other-worldly music.


Boustrophedon writing was once common and sometimes the left-right lines would also be mirror-reversed, like this:
CAS_text1


You could also use the term “boustrophedon” to describe the way this table of numbers is filled:

primes_table


The table begins with “1” in the top left-hand corner, then moves right for “2”, then down for “3”, then right-and-up for “4”, “5” and “6”, then right for “7”, then left-and-down for “8”, “9” and “10”, and so on. You could also say that the numbers snake through the table. I’ve marked the primes among them, because I was interested in the patterns made by the primes when the numbers were represented as blocks on a grid, like this:

primes_large


Primes are in solid white (compare the Ulam spiral). Here’s the boustrophedon prime-grid on a finer scale:

primes

(click for full image)


And what about other number-tests? Here are the even numbers marked on the grid (i.e. n mod 2 = 0):

mod2

n mod 2 = 0


And here are some more examples of a modulus test:

mod3

n mod 3 = 0


mod5

n mod 5 = 0


mod9

n mod 9 = 0


mod15

n mod 15 = 0


mod_various

n mod various = 0 (animated gif)


Next I looked at reciprocals (numbers divided into 1) marked on the grid, with the digits of a reciprocal marking the number of blank squares before a square is filled in (if the digit is “0”, the square is filled immediately). For example, in base ten 1/7 = 0.142857142857142857…, where the block “142857” repeats for ever. When represented on the grid, 1/7 has 1 blank square, then a filled square, then 4 blank squares, then a filled square, then 2 blank squares, then a filled square, and so on:

recip7_base10

1/7 in base 10


And here are some more reciprocals (click for full images):

recip9_base2

1/9 in base 2


recip13_base10

1/13 in base 10


recip27_base10

1/27 in base 10


recip41_base10

1/41 in base 10


recip63_base10

1/63 in base 10


recip82_base10

1/82 in base 10


recip101_base10

1/101 in base 10


recip104_base10

1/104 in base 10


recip124_base10

1/124 in base 10


recip143_base10

1/143 in base 10


recip175_base10

1/175 in base 10


recip604_base8

1/604 in base 8


recip_various

1/n in various bases (animated gif)


Digital Rodeo

What a difference a digit makes. Suppose you take all representations of n in bases b <= n. When n = 3, the bases are 2 and 3, so 3 = 11 and 10, respectively. Next, count the occurrences of the digit 1:

digitcount(3, digit=1, n=11, 10) = 3

Add this digit-count to 3:

3 + digitcount(3, digit=1, n=11, 10) = 3 + 3 = 6.

Now apply the same procedure to 6. The bases will be 2 to 6:

6 + digitcount(6, digit=1, n=110, 20, 12, 11, 10) = 6 + 6 = 12

The procedure, n = n + digitcount(n,digit=1,base=2..n), continues like this:

12 + digcount(12,dig=1,n=1100, 110, 30, 22, 20, 15, 14, 13, 12, 11, 10) = 12 + 11 = 23
23 + digcount(23,dig=1,n=10111, 212, 113, 43, 35, 32, 27, 25, 23, 21, 1B, 1A, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10) = 23 + 21 = 44
44 + digcount(44,dig=1,n=101100, 1122, 230, 134, 112, 62, 54, 48, 44, 40, 38, 35, 32, 2E, 2C, 2A, 28, 26, 24, 22, 20, 1L, 1K, 1J, 1I, 1H, 1G, 1F, 1E, 1D, 1C, 1B, 1A, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10) = 44 + 31 = 75

And the sequence develops like this:

3, 6, 12, 23, 44, 75, 124, 202, 319, 503, 780, 1196, 1824, 2766, 4191, 6338, 9546, 14383, 21656, 32562, 48930, 73494, 110361, 165714, 248733, 373303, 560214, 840602, 1261237, 1892269, 2838926, 4258966, 6389157, 9584585, 14377879…

Now try the same procedure using the digit 0: n = n + digcount(n,dig=0,base=2..n). The first step is this:

3 + digcount(3,digit=0,n=11, 10) = 3 + 1 = 4

Next come these:

4 + digcount(4,dig=0,n=100, 11, 10) = 4 + 3 = 7
7 + digcount(7,dig=0,n=111, 21, 13, 12, 11, 10) = 7 + 1 = 8
8 + digcount(8,dig=0,n=1000, 22, 20, 13, 12, 11, 10) = 8 + 5 = 13
13 + digcount(13,dig=0,n=1101, 111, 31, 23, 21, 16, 15, 14, 13, 12, 11, 10) = 13 + 2 = 15
15 + digcount(15,dig=0,n=1111, 120, 33, 30, 23, 21, 17, 16, 15, 14, 13, 12, 11, 10) = 15 + 3 = 18
18 + digcount(18,dig=0,n=10010, 200, 102, 33, 30, 24, 22, 20, 18, 17, 16, 15, 14, 13, 12, 11, 10) = 18 + 9 = 27
27 + digcount(27,dig=0,n=11011, 1000, 123, 102, 43, 36, 33, 30, 27, 25, 23, 21, 1D, 1C, 1B, 1A, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10) = 27 + 7 = 34
34 + digcount(34,dig=0,n=100010, 1021, 202, 114, 54, 46, 42, 37, 34, 31, 2A, 28, 26, 24, 22, 20, 1G, 1F, 1E, 1D, 1C, 1B, 1A, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10) = 34 + 8 = 42
42 + digcount(42,dig=0,n=101010, 1120, 222, 132, 110, 60, 52, 46, 42, 39, 36, 33, 30, 2C, 2A, 28, 26, 24, 22, 20, 1K, 1J, 1I, 1H, 1G, 1F, 1E, 1D, 1C, 1B, 1A, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10) = 42 + 9 = 51

The sequence develops like this:

3, 4, 7, 8, 13, 15, 18, 27, 34, 42, 51, 59, 62, 66, 80, 94, 99, 111, 117, 125, 132, 151, 158, 163, 173, 180, 204, 222, 232, 244, 258, 279, 292, 307, 317, 324, 351, 364, 382, 389, 400, 425, 437, 447, 454, 466, 475, 483, 494, 509, 517, 536, 553, 566, 576, 612, 637, 649, 669, 679, 693, 712, 728, 753, 768, 801, 822, 835, 849, 862, 869, 883, 895, 906, 923, 932, 943, 949, 957, 967, 975, 999, 1011…

If you compare it with the sequence for digit=1, it appears that digcount(n,dig=1,b=2..n) is always larger than digcount(n,dig=0,b=2..n). That is in fact the case, with one exception, when n = 2:

digcount(2,dig=1,n=10) = 1
digcount(2,dig=0,n=10) = 1

When n = 10 (in base ten), there are twice as many ones as zeros:

digcount(10,dig=1,n=1010, 101, 22, 20, 14, 13, 12, 11, 10) = 10
digcount(10,dig=0,n=1010, 101, 22, 20, 14, 13, 12, 11, 10) = 5

As n gets larger, the difference grows dramatically:

digcount(100,dig=1,base=2..n) = 64
digcount(100,dig=0,base=2..n) = 16

digcount(1000,dig=1,base=2..n) = 533
digcount(1000,dig=0,base=2..n) = 25

digcount(10000,dig=1,base=2..n) = 5067
digcount(10000,dig=0,base=2..n) = 49

digcount(100000,dig=1,base=2..n) = 50140
digcount(100000,dig=0,base=2..n) = 73

digcount(1000000,dig=1,base=2..n) = 500408
digcount(1000000,dig=0,base=2..n) = 102

digcount(10000000,dig=1,base=2..n) = 5001032
digcount(10000000,dig=0,base=2..n) = 134

digcount(100000000,dig=1,base=2..n) = 50003137
digcount(100000000,dig=0,base=2..n) = 160

In fact, digcount(n,dig=1,b=2..n) is greater than the digit-count for any other digit: 0, 2, 3, 4, 5… (with the exception n = 2, as shown above). But digit=0 sometimes beats digits >= 2. For example, when n = 18:

digcount(18,dig=0,n=10010, 200, 102, 33, 30, 24, 22, 20, 18, 17, 16, 15, 14, 13, 12, 11, 10) = 9
digcount(18,dig=2,n=10010, 200, 102, 33, 30, 24, 22, 20, 18, 17, 16, 15, 14, 13, 12, 11, 10) = 7
digcount(18,dig=3,n=10010, 200, 102, 33, 30, 24, 22, 20, 18, 17, 16, 15, 14, 13, 12, 11, 10) = 4
digcount(18,dig=4,n=10010, 200, 102, 33, 30, 24, 22, 20, 18, 17, 16, 15, 14, 13, 12, 11, 10) = 2
digcount(18,dig=5,n=10010, 200, 102, 33, 30, 24, 22, 20, 18, 17, 16, 15, 14, 13, 12, 11, 10) = 1

But as n gets larger, digcount(0) will fall permanently behind all these digits. However, digcount(0) will always be greater than some digit d, for the obvious reason that some digits only appear when the base is high enough. For example, the hexadecimal digit A (with the decimal value 10) first appears when n = 21:

digcount(21,dig=A,n=10101, 210, 111, 41, 33, 30, 25, 23, 21, 1A, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10) = 1 digcount(21,dig=0,n=10101, 210, 111, 41, 33, 30, 25, 23, 21, 1A, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10) = 5

There is a general rule for the n at which digit d first appears, n = 2d + 1 (this doesn’t apply when d = 0 or d = 1):

d = 2, n = 5 = 2*2 + 1
digcount(5,dig=2,n=101, 12, 11, 10) = 1

d = 3, n = 7 = 2*3 + 1
digcount(7,dig=3,n=111, 21, 13, 12, 11, 10) = 1

d = 4, n = 9 = 2*4 + 1
digcount(9,dig=4,n=1001, 100, 21, 14, 13, 12, 11, 10) = 1

d = 5, n = 11 = 2*5 + 1
digcount(11,dig=5,n=1011, 102, 23, 21, 15, 14, 13, 12, 11, 10) = 1

It should be apparent, then, that the digit-count for a particular digit starts at 1 and gets gradually higher. The rate at which the digit-count increases is highest for 1 and lowest for 0, with digits 2, 3, 4, 5… in between:

All-Base Graph

Graph for digcount(n,dig=d,b=2..n)


You could think of the graph as a digital rodeo in which these digits compete with each other. 1 is the clear and permanent winner, 0 the gradual loser. Now recall the procedure introduced at the start: n = n + digcount(n,dig=d,b=2..n). When it’s applied to the digits 0 to 5, these are the sequences that appear:

n = n + digcount(n,dig=0,b=2..n)

2, 3, 4, 7, 8, 13, 15, 18, 27, 34, 42, 51, 59, 62, 66, 80, 94, 99, 111, 117, 125, 132, 151, 158, 163, 173, 180, 204, 222, 232, 244, 258, 279, 292, 307, 317, 324, 351, 364, 382, 389, 400, 425, 437, 447, 454, 466, 475, 483, 494, 509, 517, 536, 553, 566, 576, 612, 637, 649, 669, 679, 693, 712, 728, 753, 768, 801, 822, 835, 849, 862, 869, 883, 895, 906, 923, 932, 943, 949, 957, 967, 975, 999, 1011…

n = n + digcount(n,dig=1,b=2..n)

2, 3, 6, 12, 23, 44, 75, 124, 202, 319, 503, 780, 1196, 1824, 2766, 4191, 6338, 9546, 14383, 21656, 32562, 48930, 73494, 110361, 165714, 248733, 373303, 560214, 840602, 1261237, 1892269, 2838926, 4258966, 6389157, 9584585, 14377879…

n = n + digcount(n,dig=2,b=2..n)

5, 6, 8, 12, 16, 22, 31, 37, 48, 60, 76, 94, 115, 138, 173, 213, 257, 311, 374, 454, 542, 664, 790, 935, 1109, 1310, 1552, 1835, 2167, 2548, 2989, 3509, 4120, 4832, 5690, 6687, 7829, 9166, 10727, 12568, 14697, 17182, 20089, 23470, 27425, 32042, 37477, 43768, 51113, 59687, 69705, 81379, 94998, 110910, 129488, 151153, 176429, 205923, 240331, 280490, 327396, 382067, 445858…

n = n + digcount(n,dig=3,b=2..n)

7, 8, 9, 10, 11, 13, 16, 18, 22, 25, 29, 34, 38, 44, 50, 56, 63, 80, 90, 104, 113, 131, 151, 169, 188, 210, 236, 261, 289, 320, 350, 385, 424, 463, 520, 572, 626, 684, 747, 828, 917, 999, 1101, 1210, 1325, 1446, 1577, 1716, 1871, 2040, 2228, 2429, 2642, 2875, 3133, 3413, 3719, 4044, 4402, 4786, 5196, 5645, 6140, 6673, 7257, 7900, 8582, 9315, 10130, 10998, 11942, 12954, 14058…

n = n + digcount(n,dig=4,b=2..n)

9, 10, 11, 12, 13, 14, 16, 18, 20, 23, 25, 28, 34, 41, 44, 52, 61, 67, 74, 85, 92, 102, 113, 121, 134, 148, 170, 184, 208, 229, 253, 269, 287, 306, 324, 356, 386, 410, 439, 469, 501, 531, 565, 604, 662, 703, 742, 794, 845, 895, 953, 1007, 1062, 1127, 1188, 1262, 1336, 1421, 1503, 1585, 1676, 1777, 1876, 2001, 2104, 2249, 2375, 2502, 2636, 2789, 2938, 3102, 3267, 3444, 3644, 3868, 4099…

n = n + digcount(n,dig=5,b=2..n)

11, 12, 13, 14, 15, 16, 17, 19, 21, 23, 26, 28, 29, 33, 37, 41, 48, 50, 55, 60, 64, 67, 72, 75, 83, 91, 96, 102, 107, 118, 123, 129, 137, 151, 159, 171, 180, 192, 202, 211, 224, 233, 251, 268, 280, 296, 310, 324, 338, 355, 380, 401, 430, 455, 488, 511, 536, 562, 584, 607, 638, 664, 692, 718, 748, 778, 807, 838, 874, 911, 951, 993, 1039, 1081, 1124, 1166, 1216, 1264, 1313, 1370, 1432…