Tag Archives: ternary

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.

An N-Finity

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

10111 in base 2
212 in base 3
113 in base 4
43 in base 5
35 in base 6
32 in base 7
27 in base 8
25 in base 9
23 in base 10
21 in base 11
1B in base 12
1A in base 13
19 in base 14
18 in base 15
17 in base 16
16 in base 17
15 in base 18
14 in base 19
13 in base 20
12 in base 21
11 in base 22
10 in base 23
N in all bases >= 24

√23 = 4.79583152331…

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)

Square on a Three String

by in Base Behavior, φ, Magic squares, Mathematics and tagged , , , , , , , , , , , , , , , , , , , , , , , , , , | Leave a comment

222 A.D. was the year in which the Emperor Heliogabalus was assassinated by his own soldiers. Exactly 1666 years later, the Anglo-Dutch classicist Sir Lawrence Alma-Tadema exhibited his painting The Roses of Heliogabalus (1888). I suggested in “Roses Are Golden” that Alma-Tadema must have chosen the year as deliberately as he chose the dimensions of his canvas, which, at 52″ x 84 1/8“, is an excellent approximation to the golden ratio.

But did Alma-Tadema know that lines at 0º and 222º divide a circle in the golden ratio? He could easily have done, just as he could easily have known that 222 precedes the 48th prime, 223. But it is highly unlikely that he knew that 223 yields a magic square whose columns, rows and diagonals all sum to 222. To create the square, simply list the 222 multiples of the reciprocal 1/223 in base 3, or ternary. The digits of the reciprocal repeat after exactly 222 digits and its multiples begin and end like this:

001/223 = 0.00001002102101021212111012022211122022... in base 3
002/223 = 0.00002011211202120201222101122200021121...
003/223 = 0.00010021021010212121110120222111220221...
004/223 = 0.00011100200112011110221210022100120020...
005/223 = 0.00012110002220110100102222122012012120...

[...]

218/223 = 0.22210112220002112122120000100210210102... in base 3
219/223 = 0.22211122022110211112001012200122102202...
220/223 = 0.22212201201212010101112102000111002001...
221/223 = 0.22220211011020102021000121100022201101...
222/223 = 0.22221220120121201010111210200011100200...

Each column, row and diagonal of ternary digits sums to 222. Here is the full n/223 square represented with 0s in grey, 1s in white and 2s in red:

(Click for larger)

It isn’t difficult to see that the white squares are mirror-symmetrical on a horizontal axis. Here is the symmetrical pattern rotated by 90º:

(Click for larger)

But why should the 1s be symmetrical? This isn’t something special to 1/223, because it happens with prime reciprocals like 1/7 too:

1/7 = 0.010212... in base 3
2/7 = 0.021201...
3/7 = 0.102120...
4/7 = 0.120102...
5/7 = 0.201021...
6/7 = 0.212010...

And you can notice something else: 0s mirror 2s and 2s mirror 0s. A related pattern appears in base 10:

1/7 = 0.142857...
2/7 = 0.285714...
3/7 = 0.428571...
4/7 = 0.571428...
5/7 = 0.714285...
6/7 = 0.857142...

The digit 1 in the decimal digits of n/7 corresponds to the digit 8 in the decimal digits of (7-n)/7; 4 corresponds to 5; 2 corresponds to 7; 8 corresponds to 1; 5 corresponds to 4; and 7 corresponds to 2. In short, if you’re given the digits d1 of n/7, you know the digits d2 of (n-7)/7 by the rule d2 = 9-d1.

Why does that happen? Examine these sums:

 1/7 = 0.142857142857142857142857142857142857142857...
+6/7 = 0.857142857142857142857142857142857142857142...
 7/7 = 0.999999999999999999999999999999999999999999... = 1.0

 2/7 = 0.285714285714285714285714285714285714285714...
+5/7 = 0.714285714285714285714285714285714285714285...
 7/7 = 0.999999999999999999999999999999999999999999... = 1.0

 3/7 = 0.428571428571428571428571428571428571428571...
