Digital Rodeo

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

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

Add this digit-count to 3:

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

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

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

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

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

And the sequence develops like this:

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

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

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

Next come these:

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

The sequence develops like this:

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

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

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

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

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

As n gets larger, the difference grows dramatically:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

All-Base Graph

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


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

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

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

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

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

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

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

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

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

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

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

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

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

Power Trip

Here are the first few powers of 2:

2 = 1 * 2
4 = 2 * 2
8 = 4 * 2
16 = 8 * 2
32 = 16 * 2
64 = 32 * 2
128 = 64 * 2
256 = 128 * 2
512 = 256 * 2
1024 = 512 * 2
2048 = 1024 * 2
4096 = 2048 * 2
8192 = 4096 * 2
16384 = 8192 * 2
32768 = 16384 * 2
65536 = 32768 * 2
131072 = 65536 * 2
262144 = 131072 * 2
524288 = 262144 * 2
1048576 = 524288 * 2
2097152 = 1048576 * 2
4194304 = 2097152 * 2
8388608 = 4194304 * 2
16777216 = 8388608 * 2
33554432 = 16777216 * 2
67108864 = 33554432 * 2…

As you can see, it’s a one-way power-trip: the numbers simply get larger. But what happens if you delete the digit 0 whenever it appears in a result? For example, 512 * 2 = 1024, which becomes 124. If you apply this rule, the sequence looks like this:

2 * 2 = 4
4 * 2 = 8
8 * 2 = 16
16 * 2 = 32
32 * 2 = 64
64 * 2 = 128
128 * 2 = 256
256 * 2 = 512
512 * 2 = 1024 → 124
124 * 2 = 248
248 * 2 = 496
496 * 2 = 992
992 * 2 = 1984
1984 * 2 = 3968
3968 * 2 = 7936
7936 * 2 = 15872
15872 * 2 = 31744
31744 * 2 = 63488
63488 * 2 = 126976
126976 * 2 = 253952
253952 * 2 = 507904 → 5794
5794 * 2 = 11588
11588 * 2 = 23176
23176 * 2 = 46352
46352 * 2 = 92704 → 9274…

Is this a power-trip? Not quite: it’s a return trip, because the numbers can never grow beyond a certain size and the sequence falls into a loop. If the result 2n contains a zero, then zerodelete(2n) < n, so the sequence has an upper limit and a number will eventually occur twice. This happens at step 526 with 366784, which matches 366784 at step 490.

The rate at which we delete zeros can obviously be varied. Call it 1:z. The sequence above sets z = 1, so 1:z = 1:1. But what if z = 2, so that 1:z = 1:2? In other words, the procedure deletes every second zero. The first zero occurs when 1024 = 2 * 512, so 1024 is left as it is. The second zero occurs when 2 * 1024 = 2048, so 2048 becomes 248. When z = 2 and every second zero is deleted, the sequence begins like this:

1 * 2 = 2
2 * 2 = 4
4 * 2 = 8
8 * 2 = 16
16 * 2 = 32
32 * 2 = 64
64 * 2 = 128
128 * 2 = 256
256 * 2 = 512
512 * 2 = 1024 → 1024
1024 * 2 = 2048 → 248
248 * 2 = 496
496 * 2 = 992
992 * 2 = 1984
1984 * 2 = 3968
3968 * 2 = 7936
7936 * 2 = 15872
15872 * 2 = 31744
31744 * 2 = 63488
63488 * 2 = 126976
126976 * 2 = 253952
253952 * 2 = 507904 → 50794
50794 * 2 = 101588 → 101588
101588 * 2 = 203176 → 23176
23176 * 2 = 46352
46352 * 2 = 92704 → 92704
92704 * 2 = 185408 → 18548

This sequence also has a ceiling and repeats at step 9134 with 5458864, which matches 5458864 at step 4166. And what about the sequence in which z = 3 and every third zero is deleted? Does this have a ceiling or does the act of multiplying by 2 compensate for the slower removal of zeros?

In fact, it can’t do so. The larger 2n becomes, the more zeros it will tend to contain. If 2n is large enough to contain 3 zeros on average, the deletion of zeros will overpower multiplication by 2 and the sequence will not rise any higher. Therefore the sequence that deletes every third zero will eventually repeat, although I haven’t been able to discover the relevant number.

But this reasoning applies to any rate, 1:z, of zero-deletion. If z = 100 and every hundredth zero is deleted, numbers in the sequence will rise to the point at which 2n contains sufficient zeros on average to counteract multiplication by 2. The sequence will have a ceiling and will eventually repeat. If z = 10^100 or z = 10^(10^100) and every googolth or googolplexth zero is deleted, the same is true. For any rate, 1:z, at which zeros are deleted, the sequence n = zerodelete(2n,z) has an upper limit and will eventually repeat.

