Category Archives: Binary numbers

Pi in the Bi

by in Binary numbers, Mathematics, Pi and tagged , , , , , , , , , , , , | Leave a comment

Binary is beautiful — both simple and subtle. What could be simpler than using only two digits to count with?


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, 1000000...

But the simple patterns in the two digits of binary involve two of the most important numbers in mathematics: π and e (aka Euler’s number):


π = 3.141592653589793238462643383...
e = 2.718281828459045235360287471...

It’s easy to write π and e in binary:


π = 11.00100 10000 11111 10110 10101 00010...
e = 10.10110 11111 10000 10101 00010 11000...

But how do π and e appear in the patterns of binary 1 and 0? Well, suppose you use the digits of binary to generate the sums of distinct integers. For example, here are the sums of distinct integers you can generate with three digits of binary, if you count the digits from right to left (so the rightmost digit is 1, the the next-to-rightmost digit is 2, the next-to-leftmost digit is 3, and the leftmost digit is 4):


0000 → 0*4 + 0*3 + 0*2 + 0*1 = 0
0001 → 0*4 + 0*3 + 0*2 + 1*1 = 1*1 = 1
0010 → 0*4 + 0*3 + 1*2 + 0*1 = 1*2 = 2
0011 → 0*4 + 0*3 + 1*2 + 1*1 = 1*2 + 1*1 = 3
0100 → 1*3 = 3
0101 → 1*3 + 1*1 = 4
0110 → 3 + 2 = 5
0111 → 3 + 2 + 1 = 6
1000 → 4
1001 → 4 + 1 = 5
1010 → 4 + 2 = 6
1011 → 4 + 2 + 1 = 7
1100 → 4 + 3 = 7
1101 → 4 + 3 + 1 = 8
1110 → 4 + 3 + 2 = 9
1111 → 4 + 3 + 2 + 1 = 10

There are 16 sums (16 = 2^4) generating 11 integers, 0 to 10. But some integers involve more than one sum:


3 = 2 + 1 ← 0011
3 = 3 ← 0100

4 = 3 + 1 ← 0101
4 = 4 ← 1000

5 = 3 + 2 ← 0110
5 = 4 + 1 ← 1001

6 = 3 + 2 + 1 ← 0111
6 = 4 + 2 ← 1010

7 = 4 + 2 + 1 ← 1011
7 = 4 + 3 ← 1100

Note the symmetry of the sums: the binary number 0011, yielding 3, is the mirror of 1100, yielding 7; the binary number 0100, yielding 3 again, is the mirror of 1011, yielding 7 again. In each pair of mirror-sums, the two numbers, 3 and 7, are related by the formula 10-3 = 7 and 10-7 = 3. This also applies to 4 and 6, where 10-4 = 6 and 10-6 = 4, and to 5, which is its own mirror (because 10-5 = 5). Now, try mapping the number of distinct sums for 0 to 10 as a graph:

Graph for distinct sums of the integers 0 to 4

The graph show how 0, 1 and 2 have one sum each, 3, 4, 5, 6 and 7 have two sums each, and 8, 9 and 10 have one sum each. Now look at the graph for sums derived from three digits of binary:

Graph for distinct sums of the integers 0 to 3

The single taller line of the seven lines represents the two sums of 3, because three digits of binary yield only one sum for 0, 1, 2, 4, 5 and 6:


000 → 0
001 → 1
010 → 2
011 → 2 + 1 = 3
100 → 3
101 → 3 + 1 = 4
110 → 3 + 2 = 5
111 → 3 + 2 + 1 = 6

Next, look at graphs for sums derived from one to sixteen binary digits and note how the symmetry of the lines begins to create a beautiful curve (the y axis is normalized, so that the highest number of sums reaches the same height in each graph):

Graph for sums from 1 binary digit

Graph for sums from 2 binary digits

Graph for sums from 3 binary digits

Graph for sums from 4 binary digits

Graph for sums from 5 binary digits

Graph for sums from 6 binary digits

Graph for sums from 7 binary digits

Graph for sums from 8 binary digits

Graph for sums from 9 binary digits

Graph for sums from 10 binary digits

Graph for sums from 11 binary digits

Graph for sums from 12 binary digits

Graph for sums from 13 binary digits

Graph for sums from 14 binary digits

Graph for sums from 15 binary digits

Graph for sums from 16 binary digits

Graphs for 1 to 16 binary digits (animated)

You may recognize the shape emerging above as the bell curve, whose formula is this:

Formula for the normal distribution or bell curve (image from ThoughtCo)

And that’s how you can find pi in the bi, or π in the binary digits of 0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101…

(And how you find e too, as promised above.)

Post-Performative Post-Scriptum

I asked this question above: What could be simpler than using only two digits? Well, using only one digit is simpler still:


1, 11, 111, 1111, 11111, 111111, 1111111, 11111111, 111111111, 1111111111...

But I don’t see an easy way to find π and e in numbers like that.

Z-Fall

by in Base Behavior, Binary numbers, Digit-sums, Integer sequences, Mathematics and tagged , , , , , , , , , , , , , , , , , | Leave a comment

Do you want a haunting literary image? You’ll find one of the strangest and strongest in Borges’ “La Biblioteca de Babel” (1941), which is narrated by a librarian in an infinite library. The librarian anticipates the end of his life:

Muerto, no faltarán manos piadosas que me tiren por la baranda; mi sepultura será el aire insondable; mi cuerpo se hundirá largamente y se corromperá y disolverá en el viento engenerado por la caída, que es infinita. — “La Biblioteca de Babel”

