An N-Finity

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…

Advertisements

Block’n’Role

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

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


Here are a few famous decimal numbers in binary:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

And so on.

Weight-Botchers

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 can’t be represented as a sum of positive and negative powers of 4. Nor can certain other numbers:

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

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)

Oh My Guardian #5

‘We’re stepping out of a binary’ – celebrating the art of marginalized LGBT Muslims

[…] The show features artwork themed around issues of Islamophobia, racism and homophobia to “highlight the struggles common among contemporary Muslim queer, trans and gender non-conforming communities,” said co-curator and activist Yas Ahmed. — ‘We’re stepping out of a binary’, The Guardian, 22/i/2018.


Elsewhere other-accessible:

Oh My Guardian #1
Oh My Guardian #2
Oh My Guardian #3
Oh My Guardian #4
Reds under the Thread

T4K1NG S3LF13S

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

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

1

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

→ 11

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

→ 21

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

→ 1112

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

→ 3112

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

→ 211213

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

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

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

→ 21322314

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

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

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


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

1234567890 → 10111213141516171819 → 101111213141516171819 → 101211213141516171819 → 101112213141516171819

That final number is self-descriptive:

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

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

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


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

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

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

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

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

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

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

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

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


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

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

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

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

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

For Revver and Fevver

This shape reminds me of the feathers on an exotic bird:

feathers

(click or open in new window for full size)


feathers_anim

(animated version)


The shape is created by reversing the digits of a number, so you could say it involves revvers and fevvers. I discovered it when I was looking at the Halton sequence. It’s a sequence of fractions created according to a simple but interesting rule. The rule works like this: take n in base b, reverse it, and divide reverse(n) by the first power of b that is greater thann.

For example, suppose n = 6 and b = 2. In base 2, 6 = 110 and reverse(110) = 011 = 11 = 3. The first power of 2 that is greater than 6 is 2^3 or 8. Therefore, halton(6) in base 2 equals 3/8. Here is the same procedure applied to n = 1..20:

1: halton(1) = 1/10[2] → 1/2
2: halton(10) = 01/100[2] → 1/4
3: halton(11) = 11/100[2] → 3/4
4: halton(100) = 001/1000[2] → 1/8
5: halton(101) = 101/1000[2] → 5/8
6: halton(110) = 011/1000 → 3/8
7: halton(111) = 111/1000 → 7/8
8: halton(1000) = 0001/10000 → 1/16
9: halton(1001) = 1001/10000 → 9/16
10: halton(1010) = 0101/10000 → 5/16
11: halton(1011) = 1101/10000 → 13/16
12: halton(1100) = 0011/10000 → 3/16
13: halton(1101) = 1011/10000 → 11/16
14: halton(1110) = 0111/10000 → 7/16
15: halton(1111) = 1111/10000 → 15/16
16: halton(10000) = 00001/100000 → 1/32
17: halton(10001) = 10001/100000 → 17/32
18: halton(10010) = 01001/100000 → 9/32
19: halton(10011) = 11001/100000 → 25/32
20: halton(10100) = 00101/100000 → 5/32…

Note that the sequence always produces reduced fractions, i.e. fractions in their lowest possible terms. Once 1/2 has appeared, there is no 2/4, 4/8, 8/16…; once 3/4 has appeared, there is no 6/8, 12/16, 24/32…; and so on. If the fractions are represented as points in the interval [0,1], they look like this:

line1_1_2

point = 1/2


line2_1_4

point = 1/4


line3_3_4

point = 3/4


line4_1_8

point = 1/8


line5_5_8

point = 5/8


line6_3_8

point = 3/8


line7_7_8

point = 7/8


line_b2_anim

(animated line for base = 2, n = 1..63)


It’s apparent that Halton points in base 2 will evenly fill the interval [0,1]. Now compare a Halton sequence in base 3:

1: halton(1) = 1/10[3] → 1/3
2: halton(2) = 2/10[3] → 2/3
3: halton(10) = 01/100[3] → 1/9
4: halton(11) = 11/100[3] → 4/9
5: halton(12) = 21/100[3] → 7/9
6: halton(20) = 02/100 → 2/9
7: halton(21) = 12/100 → 5/9
8: halton(22) = 22/100 → 8/9
9: halton(100) = 001/1000 → 1/27
10: halton(101) = 101/1000 → 10/27
11: halton(102) = 201/1000 → 19/27
12: halton(110) = 011/1000 → 4/27
13: halton(111) = 111/1000 → 13/27
14: halton(112) = 211/1000 → 22/27
15: halton(120) = 021/1000 → 7/27
16: halton(121) = 121/1000 → 16/27
17: halton(122) = 221/1000 → 25/27
18: halton(200) = 002/1000 → 2/27
19: halton(201) = 102/1000 → 11/27
20: halton(202) = 202/1000 → 20/27
21: halton(210) = 012/1000 → 5/27
22: halton(211) = 112/1000 → 14/27
23: halton(212) = 212/1000 → 23/27
24: halton(220) = 022/1000 → 8/27
25: halton(221) = 122/1000 → 17/27
26: halton(222) = 222/1000 → 26/27
27: halton(1000) = 0001/10000 → 1/81
28: halton(1001) = 1001/10000 → 28/81
29: halton(1002) = 2001/10000 → 55/81
30: halton(1010) = 0101/10000 → 10/81