+4/7 = 0.571428571428571428571428571428571428571428...
 7/7 = 0.999999999999999999999999999999999999999999... = 1.0

And here are the same sums in ternary (where the first seven integers are 1, 2, 10, 11, 12, 20, 21):

  1/21 = 0.010212010212010212010212010212010212010212...
+20/21 = 0.212010212010212010212010212010212010212010...
 21/21 = 0.222222222222222222222222222222222222222222... = 1.0

  2/21 = 0.021201021201021201021201021201021201021201...
+12/21 = 0.201021201021201021201021201021201021201021...
 21/21 = 0.222222222222222222222222222222222222222222... = 1.0

 10/21 = 0.102120102120102120102120102120102120102120...
+11/21 = 0.120102120102120102120102120102120102120102...
 21/21 = 0.222222222222222222222222222222222222222222... = 1.0

Accordingly, in base b with the prime p, the digits d1 of n/p correspond to the digits (p-n)/p by the rule d2 = (b-1)-d1. This explains why the 1s mirror themselves in ternary: 1 = 2-1 = (3-1)-1. In base 5, the 2s mirror themselves by the rule 2 = 4-2 = (5-1) – 2. In all odd bases, some digit will mirror itself; in all even bases, no digit will. The mirror-digit will be equal to (b-1)/2, which is always an integer when b is odd, but never an integer when b is even.

Here are some more examples of the symmetrical patterns found in odd bases:

Patterns of 1s in 1/19 in base 3

Patterns of 6s in 1/19 in base 13

Patterns of 7s in 1/19 in base 15

Elsewhere other-posted:

• Roses Are Golden — more on The Roses of Heliogabalus (1888)
• Three Is The Key — more on the 1/223 square

T4K1NG S3LF13S

by in Base Behavior, Binary numbers, Integer sequences, Mathematics and tagged , , , , , , , , , , , , , , , , , , , , , , , | 2 Comments

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 → 21322314 → 21322314…

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