When I am dead, compassionate hands will throw me over the railing; my tomb will be the unfathomable air, my body will sink for ages, and will decay and dissolve in the wind engendered by my fall, which shall be infinite. — “The Library of Babel” (translation by Andrew Hurley)

The infinite fall is the haunting image. Falling is powerful; falling for ever is more powerful still. But it can’t happen in reality: soon or later a fall has to end. Objects crash to earth or splash into the ocean. Of course, you could call being in orbit a kind of infinite fall, but it doesn’t have the same power.

However, there’s more kinds of falling than one and I think the arithmophile Borges would have liked one of the other kinds a lot. Numbers can fall — you sum their digits, take the sum from the original number, and repeat. That is, n = n – digsum(n). Here are some examples:


10 → 9 → 0
100 → 99 → 81 → 72 → 63 → 54 → 45 → 36 → 27 → 18 → 9 → 0
1000 → 999 → 972 → 954 → 936 → 918 → 900 → 891 → 873 → 855 → 837 → 819 → 801 → 792 → 774 → 756 → 738 → 720 → 711 → 702 → 693 → 675 → 657 → 639 → 621 → 612 → 603 → 594 → 576 → 558 → 540 → 531 → 522 → 513 → 504 → 495 → 477 → 459 → 441 → 432 → 423 → 414 → 405 → 396 → 378 → 360 → 351 → 342 → 333 → 324 → 315 → 306 → 297 → 279 → 261 → 252 → 243 → 234 → 225 → 216 → 207 → 198 → 180 → 171 → 162 → 153 → 144 → 135 → 126 → 117 → 108 → 99 → 81 → 72 → 63 → 54 → 45 → 36 → 27 → 18 → 9 → 0

The details are different in other bases, like 2 or 16, but the destination is the same. The number falls to zero and the fall stops, because digsum(0) = 0:


102 → 1 → 0 (n=2)
100 → 11 → 1 → 0 (n=4)
1000 → 111 → 100 → 11 → 1 → 0 (n=8)
10000 → 1111 → 1011 → 1000 → 111 → 100 → 11 → 1 → 0 (n=16)
100000 → 11111 → 11010 → 10111 → 10011 → 10000 → 1111 → 1011 → 1000 → 111 → 100 → 11 → 1 → 0 (n=32)
1000000 → 111111 → 111001 → 110101 → 110001 → 101110 → 101010 → 100111 → 100011 → 100000 → 11111 → 11010 → 10111 → 10011 → 10000 → 1111 → 1011 → 1000 → 111 → 100 → 11 → 1 → 0 (n=64)

1013 → C → 0 (n=13)
100 → CC → B1 → A2 → 93 → 84 → 75 → 66 → 57 → 48 → 39 → 2A → 1B → C → 0 (n=169)
1000 → CCC → CA2 → C84 → C66 → C48 → C2A → C0C → BC1 → BA3 → B85 → B67 → B49 → B2B → B10 → B01 → AC2 → AA4 → A86 → A68 → A4A → A2C → A11 → A02 → 9C3 → 9A5 → 987 → 969 → 94B → 930 → 921 → 912 → 903 → 8C4 → 8A6 → 888 → 86A → 84C → 831 → 822 → 813 → 804 → 7C5 → 7A7 → 789 → 76B → 750 → 741 → 732 → 723 → 714 → 705 → 6C6 → 6A8 → 68A → 66C → 651 → 642 → 633 → 624 → 615 → 606 → 5C7 → 5A9 → 58B → 570 → 561 → 552 → 543 → 534 → 525 → 516 → 507 → 4C8 → 4AA → 48C → 471 → 462 → 453 → 444 → 435 → 426 → 417 → 408 → 3C9 → 3AB → 390 → 381 → 372 → 363 → 354 → 345 → 336 → 327 → 318 → 309 → 2CA → 2AC → 291 → 282 → 273 → 264 → 255 → 246 → 237 → 228 → 219 → 20A → 1CB → 1B0 → 1A1 → 192 → 183 → 174 → 165 → 156 → 147 → 138 → 129 → 11A → 10B → CC → B1 → A2 → 93 → 84 → 75 → 66 → 57 → 48 → 39 → 2A → 1B → C → 0 (n=2197)

But the fall to 0 made me think of another kind of number-fall. What if you count the 0s in a number, take that count away from the original number, and repeat? You could call this a z-fall (pronounced zee-fall). But unlike free-fall, z-fall doesn’t last long:


10 → 9
100 → 98
1000 → 997
10000 → 9996

And the number always comes to rest far above the ground, as it were. In a fall using digsum(n), the number descends to 0. In a fall using zerocount(n), the number never even reaches 1. At least, never in any base higher than 2. But in base-2, you get this:


10 → 1 (n=2)
100 → 10 → 1 (n=4)
1000 → 101 → 100 → 10 → 1 (n=8)
10000 → 1100 → 1010 → 1000 → 101 → 100 → 10 → 1 (n=16)
100000 → 11011 → 11010 → 11000 → 10101 → 10011 → 10001 → 1110 → 1101 → 1100 → 1010 → 1000 → 101 → 100 → 10 → 1 (n=32)
1000000 → 111010 → 111000 → 110101 → 110011 → 110001 → 101110 → 101100 → 101001 → 100110 → 100011 → 100000 → 11011 → 11010 → 11000 → 10101 → 10011 → 10001 → 1110 → 1101 → 1100 → 1010 → 1000 → 101 → 100 → 10 → 1 (n=64)

When I saw that, I had a wonderful vision of how even the biggest numbers in base 2 could z-fall all the way to 1. Almost all binary numbers contain 0, after all. So the z-falls would get longer and longer, paying tribute to la caída infinita, the infinite fall, of the librarian in Borges’ Library of Babel. Alas, binary numbers don’t behave like that. The highest number in base 2 that z-falls to 1 is this:


