Mod’s Chosen

When you divide one integer by another, one of two things happens. Either the second number goes perfectly into the first or there’s a remainder:


15 / 5 = 3
18 / 5 = 3⅗

In the first case, there’s no remainder, that is, the remainder is 0. In the second case, there’s a remainder of 3. And all that gives you the basis for what’s called modular arithmetic. It returns the remainder when one number is divided by another:


15 mod 5 = 0
16 mod 5 = 1
17 mod 5 = 2
18 mod 5 = 3
19 mod 5 = 4
20 mod 5 = 0
21 mod 5 = 1
22 mod 5 = 2...

It looks simple but a lot of mathematics is built on it. I don’t know much of that maths, but I know one thing I like: the patterns you can get from modular arithmetic. Suppose you draw a square, then find a point and measure the distances from that point to all the vertices of the square. Then add the distances up, turn the result into an integer if necessary, and test whether the result is divisible by 2 or not. If it is divisible, colour the point in. If it isn’t, leave the point blank.

Then move on to another point and perform the same test. This is modular arithematic, because for each point you’re asking whether d mod 2 = 0. The result looks like this:

d mod 2 = 0


Here are more divisors:

d mod 3 = 0


d mod 4 = 0


d mod 5 = 0


d mod 6 = 0


d mod 7 = 0


d mod 8 = 0


d mod 9 = 0


d mod 10 = 0


d mod various = 0 (animated)


You can also use modular arithmetic to determine the colour of the points. For example, if d mod n = 0, the point is black; if d mod n = 1, the point is red; if d mod n = 2, the point is green; and so on.

d mod 3 = 0, 1, 2 (coloured)


d mod 4 = 0, 1, 2, 3 (coloured)


d mod 5 = 0, 1, 2, 3, 4 (coloured)



d mod 5 = 0, 1, 2, 3, 4 (animated and expanding)


Get Your Ox Off

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

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


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


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


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

primes_table


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

primes_large


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

primes

(click for full image)


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

mod2

n mod 2 = 0


And here are some more examples of a modulus test:

mod3

n mod 3 = 0


mod5

n mod 5 = 0


mod9

n mod 9 = 0


mod15

n mod 15 = 0


mod_various

n mod various = 0 (animated gif)


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

recip7_base10

1/7 in base 10


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

recip9_base2

1/9 in base 2


recip13_base10

1/13 in base 10


recip27_base10

1/27 in base 10


recip41_base10

1/41 in base 10


recip63_base10

1/63 in base 10


recip82_base10

1/82 in base 10


recip101_base10

1/101 in base 10


recip104_base10

1/104 in base 10


recip124_base10

1/124 in base 10


recip143_base10

1/143 in base 10


recip175_base10

1/175 in base 10


recip604_base8

1/604 in base 8


recip_various

1/n in various bases (animated gif)


Playing the Double Base

Here’s some mathematical nonsense:

10 > 12
100 > 122
1000 > 1222

How can 1000 > 1222? Well, it makes perfect sense in what you might call a double base. In this base, every number is identified by a unique string of digits, but the strings don’t behave as they do in a standard base.

To see how this double base works, first look at 9 in standard base 2. To generate the binary digits from right to left, you follow the procedure x mod 2 and x = x div 2, where (x mod 2) returns the remainder when x is divided by 2 and (x div 2) divides x by 2 and discards the remainder:

9 mod 2 = 1 → ...1
9 div 2 = 4
4 mod 2 = 0 → ..01
4 div 2 = 2
2 mod 2 = 0 → .001
2 div 2 = 1
1 mod 2 = 1 → 1001

So 9[b=10] = 1001[b=2]. To adapt the procedure to base 3, simply use x mod 3 and x = x div 3:

32 mod 3 = 2 → ...2
32 div 3 = 10
10 mod 3 = 1 → ..12
10 div 3 = 3
3 mod 3 = 0 → .012
3 div 3 = 1
1 mod 3 = 1 → 1012

So 32[b=10] = 1012[b=3].