And here is an animated gif representing the Halton sequence in base 3 as points in the interval [0,1]:

line_b3_anim


Halton points in base 3 also evenly fill the interval [0,1]. What happens if you apply the Halton sequence to a two-dimensional square rather a one-dimensional line? Suppose the bottom left-hand corner of the square has the co-ordinates (0,0) and the top right-hand corner has the co-ordinates (1,1). Find points (x,y) inside the square, with x supplied by the Halton sequence in base 2 and y supplied by the Halton sequence in base 3. The square will gradually fill like this:

square1

x = 1/2, y = 1/3


square2

x = 1/4, y = 2/3


square3

x = 3/4, y = 1/9


square4

x = 1/8, y = 4/9


square5

x = 5/8, y = 7/9


square6

x = 3/8, y = 2/9


square7

x = 7/8, y = 5/9


square8

x = 1/16, y = 8/9


square9

x = 9/16, y = 1/27…


square_anim

animated square


Read full page: For Revver and Fevver

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…

Can You Dij It? #1

The most powerful drug in the world is water. The second most powerful is language. But everyone’s on them, so nobody realizes how powerful they are. Well, you could stop drinking water. Then you’d soon realize its hold on the body and the brain.

But you can’t stop using language. Try it. No, the best way to realize the power of language is to learn a new one. Each is a feast with different flavours. New alphabets are good too. The Devanagari alphabet is one of the strongest, but if you want it in refined form, try the phonetic alphabet. It will transform the way you see the world. That’s because it will make you conscious of what you’re already subconsciously aware of.

But “language” is a bigger category that it used to be. Nowadays we have computer languages too. Learning one is another way of transforming the way you see the world. And like natural languages – French, Georgian, Tagalog – they come in different flavours. Pascal is not like Basic is not like C is not like Prolog. But all of them seem to put you in touch with some deeper aspect of reality. Computer languages are like mathemagick: a way to give commands to something immaterial and alter the world by the application of will.

That feeling is at its strongest when you program with machine code, the raw instructions used by the electronics of a computer. At its most fundamental, machine code is simply a series of binary numbers controlling how a computer processes other binary numbers. You can memorize and use those code-numbers, but it’s easier to use something like assembly language, which makes machine-code friendlier for human beings. But it still looks very odd to the uninitiated:

setupnum:
xor ax,ax
xor bp,bp
mov cx,20
clearloop:
mov [di+bp],ax
add bp,2
loop clearloop
ret

That’s almost at the binary bedrock. And machine code is fast. If a fast higher-level language like C feels like flying a Messerschmitt 262, which was a jet-plane, machine-code feels like flying a Messerschmitt 163, which was a rocket-plane. A very fast and very dangerous rocket-plane.

I’m not good at programming languages, least of all machine code, but they are fun to use, quite apart from the way they make you feel as though you’re in touch with a deeper aspect of reality. They do that because the world is mathematics at its most fundamental level, I think, and computer languages are a form of mathematics.

Their mathematical nature is disguised in a lot of what they’re used for, but I like to use them for recreational mathematics. Machine-code is useful when you need a lot of power and speed. For example, look at these digits:

1, 2, 3, 4, 5, 6, 7, 8, 9, 1*, 0*, 1, 1, 1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 9, 2, 0, 2, 1, 2, 2, 2, 3, 2, 4, 2, 5, 2, 6, 2, 7, 2, 8, 2, 9, 3, 0, 3, 1, 3, 2, 3, 3, 3, 4, 3, 5, 3, 6*, 3*, 7, 3, 8, 3, 9, 4, 0, 4, 1, 4, 2, 4…

They’re what the Online Encyclopedia of Integer Sequences (OEIS) calls “the almost natural numbers” (sequence A007376) and you generate them by writing the standard integers – 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13… – and then separating each digit with a comma: 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3… The commas give them some interesting twists. In a list of the standard integers, the 1st entry is 1, the 10th entry is 10, the 213rd entry is 213, the 987,009,381th entry is 987,009,381, and so on.

But that doesn’t work with the almost natural numbers. The 10th entry is 1, not 10, and the 11th entry is 0, not 11. But the 10th entry does begin the sequence (1, 0). I wondered whether that happened again. It does. The 63rd entry in the almost natural numbers begins the sequence (6, 3) – see the asterisks in the sequence above.

This happens again at the 3105th entry, which begins the sequence (3, 1, 0, 5). After that the gaps get bigger, which is where machine code comes in. An ordinary computer-language takes a long time to reach the 89,012,345,679th entry in the almost natural numbers. Machine code is much quicker, which is why I know that the 89,012,345,679th entry begins the sequence (8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 9):

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 63, 3105, 43108, 77781, 367573, 13859021, 77911127, 911360799, 35924813703, 74075186297, 89012345679…

And an ordinary computer-language might give you the impression that base 9 doesn’t have numbers like these (apart from the trivial 1, 2, 3, 4, 5, 6, 7, 8, 10…). But it does. 63 in base 10 is a low-hanging fruit: you could find it working by hand. In base 9, the fruit are much higher-hanging. But machine code plucks them with almost ridiculous ease:

1, 2, 3, 4, 5, 6, 7, 8, 10, 570086565, 655267526, 2615038272, 4581347024, 5307541865, 7273850617, 7801234568…

Block n Rule

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.