1010001 → 1001101 → 1001010 → 1000110 → 1000010 → 111101 → 111100 → 111010 → 111000 → 110101 → 110011 → 110001 → 101110 → 101100 → 101001 → 100110 → 100011 → 100000 → 11011 → 11010 → 11000 → 10101 → 10011 → 10001 → 1110 → 1101 → 1100 → 1010 → 1000 → 101 → 100 → 10 → 1 (n=81)

Above that, binary numbers land on what you might call a shelf:


1010010=82 → 1001110=78 → 1001011=75 → 1001000=72 → 1000011=67 → 111111=63 (n=82)

If binary numbers are an infinite tall mountain, 1 is at the foot of the mountain. 111111 = 63 is like a shelf a little way above the foot. But I conjecture that arbitrarily large binary numbers will z-fall to 63. For example, no matter how large the power of 2, I conjecture that it will z-fall to 63:


10 → 1 : 2 → 1 (count of steps=2)
100 ... → 1 : 4 ... → 1 (c=3)
1000 ... → 1 : 8 ... → 1 (c=5)
10000 ... → 1 : 16 ... → 1 (c=8)
100000 ... → 1 : 32 ... → 1 (c=16)
1000000 ... → 1 : 64 ... → 1 (c=27)
10000000 ... → 111111 : 128 ... → 63 (c=21)
100000000 ... → 111111 : 256 ... → 63 (c=60)
1000000000 ... → 111111 : 512 ... → 63 (c=130)
10000000000 ... → 111111 : 1024 ... → 63 (c=253)
100000000000 ... → 111111 : 2048 ... → 63 (c=473)
1000000000000 ... → 111111 : 4096 ... → 63 (c=869)
10000000000000 ... → 111111 : 8192 ... → 63 (c=1586)
100000000000000 ... → 111111 : 16384 ... → 63 (c=2899)
1000000000000000 ... → 111111 : 32768 ... → 63 (c=5327)
10000000000000000 ... → 111111 : 65536 ... → 63 (c=9851)
100000000000000000 ... → 111111 : 131072 ... → 63 (c=18340)
1000000000000000000 ... → 111111 : 262144 ... → 63 (c=34331)
10000000000000000000 ... → 111111 : 524288 ... → 63 (c=64559)
100000000000000000000 ... → 111111 : 1048576 ... → 63 (c=121831)
1000000000000000000000 ... → 111111 : 2097152 ... → 63 (c=230573)
10000000000000000000000 ... → 111111 : 4194304 ... → 63 (c=437435)
100000000000000000000000 ... → 111111 : 8388608 ... → 63 (c=831722)
1000000000000000000000000 ... → 111111 : 16777216 ... → 63 (c=1584701)
10000000000000000000000000 ... → 111111 : 33554432 ... → 63 (c=3025405)
100000000000000000000000000 ... → 111111 : 67108864 ... → 63 (c=5787008)
1000000000000000000000000000 ... → 111111 : 134217728 ... → 63 (c=11089958)
10000000000000000000000000000 ... → 111111 : 268435456 ... → 63 (c=21290279)
100000000000000000000000000000 ... → 111111 : 536870912 ... → 63 (c=40942711)
1000000000000000000000000000000 ... → 111111 : 1073741824 ... → 63 (c=78864154)

So the z-falls get longer and longer. But z-falling to 63 doesn’t have the power of z-falling to 1.

Digital Dissection

by in Base Behavior, Binary numbers, Digit-sums, Mathematics and tagged , , , , , , , , , , , , , | Leave a comment

As I never tire of pointing out, the three most powerful drugs in the universe are water, maths and language. And I never tire of snorting the fact that numbers can come in many different guises. You can take a trivial, everyday number like a hundred and see it transform like this:


100 = 1100100 in base 2; 10201 in base 3; 1210 in base 4; 400 in base 5; 244 in base 6; 202 in base 7; 144 in base 8; 121 in base 9; 100 in b10; 91 in b11; 84 in b12; 79 in b13; 72 in b14; 6A in b15; 64 in b16; 5F in b17; 5A in b18; 55 in b19; 50 in b20; 4G in b21; 4C in b22; 48 in b23; 44 in b24; 40 in b25; 3M in b26; 3J in b27; 3G in b28; 3D in b29; 3A in b30; 37 in b31; 34 in b32; 31 in b33; 2W in b34; 2U in b35; 2S in b36; 2Q in b37; 2O in b38; 2M in b39; 2K in b40; 2I in b41; 2G in b42; 2E in b43; 2C in b44; 2A in b45; 28 in b46; 26 in b47; 24 in b48; 22 in b49; 20 in b50; 1[49] in b51; 1[48] in b52; 1[47] in b53; 1[46] in b54; 1[45] in b55; 1[44] in b56; 1[43] in b57; 1[42] in b58; 1[41] in b59; 1[40] in b60; 1[39] in b61; 1[38] in b62; 1[37] in b63; 1[36] in b64; 1Z in b65; 1Y in b66; 1X in b67; 1W in b68; 1V in b69; 1U in b70; 1T in b71; 1S in b72; 1R in b73; 1Q in b74; 1P in b75; 1O in b76; 1N in b77; 1M in b78; 1L in b79; 1K in b80; 1J in b81; 1I in b82; 1H in b83; 1G in b84; 1F in b85; 1E in b86; 1D in b87; 1C in b88; 1B in b89; 1A in b90; 19 in b91; 18 in b92; 17 in b93; 16 in b94; 15 in b95; 14 in b96; 13 in b97; 12 in b98; 11 in b99