But what happens if you mix bases and use (x mod 3) and (x div 2), like this?:

2 mod 3 = 2 → .2
2 div 2 = 1
1 mod 3 = 1 → 12

3 mod 3 = 0 → .0
3 div 2 = 1
1 mod 3 = 1 → 10

So 10 > 12, i.e. 10[b=3,2] > 12[b=3,2].

5 mod 3 = 2 → ..2
5 div 2 = 2
2 mod 3 = 2 → .22
2 div 2 = 1
1 mod 3 = 1 → 122

6 mod 3 = 0 → ..0
6 div 2 = 3
3 mod 3 = 0 → .00
3 div 2 = 1
1 mod 3 = 1 → 100

So 100 > 122.

11 mod 3 = 2 → ...2
11 div 2 = 5
5 mod 3 = 2 → ..22
5 div 2 = 2
2 mod 3 = 2 → .222
2 div 2 = 1
1 mod 3 = 1 → 1222

12 mod 3 = 0 → …0
12 div 2 = 6
6 mod 3 = 0 → ..00
6 div 2 = 3
3 mod 3 = 0 → .000
3 div 2 = 1
1 mod 3 = 1 → 1000

And 1000 > 1222. Here are numbers 1 to 32 in this double base:

1 = 1
12 = 2
10 = 3
121 = 4
122 = 5
100 = 6
101 = 7
1212 = 8
1210 = 9
1221 = 10
1222 = 11
1000 = 12
1001 = 13
1012 = 14
1010 = 15
12121 = 16
12122 = 17
12100 = 18
12101 = 19
12212 = 20
12210 = 21
12221 = 22
12222 = 23
10000 = 24
10001 = 25
10012 = 26
10010 = 27
10121 = 28
10122 = 29
10100 = 30
10101 = 31
121212 = 32

Given a number represented in this mixed base, how do you extract the underlying n? Suppose the number takes the form n = (digit[1]..digit[di]), where digit[1] is the first and leftmost digit and digit[di] the final and rightmost digit. Then this algorithm will extract n:

n = 1
for i = 2 to di
..n = n * 2
..while n mod 3 ≠ digit[i]
....n = n + 1
..endwhile
next i
print n

For example, suppose n = 12212[b=3,2]. Then di = 5 and the algorithm will work like this:

n = 1
n = n * 2 = 2.
2 mod 3 = 2 = digit[2]
2 * 2 = 4
4 mod 3 = 1 ≠ digit[3]
5 mod 3 = 2 = digit[3]
5 * 2 = 10
10 mod 3 = 1 = digit[4]
10 * 2 = 20
20 mod 3 = 2 = digit[5]

Therefore 12212[b=3,2] = 20[b=10].

Now try some more mathematical nonsense:

21 > 100
111 > 1,000
1,001 > 10,000
10,001 > 100,000

How can numbers with d digits be greater than numbers with d+1 digits? Easily. In this incremental base, the base adjusts itself as the digits are generated, like this:

5 mod 2 = 1 → .1
5 div 2 = 2
2 mod (2 + 1) = 2 mod 3 = 2 → 21

The first digit generated is 1, so the base increases to (2 + 1) = 3 for the second digit. Compare the procedure when n = 4:

4 mod 2 = 0 → ..0
4 div 2 = 2
2 mod 2 = 0 → .00
2 div 2 = 1
1 mod 2 = 1 → 100

So 21 > 100, because 4 is a power of 2 and all the digits generated by (x mod 2) are 0 except the final and leftmost. 2 + 0 = 2. Now try n = 33:

33 mod 2 = 1 → ...1
33 div 2 = 16
16 mod (2+1) = 16 mod 3 = 1 → ..11
16 div 3 = 5
5 mod (3+1) = 5 mod 4 = 1 → .111
5 div 4 = 1
1 mod (4+1) = 1 mod 5 = 1.

33[b=10] = 1111[b=2,3,4,5].