Spijit

The only two digits found in all standard bases are 1 and 0. But they behave quite differently. Suppose you take the integers 1 to 100 and compare the number of 1s and 0s in the representation of each integer, n, in bases 2 to n-1. For example, 10 would look like this:

1010 in base 2
101 in base 3
22 in base 4
20 in base 5
14 in base 6
13 in base 7
12 in base 8
11 in base 9

So there are nine 1s and four 0s. If you check 1 to 100 using this all-base function, the count of 1s goes like this:

1, 1, 2, 3, 5, 5, 8, 5, 9, 9, 11, 10, 15, 12, 14, 13, 15, 12, 17, 14, 20, 19, 20, 15, 23, 19, 22, 22, 25, 24, 31, 21, 25, 24, 24, 27, 33, 27, 31, 29, 34, 29, 36, 30, 34, 35, 34, 30, 40, 33, 36, 35, 38, 34, 42, 37, 43, 40, 41, 37, 48, 39, 42, 42, 44, 43, 48, 43, 47, 46, 51, 42, 53, 44, 48, 50, 51, 50, 55, 48, 59, 55, 55, 54, 64, 57, 57, 55, 60, 57, 68, 60, 64, 63, 64, 59, 68, 58, 61, 63.

And the count of 0s goes like this:

0, 1, 0, 2, 1, 2, 0, 4, 4, 4, 2, 5, 1, 2, 2, 7, 4, 8, 4, 7, 4, 3, 1, 8, 4, 4, 6, 8, 4, 7, 1, 10, 8, 7, 7, 12, 5, 6, 5, 10, 4, 8, 2, 6, 7, 4, 2, 12, 6, 9, 7, 8, 4, 11, 6, 10, 5, 4, 2, 12, 2, 3, 5, 14, 11, 13, 7, 10, 8, 11, 5, 17, 7, 8, 10, 10, 8, 10, 4, 13, 12, 10, 8, 16, 8, 7, 7, 12, 6, 14, 6, 8, 5, 4, 4, 16, 6, 10, 11, 15.

The bigger the numbers get, the bigger the discrepancies get. Sometimes the discrepancy is dramatic. For example, suppose you represented the prime 1014719 in bases 2 to 1014718. How 0s would there be? And how many 1s? There are exactly nine zeroes:

1014719 = 11110111101110111111 in base 2 = 1220112221012 in base 3 = 40B27B in base 12 = 1509CE in base 15 = 10[670] in base 1007.

But there are 507723 ones. The same procedure applied to the next integer, 1014720, yields 126 zeroes and 507713 ones. However, there is a way to see that 1s and 0s in the all-base representation are behaving in a similar way. To do this, imagine listing the individual digits of n in bases 2 to n-1 (or just base 2, if n <= 3). When the digits aren’t individual they look like this:

1 = 1 in base 2
2 = 10 in base 2
3 = 11 in base 2
4 = 100 in base 2; 11 in base 3
5 = 101 in base 2; 12 in base 3; 11 in base 4
6 = 110 in base 2; 20 in base 3; 12 in base 4; 11 in base 5
7 = 111 in base 2; 21 in base 3; 13 in base 4; 12 in base 5; 11 in base 6
8 = 1000 in base 2; 22 in base 3; 20 in base 4; 13 in base 5; 12 in base 6; 11 in base 7
9 = 1001 in base 2; 100 in base 3; 21 in base 4; 14 in base 5; 13 in base 6; 12 in base 7; 11 in base 8
10 = 1010 in base 2; 101 in base 3; 22 in base 4; 20 in base 5; 14 in base 6; 13 in base 7; 12 in base 8; 11 in base 9

So the list would look like this:

1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 2, 1, 1, 1, 1, 0, 2, 0, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 3, 1, 2, 1, 1, 1, 0, 0, 0, 2, 2, 2, 0, 1, 3, 1, 2, 1, 1, 1, 0, 0, 1, 1, 0, 0, 2, 1, 1, 4, 1, 3, 1, 2, 1, 1, 1, 0, 1, 0, 1, 0, 1, 2, 2, 2, 0, 1, 4, 1, 3, 1, 2, 1, 1

Suppose that these digits are compared against the squares of a counter-clockwise spiral on a rectangular grid. If the spiral digit is equal to 1, the square is filled in; if the spijit is not equal to 1, the square is left blank. The 1-spiral looks like this:
1spiral
Now try zero. If the spijit is equal to 0, the square is filled in; if not, the square is left blank. The 0-spiral looks like this:
0spiral
And here’s an animated gif of the n-spiral for n = 0..9:
animspiral