I like the shifts from 1100100 to 10201 to 1210 to 400 to 244 to 202 to 144 to 121. How can 1100100 and 244 be the same number? Well, they are — or they’re not, as you please. In base 2, 1100100 = 244 in base 6 = 100 in base 10. But if all those numbers are in the same base, they’re completely different and 1100100 dwarfs the other two.

But some things you can’t please yourself about. Suppose you take the different representations of 6561 in bases 2..6560 and add up the 1s, the 2s, the 3s and so on, like this:


n=6561

digsum(1,6561,b=2..6560) = 3343 (50.95% of 6561)
digsum(2,6561,b=2..6560) = 2246 (34.23% of 6561)
digsum(3,6561,b=2..6560) = 1680 (25.61% of 6561)
digsum(4,6561,b=2..6560) = 1368 (20.85% of 6561)
digsum(5,6561,b=2..6560) = 1185 (18.06% of 6561)
digsum(6,6561,b=2..6560) = 1074 (16.37% of 6561)
digsum(7,6561,b=2..6560) = 875 (13.34% of 6561)
digsum(8,6561,b=2..6560) = 768 (11.71% of 6561)
digsum(9,6561,b=2..6560) = 1080 (16.46% of 6561)
[...]
digcount(0,6561,b=2..6560) = 31

Is there a pattern in the percentages? Let’s apply the same process to some bigger numbers (and note that 0 does not behave like the other digits):


n=59049

digsum(1,59049) = 29648 (50.21%)
digsum(2,59049) = 19790 (33.51%)
digsum(3,59049) = 14901 (25.23%)
digsum(4,59049) = 11956 (20.25%)
digsum(5,59049) = 9970 (16.88%)
digsum(6,59049) = 8550 (14.48%)
digsum(7,59049) = 7539 (12.77%)
digsum(8,59049) = 6672 (11.30%)
digsum(9,59049) = 6579 (11.14%)
digcount(0,59049) = 41

n=531441

digsum(1,531441) = 266065 (50.06%)
digsum(2,531441) = 177394 (33.38%)
digsum(3,531441) = 133128 (25.05%)
digsum(4,531441) = 106532 (20.05%)
digsum(5,531441) = 88815 (16.71%)
digsum(6,531441) = 76224 (14.34%)
digsum(7,531441) = 66661 (12.54%)
digsum(8,531441) = 59320 (11.16%)
digsum(9,531441) = 53928 (10.15%)
digcount(0,531441) = 62

n=4782969

digsum(1,4782969) = 2392219 (50.02%)
digsum(2,4782969) = 1595000 (33.35%)
digsum(3,4782969) = 1196370 (25.01%)
digsum(4,4782969) = 957300 (20.01%)
digsum(5,4782969) = 797700 (16.68%)
digsum(6,4782969) = 683850 (14.30%)
digsum(7,4782969) = 598444 (12.51%)
digsum(8,4782969) = 531944 (11.12%)
digsum(9,4782969) = 480870 (10.05%)
digcount(0,4782969) = 66

Yes, the pattern’s getting stronger. Let’s try even bigger numbers:


n=43046721

digsum(1,43046721) = 21525521 (50.01%)
digsum(2,43046721) = 14350754 (33.34%)
digsum(3,43046721) = 10763496 (25.00%)
digsum(4,43046721) = 8610980 (20.00%)
digsum(5,43046721) = 7175955 (16.67%)
digsum(6,43046721) = 6150924 (14.29%)
digsum(7,43046721) = 5382167 (12.50%)
digsum(8,43046721) = 4784232 (11.11%)
digsum(9,43046721) = 4306257 (10.00%)
digcount(0,43046721) = 86

n=387420489

digsum(1,387420489) = 193716365 (50.00%)
digsum(2,387420489) = 129145522 (33.33%)
digsum(3,387420489) = 96859980 (25.00%)
digsum(4,387420489) = 77488588 (20.00%)
digsum(5,387420489) = 64574220 (16.67%)
digsum(6,387420489) = 55349742 (14.29%)
digsum(7,387420489) = 48431250 (12.50%)
digsum(8,387420489) = 43050264 (11.11%)
digsum(9,387420489) = 38748357 (10.00%)
digcount(0,387420489) = 95

To the given precision, the sum of 1s is 1/2 of n; the sum of 2s is 1/3; the sum of 3 is 1/4; and the sum of 4s is 1/5. It looks as though the sum of a given digit d → 1/(d+1) of n as n → ∞. But why? My mathematical intuition is bad, so it took me a while to see what some people will see in a flash. To see what’s going on, let’s go back to the all-base representations of 100:


100 = 1100100 in base 2; 10201 in base 3; 1210 in base 4; 400 in base 5; 244 in base 6; 202 in base 7; 144 in base 8; 121 in base 9; 100 in b10; 91 in b11; 84 in b12; 79 in b13; 72 in b14; 6A in b15; 64 in b16; 5F in b17; 5A in b18; 55 in b19; 50 in b20; 4G in b21; 4C in b22; 48 in b23; 44 in b24; 40 in b25; 3M in b26; 3J in b27; 3G in b28; 3D in b29; 3A in b30; 37 in b31; 34 in b32; 31 in b33; 2W in b34; 2U in b35; 2S in b36; 2Q in b37; 2O in b38; 2M in b39; 2K in b40; 2I in b41;
2G in b42; 2E in b43; 2C in b44; 2A in b45; 28 in b46; 26 in b47; 24 in b48; 22 in b49; 20 in b50; 1[49] in b51; 1[48] in b52; 1[47] in b53; 1[46] in b54; 1[45] in b55; 1[44] in b56; 1[43] in b57; 1[42] in b58; 1[41] in b59; 1[40] in b60; 1[39] in b61; 1[38] in b62; 1[37] in b63; 1[36] in b64; 1Z in b65; 1Y in b66; 1X in b67; 1W in b68; 1V in b69; 1U in b70; 1T in b71; 1S in b72; 1R in b73; 1Q in b74; 1P in b75; 1O in b76; 1N in b77; 1M in b78; 1L in b79; 1K in b80; 1J in b81
; 1I in b82; 1H in b83; 1G in b84; 1F in b85; 1E in b86; 1D in b87; 1C in b88; 1B in b89; 1A in b90; 19 in b91; 18 in b92; 17 in b93; 16 in b94; 15 in b95; 14 in b96; 13 in b97; 12 in b98; 11 in b99