Here are numbers 1 to 60 in this incremental base (note how 21 > 100, 111 > 1000, 1001 > 10000 and 10001 > 100000):

1 = 1
10 = 2
11 = 3
100 = 4*
21 = 5*
110 = 6
101 = 7
1000 = 8*
111 = 9*
210 = 10
121 = 11
1100 = 12
201 = 13
1010 = 14
211 = 15
10000 = 16*
221 = 17
1110 = 18
1001 = 19*
2100 = 20
311 = 21
1210 = 22
321 = 23
11000 = 24
1101 = 25
2010 = 26
1011 = 27
10100 = 28
421 = 29
2110 = 30
1201 = 31
100000 = 32*
1111 = 33
2210 = 34
1021 = 35
11100 = 36
2001 = 37
10010 = 38
1211 = 39
21000 = 40
1121 = 41
3110 = 42
2101 = 43
12100 = 44
1311 = 45
3210 = 46
1221 = 47
110000 = 48
2201 = 49
11010 = 50
2011 = 51
20100 = 52
1321 = 53
10110 = 54
10001 = 55*
101000 = 56
2111 = 57
4210 = 58
1421 = 59
21100 = 60

And here are numbers 256 to 270 (Note how 8,421 > 202,100 > 100,000,000):

100000000 = 256*
11221 = 257
101110 = 258
32101 = 259
202100 = 260*
13311 = 261
41210 = 262
10321 = 263
1111000 = 264
24201 = 265
131010 = 266
23011 = 267
320100 = 268
8421 = 269*
52110 = 270

Extracting n from a number represented in this incremental base is trickier than for the double base using (x mod 3) and (x div 2). To see how to do it, examine 11221[b=incremental]. The fifth and rightmost digit is 1, so the base increases to (2 + 1) = 3 for the fourth digit, which is 2. The base increases to (3 + 2) = 5 for the third digit, which is 2 again. The base increases to (5 + 2) = 7 for the second digit, 1. But the first and rightmost digit, 1, represents (x div 7) mod (7 + 1 = 8). So n can be extracted like this:

digit[1] * 7 = 1 * 7 = 7
7 mod 7 = 0 ≠ digit[2]
8 mod 7 = 1 = digit[2]
8 * 5 = 40
40 mod 5 = 0 ≠ digit[3]
41 mod 5 = 1 ≠ digit[3]
42 mod 5 = 2 = digit[3]
42 * 3 = 126
126 mod 3 = 0 ≠ digit[4]
127 mod 3 = 1 ≠ digit[4]
128 mod 3 = 2 = digit[4]
128 * 2 = 256
256 mod 2 = 0 ≠ digit[5]
257 mod 2 = 1 = digit[5]

So 11221[b=8,7,5,3,2] = 257[b=10].

Now try 8421[b=incremental]. The fourth and rightmost digit is 1, so the base increases to (2 + 1) = 3 for the third digit, which is 2. The base increases to (3 + 2) = 5 for the second digit, 4. But the first and rightmost digit, 8, represents (x div 5) mod (5 + 4 = 9). So n can be extracted like this:

digit[1] * 5 = 8 * 5 = 40
40 mod 5 = 0 ≠ digit[2]
41 mod 5 = 1 ≠ digit[2]
42 mod 5 = 2 ≠ digit[2]
43 mod 5 = 3 ≠ digit[2]
44 mod 5 = 4 = digit[2]
44 * 3 = 132
132 mod 3 = 0 ≠ digit[3]
133 mod 3 = 1 ≠ digit[3]
134 mod 3 = 2 = digit[3]
134 * 2 = 268
268 mod 2 = 0 ≠ digit[4]
269 mod 2 = 1 = digit[4]

So 8421[b=9,5,3,2] = 269[b=10].

Miss This

1,729,404 is seven digits long. If you drop one digit at a time, you can create seven more numbers from it, each six digits long. If you add these numbers, something special happens:

1,729,404 → 729404 (missing 1) + 129404 (missing 7) + 179404 (missing 2) + 172404 + 172904 + 172944 + 172940 = 1,729,404