1 → 11 → 101 → 10101 → 100111 → 1001001 → 1000111 → 1101001 → 1101001… (b=2) (1101001[2] = 105 in base 10)
1 → 11 → 21 → 1112 → 10112 → 1010112 → 2011112 → 1011122 → 1011122… (b=3) (1011122[3] = 854 in base 10)
1 → 11 → 21 → 1112 → 3112 → 211213 → 312213 → 212223 → 1110213 → 101011213 → 201111213 → 101112213 → 101112213… (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:

22 → 22… (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

Block n Rule

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

One of my favourite integer sequences uses the formula n(i) = n(i-1) + digsum(n(i-1)), where digsum(n) sums the digits of n. In base 10, it goes like this:

1, 2, 4, 8, 16, 23, 28, 38, 49, 62, 70, 77, 91, 101, 103, 107, 115, 122, 127, 137, 148, 161, 169, 185, 199, 218, 229, 242, 250, 257, 271, 281, 292, 305, 313, 320, 325, 335, 346, 359, 376, 392, 406, 416, 427, 440, 448, 464, 478, 497, 517, 530, 538, 554, 568, 587, 607, 620, 628, 644, 658, 677, 697, 719, 736, 752, 766, 785, 805, 818, 835, 851, 865, 884, 904, 917, 934, 950, 964, 983, 1003…

Another interesting sequence uses the formula n(i) = n(i-1) + digprod(n(i-1)), where digprod(n) multiplies the digits of n (excluding 0). In base 10, it goes like this:

1, 2, 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, 138, 162, 174, 202, 206, 218, 234, 258, 338, 410, 414, 430, 442, 474, 586, 826, 922, 958, 1318, 1342, 1366, 1474, 1586, 1826, 1922, 1958, 2318, 2366, 2582, 2742, 2854, 3174, 3258, 3498, 4362, 4506, 4626, 4914, 5058, 5258, 5658, 6858, 8778, 11914, 11950, 11995…

You can apply these formulae in other bases and it’s trivially obvious that the sequences rise most slowly in base 2, because you’re never summing or multiplying anything but the digit 1. However, there is a sequence for which base 2 is by far the best performer. It has the formula n(i) = n(i-1) + blockmult(n(i-1)), where blockmult(n) counts the lengths of distinct blocks of the same digit, including 0, then multiplies those lengths together. For example:

blockmult(3,b=2) = blockmult(11) = 2
blockmult(28,b=2) = blockmult(11100) = 3 * 2 = 6
blockmult(51,b=2) = blockmult(110011) = 2 * 2 * 2 = 8
blockmult(140,b=2) = blockmult(10001100) = 1 * 3 * 2 * 2 = 12
blockmult(202867,b=2) = blockmult(110001100001110011) = 2 * 3 * 2 * 4 * 3 * 2 * 2 = 576

The full sequence begins like this (numbers are represented in base 10, but the formula is being applied to their representations in binary):

1, 2, 3, 5, 6, 8, 11, 13, 15, 19, 23, 26, 28, 34, 37, 39, 45, 47, 51, 59, 65, 70, 76, 84, 86, 88, 94, 98, 104, 110, 116, 122, 126, 132, 140, 152, 164, 168, 171, 173, 175, 179, 187, 193, 203, 211, 219, 227, 245, 249, 259, 271, 287, 302, 308, 316, 332, 340, 342, 344, 350, 354, 360, 366, 372, 378, 382, 388, 404, 412, 436, 444, 460, 484, 500, 510, 518, 530, 538, 546, 555, 561, 579, 595, 603, 611, 635, 651, 657, 663, 669, 675, 681…

In higher bases, it rises much more slowly. This is base 3:

1, 2, 3, 4, 6, 7, 8, 10, 11, 12, 14, 16, 17, 19, 20, 21, 22, 24, 26, 29, 31, 33, 34, 35, 37, 39, 42, 44, 48, 49, 51, 53, 56, 58, 60, 61, 62, 64, 65, 66, 68, 70, 71, 73, 75, 77, 79, 82, 85, 89, 93, 95, 97, 98, 100, 101, 102, 103, 105, 107, 110, 114, 116, 120, 124, 127, 129, 131, 133, 137, 139, 141, 142, 143, 145, 146, 147, 149, 151, 152, 154, 156, 158, 160, 163…

And this is base 10:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 90…

Note how, in bases 3 and 10, blockmult(n) often equals 1. In base 3, the sequence contains [141, 142, 143, 145]:

blockmult(141,b=3) = blockmult(12020) = 1 * 1 * 1 * 1 = 1
blockmult(142,b=3) = blockmult(12021) = 1 * 1 * 1 * 1 = 1
blockmult(143,b=3) = blockmult(12022) = 1 * 1 * 1 * 2 = 2

The formula also returns 1 much further along the sequence in base 3. For example, the 573809th number in the sequence, or n(573809), is 5775037 and blockmult(5775037) = blockmult(101212101212021) = 1^15 = 1. But in base 2, blockmult(n) = 1 is very rare. It happens three times at the beginning of the sequence:

1, 2, 3, 5, 6, 8, 11…

After that, I haven’t found any more examples of blockmult(n) = 1, although blockmult(n) = 2 occurs regularly. For example,

blockmult(n(100723)) = blockmult(44739241) = blockmult(10101010101010101010101001) = 2
blockmult(n(100724)) = blockmult(44739243) = blockmult(10101010101010101010101011) = 2
blockmult(n(100725)) = blockmult(44739245) = blockmult(10101010101010101010101101) = 2

Does the sequence in base 2 return another example of blockmult(n) = 1? The odds seem against it. For any given number of digits in base 2, there is only one number for which blockmult(n) = 1. For example: 1, 10, 101, 1010, 10101, 101010, 1010101… As the sequence increases, the percentage of these numbers becomes smaller and smaller. But the sequence is infinite, so who knows what happens in the end? Perhaps blockmult(n) = 1 occurs infinitely often.