When the base b is higher than half of 100, the representations of 100 consist of a digit 1 followed by another digit. Half of a hundred = 50, therefore 100 in base 10 = 1[49] in b51, 1[48] in b52, 1[47] in b53, 1[46] in b54, 1[45] in b55, 1[44] in b56, 1[43] in b57, 1[42] in b58, 1[41] in b59… If you take binary and so on into account, 1 is the first digit of slightly over half the representations of 100. And 1 also occurs in other positions. Therefore digsum(1,100,b=2..99) > 50. As the number n gets larger and larger, the contribution of leading 1s in bases b > n/2 begins to swamp the contributions of 1s in other positions, therefore digsum(1,n) → 1/2 of n as n → ∞.

And what about 2s and 3s? Similar reasoning applies. One hundred has a leading digit of 2 in bases b where b > 1/3 of 100 and b <= 1/2 of 100. So 100 = 2W in b34, 2U in b35, 2S in b36, 2Q in b37, 2O in b38… In other words, roughly 1/2 – 1/3 of the representations of 100 have a leading 2. Now, 1/2 – 1/3 = 3/6 – 2/6 = 1/6 and 1/6 * 2 = 1/3 (i.e., 1/6 of the representations contribute a leading 2 to the sum of 2s). Therefore the all-base digsum(2,n) → 1/3 of n as n → ∞. Next, one hundred has a leading digit of 3 in bases b where b > 1/4 of 100 and b <= 1/3. So 100 = 3M in b26, 3J in b27, 3G in b28, 3D in b29, 3A in b30… Now, 1/3 – 1/4 = 4/12 – 3/12 = 1/12 and 1/12 * 3 = 1/4. Therefore the all-base digsum(3,n) → 1/4 of n as n → ∞.

And so on.

B a Pal

by in Base Behavior, Binary numbers, Integer sequences, Mathematics, Palindromic numbers and tagged , , , , , , , , , , | Leave a comment

As a keyly committed core component of the counter-cultural community (I wish!), I like to post especially edgy and esoteric material to Overlord In Terms of Core Issues Around Maximal Engagement with Key Notions of the Über-Feral on the 23rd of each month. And today I may be posting the especially edgiest and esoterickest material ever dot dot dot

After all, this entry at the Online Encyclopedia of Integer Sequences is about numbers that are palindromes in two particularly pertinent bases:

A060792 Numbers that are palindromic in bases 2 and 3.

0, 1, 6643, 1422773, 5415589, 90396755477, 381920985378904469, 1922624336133018996235, 2004595370006815987563563, 8022581057533823761829436662099, 392629621582222667733213907054116073, 32456836304775204439912231201966254787, 428027336071597254024922793107218595973 (A060792 at OEIS, with more entries)

And here are the underlying palindromes:

0: 0 ↔ 0
1: 1 ↔ 1
6643: 1100111110011 ↔ 100010001
1422773: 101011011010110110101 ↔ 2200021200022
5415589: 10100101010001010100101 ↔ 101012010210101
90396755477: 1010100001100000100010000011000010101 ↔ 22122022220102222022122
381920985378904469: 10101001100110110110001110011011001110001101101100110010101 ↔ 2112200222001222121212221002220022112
1922624336133018996235: 11010000011100111000101110001110011011001110001110100011100111000001011 ↔
122120102102011212112010211212110201201021221
2004595370006815987563563: 110101000011111010101010100101111011110111011110111101001010101010111110000101011 ↔ 221010112100202002120002212200021200202001211010122
8022581057533823761829436662099: 1100101010000100101101110000011011011111111011000011100001101111111101101100000111011010010000101010011 ↔ 21000020210011222122220212010000100001021202222122211001202000012
392629621582222667733213907054116073: 10010111001111000100010100010100000011011011000101011011100000111011010100011011011000000101000101000100011110011101001 ↔ 122102120011102000101101000002010021111120010200000101101000201110021201221
32456836304775204439912231201966254787: 11000011010101111010110010100010010011011010101001101000001000100010000010110010101011011001001000101001101011110101011000011 ↔ 1222100201002211120110022121002012121101011212102001212200110211122001020012221
428027336071597254024922793107218595973: 101000010000000110001000011111100101011110011100001110100011100010001110001011100001110011110101001111110000100011000000010000101 ↔ 222001200110022102121001000200200202022111220202002002000100121201220011002100222

Binary Babushkas

by in Base Behavior, Binary numbers, Integer sequences, Mathematics and tagged , , , , , , , , , , , , , , , , , , , , , , , | Leave a comment

What’s the connection between grandmothers and this set of numbers?


1, 2, 6, 12, 44, 92, 184, 1208, 1256, 4792, 9912, 19832, 39664, 563952, 576464, 4496112, 4499184, 17996528, 17997488, 143972080, 145057520, 145070832, 294967024, 589944560...