So 1,729,404 is narcissistic, or equal to some manipulation of its own digits. Searching for numbers like this might seem like a big task, but you can cut the search-time considerably by noting that the final two digits determine whether a number is a suitable candidate for testing. For example, what if a seven-digit number ends in …38? Then the final digit of the missing-digit sum will equal (3 x 1 + 8 x 6) modulo 10 = (3 + 48) mod 10 = 51 mod 10 = 1. This means that you don’t need to check any seven-digit number ending in …38.

But what about seven-digit numbers ending in …57? Now the final digit of the sum will equal (5 x 1 + 7 x 6) modulo 10 = (5 + 42) mod 10 = 47 mod 10 = 7. So seven-digit numbers ending in …57 are possible missing-digit narcissistic sums. Then you can test numbers ending …157, …257, …357 and so on, to determine the last-but-one digit of the sum. Using this method, one quickly finds the only two seven-digit numbers of this form in base-10:

1,729,404 → 729404 + 129404 + 179404 + 172404 + 172904 + 172944 + 172940 = 1,729,404

1,800,000 → 800000 + 100000 + 180000 + 180000 + 180000 + 180000 + 180000 = 1,800,000

What about eight-digit numbers? Only those ending in these two digits need to be checked: …00, …23, …28, …41, …46, …64, …69, …82, …87. Here are the results:

• 13,758,846 → 3758846 + 1758846 + 1358846 + 1378846 + 1375846 + 1375846 + 1375886 + 1375884 = 13,758,846
• 13,800,000 → 3800000 + 1800000 + 1300000 + 1380000 + 1380000 + 1380000 + 1380000 + 1380000 = 13,800,000
• 14,358,846 → 4358846 + 1358846 + 1458846 + 1438846 + 1435846 + 1435846 + 1435886 + 1435884 = 14,358,846
• 14,400,000 → 4400000 + 1400000 + 1400000 + 1440000 + 1440000 + 1440000 + 1440000 + 1440000 = 14,400,000
• 15,000,000 → 5000000 + 1000000 + 1500000 + 1500000 + 1500000 + 1500000 + 1500000 + 1500000 = 15,000,000
• 28,758,846 → 8758846 + 2758846 + 2858846 + 2878846 + 2875846 + 2875846 + 2875886 + 2875884 = 28,758,846
• 28,800,000 → 8800000 + 2800000 + 2800000 + 2880000 + 2880000 + 2880000 + 2880000 + 2880000 = 28,800,000
• 29,358,846 → 9358846 + 2358846 + 2958846 + 2938846 + 2935846 + 2935846 + 2935886 + 2935884 = 29,358,846
• 29,400,000 → 9400000 + 2400000 + 2900000 + 2940000 + 2940000 + 2940000 + 2940000 + 2940000 = 29,400,000

But there are no nine-digit sumbers, or nine-digit numbers that supply missing-digit narcissistic sums. What about ten-digit sumbers? There are twenty-one:

1,107,488,889; 1,107,489,042; 1,111,088,889; 1,111,089,042; 3,277,800,000; 3,281,400,000; 4,388,888,889; 4,388,889,042; 4,392,488,889; 4,392,489,042; 4,500,000,000; 5,607,488,889; 5,607,489,042; 5,611,088,889; 5,611,089,042; 7,777,800,000; 7,781,400,000; 8,888,888,889; 8,888,889,042; 8,892,488,889; 8,892,489,042 (21 numbers)

Finally, the nine eleven-digit sumbers all take this form:

30,000,000,000 → 0000000000 + 3000000000 + 3000000000 + 3000000000 + 3000000000 + 3000000000 + 3000000000 + 3000000000 + 3000000000 + 3000000000 + 3000000000 = 30,000,000,000

So that’s forty-one narcissistic sumbers in base-10. Not all of them are listed in Sequence A131639 at the Encyclopedia of Integer Sequences, but I think I’ve got my program working right. Other bases show similar patterns. Here are some missing-digit narcissistic sumbers in base-5:

• 1,243 → 243 + 143 + 123 + 124 = 1,243 (b=5) = 198 (b=10)
• 1,324 → 324 + 124 + 134 + 132 = 1,324 (b=5) = 214 (b=10)
• 1,331 → 331 + 131 + 131 + 133 = 1,331 (b=5) = 216 (b=10)
• 1,412 → 412 + 112 + 142 + 141 = 1,412 (b=5) = 232 (b=10)

• 100,000 → 00000 + 10000 + 10000 + 10000 + 10000 + 10000 = 100,000 (b=5) = 3,125 (b=10)
• 200,000 → 00000 + 20000 + 20000 + 20000 + 20000 + 20000 = 200,000 (b=5) = 6,250 (b=10)
• 300,000 → 00000 + 30000 + 30000 + 30000 + 30000 + 30000 = 300,000 (b=5) = 9,375 (b=10)
• 400,000 → 00000 + 40000 + 40000 + 40000 + 40000 + 40000 = 400,000 (b=5) = 12,500 (b=10)

And here are some sumbers in base-16:

5,4CD,111,0EE,EF0,542 = 4CD1110EEEF0542 + 5CD1110EEEF0542 + 54D1110EEEF0542 + 54C1110EEEF0542 + 54CD110EEEF0542 + 54CD110EEEF0542 + 54CD110EEEF0542 + 54CD111EEEF0542 + 54CD1110EEF0542 + 54CD1110EEF0542 + 54CD1110EEF0542 + 54CD1110EEE0542 + 54CD1110EEEF542 + 54CD1110EEEF042 + 54CD1110EEEF052 + 54CD1110EEEF054 (b=16) = 6,110,559,033,837,421,890 (b=10)

6,5DD,E13,CEE,EF0,542 = 5DDE13CEEEF0542 + 6DDE13CEEEF0542 + 65DE13CEEEF0542 + 65DE13CEEEF0542 + 65DD13CEEEF0542 + 65DDE3CEEEF0542 + 65DDE1CEEEF0542 + 65DDE13EEEF0542 + 65DDE13CEEF0542 + 65DDE13CEEF0542 + 65DDE13CEEF0542 + 65DDE13CEEE0542 + 65DDE13CEEEF542 + 65DDE13CEEEF042 + 65DDE13CEEEF052 + 65DDE13CEEEF054 (b=16) = 7,340,270,619,506,705,730 (b=10)

10,000,000,000,000,000 → 0000000000000000 + 1000000000000000 + 1000000000000000 + 1000000000000000 + 1000000000000000 + 1000000000000000 + 1000000000000000 + 1000000000000000 + 1000000000000000 + 1000000000000000 + 1000000000000000 + 1000000000000000 + 1000000000000000 + 1000000000000000 + 1000000000000000 + 1000000000000000 + 1000000000000000 = 10,000,000,000,000,000 (b=16) = 18,446,744,073,709,551,616 (b=10)

F0,000,000,000,000,000 → 0000000000000000 + F000000000000000 + F000000000000000 + F000000000000000 + F000000000000000 + F000000000000000 + F000000000000000 + F000000000000000 + F000000000000000 + F000000000000000 + F000000000000000 + F000000000000000 + F000000000000000 + F000000000000000 + F000000000000000 + F000000000000000 + F000000000000000 = F0,000,000,000,000,000 (b=16) = 276,701,161,105,643,274,240 (b=10)

Next I’d like to investigate sumbers created by missing two, three and more digits at a time. Here’s a taster:

1,043,101 → 43101 (missing 1 and 0) + 03101 (missing 1 and 4) + 04101 (missing 1 and 3) + 04301 + 04311 + 04310 + 13101 + 14101 + 14301 + 14311 + 14310 + 10101 + 10301 + 10311 + 10310 + 10401 + 10411 + 10410 + 10431 + 10430 + 10431 = 1,043,101 (b=5) = 18,526 (b=10)