To take the first step towards the answer, you need to put the numbers into binary:


1, 10, 110, 1100, 101100, 1011100, 10111000, 10010111000, 10011101000, 1001010111000, 10011010111000, 100110101111000, 1001101011110000, 10001001101011110000, 10001100101111010000, 10001001001101011110000, 10001001010011011110000, 1000100101001101011110000, 1000100101001111010110000, 1000100101001101011011110000, 1000101001010110011011110000, 1000101001011001101011110000, 10001100101001101011011110000, 100011001010011101011011110000...

The second step is compare those binary numbers with these binary numbers, which represent 1 to 30:


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

To see what’s going on, take the first five numbers from each set:


• 1, 10, 110, 1100, 101100...
• 1, 10, 11, 100, 101...

What’s going on? If you look, you can see the n-th binary number of set 1 contains the digits of all binary numbers <= n in set 2. For example, 101100 is the 5th binary number in set 1, so it contains the digits of the binary numbers 1 to 5:


101100 ← 1
101100 ← 10
101100 ← 11
101100 ← 100
101100 ← 101

Now try 1256 = 10,011,101,000, the ninth number in set 1. It contains all the binary numbers from 1 to 1001:


10011101000 ← 1 (n=1)
10011101000 ← 10 (n=2)
10011101000 ← 11 (n=3)
10011101000 ← 100 (n=4)
10011101000 ← 101 (n=5)
10011101000 ← 110 (n=6)
10011101000 ← 111 (n=7)
10011101000 ← 1000 (n=8)
10011101000 ← 1001 (n=9)

But where do grandmothers come in? They come in via this famous toy:

Nested doll or Russian doll

It’s called a Russian doll and the way all the smaller dolls pack inside the largest doll reminds me of the way all the smaller numbers 1 to 1010 pack into 1001010111000. But in the Russian language, as you might expect, Russian dolls aren’t called Russian dolls. Instead, they’re called matryoshki (матрёшки, singular матрёшка), meaning “little matrons”. However, there’s a mistaken idea in English that in Russian they’re called babushka dolls, from Russian бабушка, babuška, meaning “grandmother”. And that’s what I thought, until I did a little research.

But the mistake is there, so I’ll call these babushka numbers or grandmother numbers:


1, 2, 6, 12, 44, 92, 184, 1208, 1256, 4792, 9912, 19832, 39664, 563952, 576464, 4496112, 4499184, 17996528, 17997488, 143972080, 145057520, 145070832, 294967024, 589944560...

They’re sequence A261467 at the Online Encyclopedia of Integer Sequences. They go on for ever, but the biggest known so far is 589,944,560 = 100,011,001,010,011,101,011,011,110,000 in binary. And here is that binary babushka with its binary babies:


100011001010011101011011110000 ← 1 (n=1)
100011001010011101011011110000 ← 10 (n=2)
100011001010011101011011110000 ← 11 (n=3)
100011001010011101011011110000 ← 100 (n=4)
100011001010011101011011110000 ← 101 (n=5)
100011001010011101011011110000 ← 110 (n=6)
100011001010011101011011110000 ← 111 (n=7)
100011001010011101011011110000 ← 1000 (n=8)
100011001010011101011011110000 ← 1001 (n=9)
100011001010011101011011110000 ← 1010 (n=10)
100011001010011101011011110000 ← 1011 (n=11)
100011001010011101011011110000 ← 1100 (n=12)
100011001010011101011011110000 ← 1101 (n=13)
100011001010011101011011110000 ← 1110 (n=14)
100011001010011101011011110000 ← 1111 (n=15)
100011001010011101011011110000 ← 10000 (n=16)
100011001010011101011011110000 ← 10001 (n=17)
100011001010011101011011110000 ← 10010 (n=18)
100011001010011101011011110000 ← 10011 (n=19)
100011001010011101011011110000 ← 10100 (n=20)
100011001010011101011011110000 ← 10101 (n=21)
100011001010011101011011110000 ← 10110 (n=22)
100011001010011101011011110000 ← 10111 (n=23)
100011001010011101011011110000 ← 11000 (n=24)
100011001010011101011011110000 ← 11001 (n=25)
100011001010011101011011110000 ← 11010 (n=26)
100011001010011101011011110000 ← 11011 (n=27)
100011001010011101011011110000 ← 11100 (n=28)
100011001010011101011011110000 ← 11101 (n=29)
100011001010011101011011110000 ← 11110 (n=30)

Babushka numbers exist in higher bases, of course. Here are the first thirteen in base 3 or ternary:


1 contains 1 (c=1) (n=1)
12 contains 1, 2 (c=2) (n=5)
102 contains 1, 2, 10 (c=3) (n=11)
1102 contains 1, 2, 10, 11 (c=4) (n=38)
10112 contains 1, 2, 10, 11, 12 (c=5) (n=95)
101120 contains 1, 2, 10, 11, 12, 20 (c=6) (n=285)
1021120 contains 1, 2, 10, 11, 12, 20, 21 (c=7) (n=933)
10211220 contains 1, 2, 10, 11, 12, 20, 21, 22 (c=8) (n=2805)
100211220 contains 1, 2, 10, 11, 12, 20, 21, 22, 100 (c=9) (n=7179)
10021011220 contains 1, 2, 10, 11, 12, 20, 21, 22, 100, 101 (c=10) (n=64284)
1001010211220 contains 1, 2, 10, 11, 12, 20, 21, 22, 100, 101, 102 (c=11) (n=553929)
1001011021220 contains 1, 2, 10, 11, 12, 20, 21, 22, 100, 101, 102, 110 (c=12) (n=554253)
10010111021220 contains 1, 2, 10, 11, 12, 20, 21, 22, 100, 101, 102, 110, 111 (c=13) (n=1663062)

Look at 1,001,010,211,220 (n=553929) and 1,001,011,021,220 (n=554253). They have the same number of digits, but the babushka 1,001,011,021,220 manages to pack in one more baby:


1001010211220 contains 1, 2, 10, 11, 12, 20, 21, 22, 100, 101, 102 (c=11) (n=553929)
1001011021220 contains 1, 2, 10, 11, 12, 20, 21, 22, 100, 101, 102, 110 (c=12) (n=554253)

That happens in binary too:


10010111000 contains 1, 10, 11, 100, 101, 110, 111, 1000, 1001 (c=9) (n=1208)
10011101000 contains 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010 (c=10) (n=1256)

What happens in higher bases? Watch this space.

Pi and By

by in √2, Base Behavior, Binary numbers, Integer sequences, Irrational numbers, π, Mathematics, Pi, Square root of 2 and tagged , , , , , , , , , , , , , , , , , , , | Leave a comment

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.

Block’n’Role

by in Base Behavior, Binary numbers, Integer sequences, Mathematics, Narcissistic numbers and tagged , , , , , , , , , , , , , | Leave a comment

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.

Weight-Botchers

by in Base Behavior, Binary numbers, Mathematics, Powers and tagged , , , , , , , , , , , , , , , , , , , , , | Leave a comment

Suppose you have a balance scale and four weights of 1 unit, 2 units, 4 units and 8 units. How many different weights can you match? If you know binary arithmetic, it’s easy to see that you can match any weight up to fifteen units inclusive. With the object in the left-hand pan of the scale and the weights in the right-hand pan, these are the matches:

01 = 1
02 = 2
03 = 2+1
04 = 4
05 = 4+1
06 = 4+2
07 = 4+2+1
08 = 8
09 = 8+1
10 = 8+2
11 = 8+2+1
12 = 8+4
13 = 8+4+1
14 = 8+4+2
15 = 8+4+2+1

Balance scale


The weights that sum to n match the 1s in the digits of n in binary.

01 = 0001 in binary
02 = 0010 = 2
03 = 0011 = 2+1
04 = 0100 = 4
05 = 0101 = 4+1
06 = 0110 = 4+2
07 = 0111 = 4+2+1
08 = 1000 = 8
09 = 1001 = 8+1
10 = 1010 = 8+2
11 = 1011 = 8+2+1
12 = 1100 = 8+4
13 = 1101 = 8+4+1
14 = 1110 = 8+4+2
15 = 1111 = 8+4+2+1

But there’s another set of four weights that will match anything from 1 unit to 40 units. Instead of using powers of 2, you use powers of 3: 1, 3, 9, 27. But how would you match an object weighing 2 units using these weights? Simple. You put the object in the left-hand scale, the 3-weight in the right-hand scale, and then add the 1-weight to the left-hand scale. In other words, 2 = 3-1. Similarly, 5 = 9-3-1, 6 = 9-3 and 7 = 9-3+1. When the power of 3 is positive, it’s in the right-hand pan; when it’s negative, it’s in the left-hand pan.

This system is actually based on base 3 or ternary, which uses three digits, 0, 1 and 2. However, the relationship between ternary numbers and the sums of positive and negative powers of 3 is more complicated than the relationship between binary numbers and sums of purely positive powers of 2. See if you can work out how to derive the sums in the middle from the ternary numbers on the right:

01 = 1 = 1 in ternary
02 = 3-1 = 2
03 = 3 = 10
04 = 3+1 = 11
05 = 9-3-1 = 12
06 = 9-3 = 20
07 = 9-3+1 = 21
08 = 9-1 = 22
09 = 9 = 100
10 = 9+1 = 101
11 = 9+3-1 = 102
12 = 9+3 = 110
13 = 9+3+1 = 111
14 = 27-9-3-1 = 112
15 = 27-9-3 = 120
16 = 27-9-3+1 = 121
17 = 27-9-1 = 122
18 = 27-9 = 200
19 = 27-9+1 = 201
20 = 27-9+3-1 = 202
21 = 27-9+3 = 210
22 = 27-9+3+1 = 211
23 = 27-3-1 = 212
24 = 27-3 = 220
25 = 27-3+1 = 221
26 = 27-1 = 222
27 = 27 = 1000
28 = 27+1 = 1001
29 = 27+3-1 = 1002
30 = 27+3 = 1010
31 = 27+3+1 = 1011
32 = 27+9-3-1 = 1012
33 = 27+9-3 = 1020
34 = 27+9-3+1 = 1021
35 = 27+9-1 = 1022
36 = 27+9 = 1100
37 = 27+9+1 = 1101
38 = 27+9+3-1 = 1102
39 = 27+9+3 = 1110
40 = 27+9+3+1 = 1111

To begin understanding the sums, consider those ternary numbers containing only 1s and 0s, like n = 1011[3], which equals 31 in decimal. The sum of powers is straightforward, because all of them are positive and they’re easy to work out from the digits of n in ternary: 1011 = 1*3^3 + 0*3^2 + 1*3^1 + 1*3^0 = 27+3+1. Now consider n = 222[3] = 26 in decimal. Just as a decimal number consisting entirely of 9s is always 1 less than a power of 10, so a ternary number consisting entirely of 2s is always 1 less than a power of three:

999 = 1000 - 1 = 10^3 - 1 (decimal)
222 = 1000[3] - 1 (ternary) = 26 = 27-1 = 3^3 - 1 (decimal)

If a ternary number contains only 2s and is d digits long, it will be equal to 3^d – 1. But what about numbers containing a mixture of 2s, 1s and 0s? Well, all ternary numbers containing at least one 2 will have a negative power of 3 in the sum. You can work out the sum by using the following algorithm. Suppose the number is five digits long and the rightmost digit is digit #1 and the leftmost is digit #5:

01. i = 1, sum = 0, extra = 0, posi = true.
02. if posi = false, goto step 07.
03. if digit #i = 0, sum = sum + 0.
04. if digit #i = 1, sum = sum + 3^(i-1).
05. if digit #i = 2, sum = sum - 3^(i-1), extra = 3^5, posi = false.
06. goto step 10.
07. if digit #i = 0, sum = sum + 3^(i-1), extra = 0, posi = true.
08. if digit #i = 1, sum = sum - 3^(i-1).
09. if digit #i = 2, sum = sum + 0.
10. i = i+1. if i <= 5, goto step 2.
11. print sum + extra.

As the number of weights grows, the advantages of base 3 get bigger:

With 02 weights, base 3 reaches 04 and base 2 reaches 3: 04-3 = 1.
With 03 weights, base 3 reaches 13 and base 2 reaches 7: 13-7 = 6.
With 04 weights, 000040 - 0015 = 000025
With 05 weights, 000121 - 0031 = 000090
With 06 weights, 000364 - 0063 = 000301
With 07 weights, 001093 - 0127 = 000966
With 08 weights, 003280 - 0255 = 003025
With 09 weights, 009841 - 0511 = 009330
With 10 weights, 029524 - 1023 = 028501
With 11 weights, 088573 - 2047 = 086526
With 12 weights, 265720 - 4095 = 261625...

But what about base 4, or quaternary? With four weights of 1, 4, 16 and 64, representing powers of 4 from 4^0 to 4^3, you should be able to weigh objects from 1 to 85 units using sums of positive and negative powers. In fact, some weights can’t be matched. As you can see below, if n in base 4 contains a 2, it usually can’t be represented as a sum of positive and negative powers of 4 (one exception is 23 = 2*4 + 3 = 11 in base 10). Certain other numbers are also impossible to represent as that kind of sum:

1 = 1 ← 1
2 has no sum = 2
3 = 4-1 ← 3
4 = 4 ← 10 in base 4
5 = 4+1 ← 11 in base 4
6 has no sum = 12 in base 4
7 has no sum = 13
8 has no sum = 20
9 has no sum = 21
10 has no sum = 22
11 = 16-4-1 ← 23
12 = 16-4 ← 30
13 = 16-4+1 ← 31
14 has no sum = 32
15 = 16-1 ← 33
16 = 16 ← 100
17 = 16+1 ← 101
18 has no sum = 102
19 = 16+4-1 ← 103
20 = 16+4 ← 110
21 = 16+4+1 ← 111
22 has no sum = 112
23 has no sum = 113
24 has no sum = 120
25 has no sum = 121
26 has no sum = 122
27 has no sum = 123
[...]

With a more complicated balance scale, it’s possible to use weights representing powers of base 4 and base 5 (use two pans on each arm of the scale instead of one, placing the extra pan at the midpoint of the arm). But with a standard balance scale, base 3 is the champion. However, there is a way to do slightly better than standard base 3. You do it by botching the weights. Suppose you have four weights of 1, 4, 10 and 28 (representing 1, 3+1, 9+1 and 27+1). There are some weights n you can’t match, but because you can match n-1 and n+1, you know what these unmatchable weights are. Accordingly, while weights of 1, 3, 9 and 27 can measure objects up to 40 units, weights of 1, 4, 10 and 28 can measure objects up to 43 units:

1 = 1 ← 1
2 has no sum = 2
3 = 4-1 ← 10 in base 3
4 = 4 ← 11 in base 3
5 = 4+1 ← 12 in base 3
6 = 10-4 ← 20
7 = 10-4+1 ← 21
8 has no sum = 22
9 = 10-1 ← 100
10 = 10 ← 101
11 = 10+1 ← 102
12 has no sum = 110
13 = 10+4-1 ← 111
14 = 10+4 ← 112
15 = 10+4+1 ← 120
16 has no sum = 121
17 = 28-10-1 ← 122
18 = 28-10 ← 200
19 = 28-10+1 ← 201
20 has no sum = 202
21 = 28-10+4-1 ← 210
22 = 28-10+4 ← 211
23 = 28-4-1 ← 212
24 = 28-4 ← 220
25 = 28-4+1 ← 221
26 has no sum = 222
27 = 28-1 ← 1000
28 = 28 ← 1001
29 = 28+1 ← 1002
30 has no sum = 1010
31 = 28+4-1 ← 1011
32 = 28+4 ← 1012
33 = 28+4+1 ← 1020
34 = 28+10-4 ← 1021
35 = 28+10-4+1 ← 1022
36 has no sum = 1100
37 = 28+10-1 ← 1101
38 = 28+10 ← 1102
39 = 28+10+1 ← 1110
40 = has no sum = 1111*
41 = 28+10+4-1 ← 1112
42 = 28+10+4 ← 1120
43 = 28+10+4+1 ← 1121

*N.B. 40 = 82-28-10-4, i.e. has a sum when another botched weight, 82 = 3^4+1, is used.

Zequality Now

by in Base Behavior, Binary numbers, Integer sequences, Mathematics and tagged , , , , , , , , , , , , , , , , , , | Leave a comment

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

by in Base Behavior, Binary numbers, Integer sequences, Mathematics, Narcissistic numbers and tagged , , , , , , , , , , , , , , , , , , , , | Leave a comment

“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)