Tag Archives: powers of 2

Bi-Bell Basics

by in Arithmetic, Base Behavior, Binary numbers, Blancmange Curves, Fibonacci Sequence, Fractals, Geometry, Mathematics, Powers and tagged , , , , , , , , , , , , , , , , , | Leave a comment

Here’s what you might call a Sisyphean sequence. It struggles upward, then slips back, over and over again:

1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2...


The struggle goes on for ever. Every time it reaches a new maximum, it will fall back to 1 at the next step. And in fact 1, 2, 3 and all other integers occur infinitely often in the sequence, because it represents the digit-sums of binary numbers:

1 ← 1
1 = 1+0 ← 10 in binary = 2 in base ten
2 = 1+1 ← 11 = 3
1 = 1+0+0 ← 100 = 4
2 = 1+0+1 ← 101 = 5
2 = 1+1+0 ← 110 = 6
3 = 1+1+1 ← 111 = 7
1 = 1+0+0+0 ← 1000 = 8
2 = 1+0+0+1 ← 1001 = 9
2 = 1+0+1+0 ← 1010 = 10
3 = 1+0+1+1 ← 1011 = 11
2 = 1+1+0+0 ← 1100 = 12
3 = 1+1+0+1 ← 1101 = 13
3 = 1+1+1+0 ← 1110 = 14
4 = 1+1+1+1 ← 1111 = 15
1 = 1+0+0+0+0 ← 10000 = 16
2 = 1+0+0+0+1 ← 10001 = 17
2 = 1+0+0+1+0 ← 10010 = 18
3 = 1+0+0+1+1 ← 10011 = 19
2 = 1+0+1+0+0 ← 10100 = 20


Now here’s a related sequence in which all integers do not occur infinitely often:

1, 2, 3, 3, 4, 5, 6, 4, 5, 6, 7, 7, 8, 9, 10, 5, 6, 7, 8, 8, 9, 10, 11, 9, 10, 11, 12, 12, 13, 14, 15, 6, 7, 8, 9, 9, 10, 11, 12, 10, 11, 12, 13, 13, 14, 15, 16, 11, 12, 13, 14, 14, 15, 16, 17, 15, 16, 17, 18, 18, 19, 20, 21, 7, 8, 9, 10, 10, 11, 12, 13, 11, 12, 13, 14, 14, 15, 16, 17, 12, 13, 14, 15, 15, 16, 17, 18, 16, 17, 18, 19, 19, 20, 21, 22, 13, 14, 15, 16, 16, 17, 18, 19, 17, 18, 19, 20, 20, 21, 22, 23, 18, 19, 20, 21, 21, 22, 23, 24, 22, 23, 24, 25, 25, 26, 27, 28, 8, 9, 10, 11, 11, 12, 13, 14, 12, 13, 14, 15, 15...


The sequence represents the sum of the values of occupied columns in the binary numbers, reading from right to left:

10 in binary = 2 in base ten
21 (column values from right to left)
2*1 + 1*0 = 2

11 = 3
21
2*1 + 1*1 = 3

100 = 4
321 (column values from right to left)
3*1 + 2*0 + 1*0 = 3

101 = 5
321
3*1 + 2*0 + 1*1 = 4

110 = 6
321
3*1 + 2*1 + 1*0 = 5

111 = 7
321
3*1 + 2*1 + 1*1 = 6

1000 = 8
4321
4*1 + 3*0 + 2*0 + 1*0 = 4

1001 = 9
4321
4*1 + 3*0 + 2*0 + 1*1 = 5

1010 = 10
4321
4*1 + 3*0 + 2*1 + 1*0 = 6

1011 = 11
4321
4*1 + 3*0 + 2*1 + 1*1 = 7

1100 = 12
4321
4*1 + 3*1 + 2*0 + 1*0 = 7

1101 = 13
4321
4*1 + 3*1 + 2*0 + 1*1 = 8

1110 = 14
4321
4*1 + 3*1 + 2*1 + 1*0 = 9

1111 = 15
4321
4*1 + 3*1 + 2*1 + 1*1 = 10

10000 = 16
54321
5*1 + 4*0 + 3*0 + 2*0 + 1*0 = 5


In that sequence, although no number occurs infinitely often, some numbers occur more often than others. If you represent the count of sums up to a certain digit-length as a graph, you get a famous shape:

Bell curve formed by the count of column-sums in base 2

Bi-bell curves for 1 to 16 binary digits (animated)

In “Pi in the Bi”, I looked at that way of forming the bell curve and called it the bi-bell curve. Now I want to go further. Suppose that you assign varying values to the columns and try other bases. For example, what happens if you assign the values 2^p + 1 to the columns, reading from right to left, then use base 3 to generate the sums? These are the values of 2^p + 1:

2, 3, 5, 9, 17, 33, 65, 129, 257, 513, 1025...


And here’s an example of how you generate a column-sum in base 3:

2102 in base 3 = 65 in base ten
9532 (column values from right to left)
2*9 + 1*5 + 0*3 + 2*2 = 27


The graphs for these column-sums using base 3 look like this as the digit-length rises. They’re no longer bell-curves (and please note that widths and heights have been normalized so that all graphs fit the same space):

Graph for the count of column-sums in base 3 using 2^p + 1 (digit-length <= 7)

(width and height are normalized)

Graph for base 3 and 2^p + 1 (dl<=8)

Graph for base 3 and 2^p + 1 (dl<=9)

Graph for base 3 and 2^p + 1 (dl<=10)

Graph for base 3 and 2^p + 1 (dl<=11)

Graph for base 3 and 2^p + 1 (dl<=12)

Graph for base 3 and 2^p + 1 (animated)

Now try base 3 and column-values of 2^p + 2 = 3, 4, 6, 10, 18, 34, 66, 130, 258, 514, 1026…

Graph for base 3 and 2^p + 2 (dl<=7)

Graph for base 3 and 2^p + 2 (dl<=8)

Graph for base 3 and 2^p + 2 (dl<=9)

Graph for base 3 and 2^p + 2 (dl<=10)

Graph for base 3 and 2^p + 2 (animated)

Now try base 5 and 2^p + 1 for the columns. The original bell curve has become like a fractal called the blancmange curve:

Graph for base 5 and 2^p + 1 (dl<=7)

Graph for base 5 and 2^p + 1 (dl<=8)

Graph for base 5 and 2^p + 1 (dl<=9)

Graph for base 5 and 2^p + 1 (dl<=10)

Graph for base 5 and 2^p + 1 (animated)

And finally, return to base 2 and try the Fibonacci numbers for the columns:

Graph for base 2 and Fibonacci numbers = 1,1,2,3,5… (dl<=7)

Graph for base 2 and Fibonacci numbers (dl<=9)

Graph for base 2 and Fibonacci numbers (dl<=11)

Graph for base 2 and Fibonacci numbers (dl<=13)

Graph for base 2 and Fibonacci numbers (dl<=15)

Graph for base 2 and Fibonacci numbers (animated)

Previously Pre-Posted…

• Pi in the Bi — bell curves generated by binary digits

A Walk on the Wide Side

by in Base Behavior, Digit-sums, Fibonacci Sequence, Integer Sequences, Irrational numbers, φ, Mathematics, Phi and tagged , , , , , , , , , , , , , , , | Leave a comment

How wide is a number? The obvious answer is to count digits and say that 1 and 9 are one digit wide, 11 and 99 are two digits wide, 111 and 999 are three digits wide, and so on. But that isn’t a very good answer. 111 and 999 are both three digits wide, but 999 is nine larger times than 111. And although 111 and 999 are both one digit wider than 11 and 99, 111 is much closer to 99 than 999 is to 111.

So there’s got to be a better answer to the question. I came across it indirectly, when I started looking at carries in powers. I wanted to know how fast a number grew in digit-width as it was multiplied repeatedly by, say, 2. For example, 2^3 = 8 and 2^4 = 16, so there’s been a carry at the far left and 2^4 = 16 has increased in digit-width by 1 over 2^3 = 8. After that, 2^6 = 64 and 2^7 = 128, so there’s another carry and another increase in digit-width. I wrote a program to sum the carries and divide them by the power. If I were better at math, I would’ve known what the value of carries / power was going to be. Here’s the program beginning to find it (it begins with a carry of 1, to mark 2^0 = 1 as creating a digit ex nihilo, as it were):


8 = 2^3
16 = 2^4 → 2 / 4 = 0.5
64 = 2^6
128 = 2^7 → 3 / 7 = 0.4285714285714285714285714286
512 = 2^9
1024 = 2^10 → 4 / 10 = 0.4
8192 = 2^13
16384 = 2^14 → 5 / 14 = 0.3571428571428571428571428571
65536 = 2^16
131072 = 2^17 → 6 / 17 = 0.3529411764705882352941176471
524288 = 2^19
1048576 = 2^20 → 7 / 20 = 0.35
8388608 = 2^23
16777216 = 2^24 → 8 / 24 = 0.3...
67108864 = 2^26
134217728 = 2^27 → 9 / 27 = 0.3...
536870912 = 2^29
1073741824 = 2^30 → 10 / 30 = 0.3...
8589934592 = 2^33
17179869184 = 2^34 → 11 / 34 = 0.3235294117647058823529411765
68719476736 = 2^36
137438953472 = 2^37 → 12 / 37 = 0.3243243243243243243243243243
549755813888 = 2^39
1099511627776 = 2^40 → 13 / 40 = 0.325
8796093022208 = 2^43
17592186044416 = 2^44 → 14 / 44 = 0.318...
70368744177664 = 2^46
140737488355328 = 2^47 → 15 / 47 = 0.3191489361702127659574468085
562949953421312 = 2^49
1125899906842624 = 2^50 → 16 / 50 = 0.32
9007199254740992 = 2^53
18014398509481984 = 2^54 → 17 / 54 = 0.3148...
72057594037927936 = 2^56
144115188075855872 = 2^57 → 18 / 57 = 0.3157894736842105263157894737
576460752303423488 = 2^59
1152921504606846976 = 2^60 → 19 / 60 = 0.316...
9223372036854775808 = 2^63
18446744073709551616 = 2^64 → 20 / 64 = 0.3125
73786976294838206464 = 2^66
147573952589676412928 = 2^67 → 21 / 67 = 0.3134328358208955223880597015
590295810358705651712 = 2^69
1180591620717411303424 = 2^70 → 22 / 70 = 0.3142857...
9444732965739290427392 = 2^73
18889465931478580854784 = 2^74 → 23 / 74 = 0.3108...
75557863725914323419136 = 2^76
151115727451828646838272 = 2^77 → 24 / 77 = 0.3116883...
604462909807314587353088 = 2^79
1208925819614629174706176 = 2^80 → 25 / 80 = 0.3125
9671406556917033397649408 = 2^83
19342813113834066795298816 = 2^84 → 26 / 84 = 0.3095238095238095238095238095
77371252455336267181195264 = 2^86
154742504910672534362390528 = 2^87 → 27 / 87 = 0.3103448275862068965517241379
618970019642690137449562112 = 2^89
1237940039285380274899124224 = 2^90 → 28 / 90 = 0.31...
9903520314283042199192993792 = 2^93
19807040628566084398385987584 = 2^94 → 29 / 94 = 0.3085106382978723404255319149
79228162514264337593543950336 = 2^96
158456325028528675187087900672 = 2^97 → 30 / 97 = 0.3092783505154639175257731959
633825300114114700748351602688 = 2^99
1267650600228229401496703205376 = 2^100 → 31 / 100 = 0.31

After calculating 2^p higher and higher (I discarded trailing digits of 2^p), I realized that the answer — carries / power — was converging on a value of slightly less than 0.30103. In the end (doh!), I realized that what I was calculating was the logarithm of 2 in base 10:


log(2) = 0.3010299956639811952137388947...
10^0.301029995663981... = 2

You can use then same carries-and-powers method to approximate the values of other logarithms:


log(1) = 0
log(2) = 0.3010299956639811952137388947...
log(3) = 0.4771212547196624372950279033...
log(4) = 0.6020599913279623904274777894...
log(5) = 0.6989700043360188047862611053...
log(6) = 0.7781512503836436325087667980...
log(7) = 0.8450980400142568307122162586...
log(8) = 0.9030899869919435856412166842...
log(9) = 0.9542425094393248745900558065...

I also realized logarithms are a good answer to the question I raised above: How wide is a number? The logs of the powers of 2 are multiples of log(2):


    log(2^1) = log(2) = 0.301029995663981195213738894
    log(2^2) = log(4) = 0.602059991327962390427477789 = 2 * log(2)
    log(2^3) = log(8) = 0.903089986991943585641216684 = 3 * log(2)
   log(2^4) = log(16) = 1.204119982655924780854955579 = 4 * log(2)
   log(2^5) = log(32) = 1.505149978319905976068694474 = 5 * log(2)
   log(2^6) = log(64) = 1.806179973983887171282433368 = 6 * log(2)
  log(2^7) = log(128) = 2.107209969647868366496172263 = 7 * log(2)
  log(2^8) = log(256) = 2.408239965311849561709911158 = 8 * log(2)
  log(2^9) = log(512) = 2.709269960975830756923650053 = 9 * log(2)
log(2^10) = log(1024) = 3.010299956639811952137388947 = 10 * log(2)

4 is 2 times larger than 2 and, in a sense, the width of 4 is 0.301029995663981… greater than the width of 2. As you can see, when the integer part of the log-sum increases by 1, so does the digit-width of the power:


 log(2^3) = log(8) = 0.903089986991943585641216684 = 3 * log(2)
log(2^4) = log(16) = 1.204119982655924780854955579 = 4 * log(2)

[...]

 log(2^6) = log(64) = 1.806179973983887171282433368 = 6 * log(2)
log(2^7) = log(128) = 2.107209969647868366496172263 = 7 * log(2)

[...]

  log(2^9) = log(512) = 2.709269960975830756923650053 = 9 * log(2)
log(2^10) = log(1024) = 3.01029995663981195213738894 = 10 * log(2)

In other words, powers of 2 are increasing in width by 0.301029995663981… units. When the increase flips the integer part of the log-sum up by 1, the digit-width or digit-count also increases by 1. To find the digit-count of a number, n, in a particular base, you simply take the integer part of log(n,b) and add 1. In base 10, the log of 123456789 is 8.091514… The integer part is 8 and 8+1 = 9. But it also makes perfect sense that log(1) = 0. No matter how many times you multiply a number by 1, the number never changes. That is, its width stays the same. So you can say that 1 has a width of 0, while 2 has a width of 0.301029995663981…

Logarithms also answer a question pre-previously raised on Overlord of the Über-Feral: Why are the Fibonacci numbers so productive in base 11 for digsum(fib(k)) = k? In base 10, such numbers are quickly exhausted:


digsum(fib(1)) = 1 = digsum(1)
digsum(fib(5)) = 5 = digsum(5)
digsum(fib(10)) = 10 = digsum(55)
digsum(fib(31)) = 31 = digsum(1346269)
digsum(fib(35)) = 35 = digsum(9227465)
digsum(fib(62)) = 62 = digsum(4052739537881)
digsum(fib(72)) = 72 = digsum(498454011879264)
digsum(fib(175)) = 175 = digsum(1672445759041379840132227567949787325)
digsum(fib(180)) = 180 = digsum(18547707689471986212190138521399707760)
digsum(fib(216)) = 216 = digsum(619220451666590135228675387863297874269396512)
digsum(fib(251)) = 251 = digsum(12776523572924732586037033894655031898659556447352249)
digsum(fib(252)) = 252 = digsum(20672849399056463095319772838289364792345825123228624)
digsum(fib(360)) = 360
digsum(fib(494)) = 494
digsum(fib(540)) = 540
digsum(fib(946)) = 946
digsum(fib(1188)) = 1188
digsum(fib(2222)) = 2222

In base 11, such numbers go on and on:


digsum(fib(1),b=11) = 1 = digsum(1) (k=1)
digsum(fib(5),b=11) = 5 = digsum(5) (k=5)
digsum(fib(12),b=11) = 12 = digsum(1A2) (k=13)
digsum(fib(38),b=11) = 38 = digsum(855138A1) (k=41)
digsum(fib(49)) = 49 = digsum(2067A724762) (k=53) (c=5)
digsum(fib(50)) = 50 = digsum(542194A6905) (k=55)
digsum(fib(55)) = 55 = digsum(54756364A280) (k=60)
digsum(fib(56)) = 56 = digsum(886283256841) (k=61)
digsum(fib(82)) = 82 = digsum(57751318A9814A6410) (k=90)
digsum(fib(89)) = 89 = digsum(140492673676A06482A2) (k=97)
digsum(fib(144)) = 144 = digsum(401631365A48A784A09392136653457871) (k=169) (c=10)
digsum(fib(159)) = 159 = digsum(67217257641069185100889658A1AA72A0805) (k=185)
digsum(fib(166)) = 166 = digsum(26466A3A88237918577363A2390343388205432) (k=193)
digsum(fib(186)) = 186 = digsum(6A963147A9599623A20A05390315140A21992A96005) (k=215)
digsum(fib(221)) = 221 (k=265) (c=15)
digsum(fib(225)) = 225 (k=269)
digsum(fib(2A1)) = 2A1 (k=353)
digsum(fib(2A3)) = 2A3 (k=355)

[...]

digsum(fib(39409)) = 39409 (k=56395)
digsum(fib(3958A)) = 3958A (k=56605) (c=295)
digsum(fib(3965A)) = 3965A (k=56693)
digsum(fib(3A106)) = 3A106 (k=57360)
digsum(fib(3AA46)) = 3AA46 (k=58493)
digsum(fib(40140)) = 40140 (k=58729)
digsum(fib(4222A)) = 4222A (k=61500) (c=300)
digsum(fib(42609)) = 42609 (k=61961)
digsum(fib(42775)) = 42775 (k=62155)
digsum(fib(4287A)) = 4287A (k=62281)
digsum(fib(430A2)) = 430A2 (k=62669)
digsum(fib(43499)) = 43499 (k=63149) (c=305)
digsum(fib(435A9)) = 435A9 (k=63281)

[...]

digsum(fib(157476)) = 157476 (k=244140) (c=525)
digsum(fib(158470)) = 158470 (k=245465)
digsum(fib(159037)) = 159037 (k=246275)
digsum(fib(159285)) = 159285 (k=246570)
digsum(fib(159978)) = 159978 (k=247409)
digsum(fib(162993)) = 162993 (k=252750) (c=530)
digsum(fib(163A32)) = 163A32 (k=254135)
digsum(fib(164918)) = 164918 (k=255329)
digsum(fib(166985)) = 166985 (k=258065)
digsum(fib(167234)) = 167234 (k=258493)
digsum(fib(167371)) = 167371 (k=258655) (c=535)
digsum(fib(1676A5)) = 1676A5 (k=259055)
digsum(fib(16992A)) = 16992A (k=261997)

[...]

When do these numbers run out in base 11? I don’t know, but I do know why there are so many of them. The answer involves the logarithm of a special number. The most famous aspect of Fibonacci numbers is that the ratio, fib(k) / fib(k-1), of successive numbers converges on an irrational constant known as Φ. Here are the first Fibonacci numbers, where fib(k) = fib(k-2) + fib(k-1) (in other words, 1+1 = 2, 1+2 = 3, 2+3 = 5, and so on):


1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, ...

And here are the first ratios:


1 / 1 = 1
2 / 1 = 2
3 / 2 = 1.5
5 / 3 = 1.6...
8 / 5 = 1.6
13 / 8 = 1.625
21 / 13 = 1.6153846...
34 / 21 = 1.619047...
55 / 34 = 1.617647058823529411764705882
89 / 55 = 1.618...
144 / 89 = 1.617977528089887640449438202
233 / 144 = 1.61805...
377 / 233 = 1.618025751072961373390557940
610 / 377 = 1.618037135278514588859416446
987 / 610 = 1.618032786885245901639344262
1597 / 987 = 1.618034447821681864235055724
2584 / 1597 = 1.618033813400125234815278648
4181 / 2584 = 1.618034055727554179566563468
6765 / 4181 = 1.618033963166706529538387946
[...]

The ratios get closer and closer to Φ = 1.618033988749894848204586834… = (√5 + 1) / 2. In other words, fib(k) ≈ fib(k-1) * Φ = fib(k-1) * 1.618… in base 10. This means that the digit-length of fib(k) ≈ integer(k * log(&Phi)) + 1. In base b, the average value of a digit in a Fibonacci number is (b^2-b) / 2b. Therefore in base 10, the average value of a digit is (10^2-10) / 20 = 90 / 20 = 4.5. The average value of digsum(fib(k)) ≈ 4.5 * log(&Phi) * k = 4.5 * 0.20898764… * k = 0.940444… * k. It isn’t surprising that as fib(k) gets larger, digsum(fib(k)) tends to get smaller than k.

In base 10, anyway. But what about base 11? In base 11, log(Φ) = 0.20068091818623… and the average value of a base-11 digit in fib(k) is 5 = 110 / 22 = (11^2 – 11) / 22. Therefore the average value of digsum(fib(k)) in base 11 is 5 * log(&Phi) * k = 5 * 0.20068091818623… * k = 1.00340459… * k. The average value of digsum(fib(k)) is much closer to k and it’s not surprising that for so many fib(k) in base 11, digsum(fib(k)) = k. In base 11, log(Φ) ≈ 1/5 and because the average digval is 5, digsum(fib(k)) ≈ 5 * 1/5 * k = 1 * k = k. As we’ve seen, that isn’t true in base 10. Nor is it true in base 12, where log(Φ) = 0.1936538843826… and average digval is 5.5 = (12^2 – 12) / 24 = 132 / 24. Therefore the average value in base 12 of digsum(fib(k)) = 1.0650963641… * k. The function digsum(fib(k)) = k rapidly dries up in base 12, just as it does in base 10:


digsum(fib(1),b=12) = 1 = digsum(1) (k=1)
digsum(fib(5),b=12) = 5 = digsum(5) (k=5)
digsum(fib(11) = 11 = digsum(175) (k=13)
digsum(fib(12) = 12 = digsum(275) (k=14)
digsum(fib(75) = 75 = digsum(976446538A0863811) (k=89) (c=5)
digsum(fib(80) = 80 = digsum(1B3643B50939808B400) (k=96)
digsum(fib(A3) = A3 = digsum(35147A566682BB9529034402) (k=123)
digsum(fib(165) = 165 (k=221)
digsum(fib(283) = 283 (k=387)
digsum(fib(2AB) = 2AB (k=419) (c=10)
digsum(fib(39A) = 39A (k=550)
digsum(fib(460) = 460 (k=648)
digsum(fib(525) = 525 (k=749)
digsum(fib(602) = 602 (k=866)
digsum(fib(624) = 624 (k=892) (c=15)
digsum(fib(781) = 781 (k=1105)
digsum(fib(1219) = 1219 (k=2037)

Previously Pre-Posted…

• Mötley Vüe — more on digsum(fib(k)) = k

Pi in the Bi

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

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


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

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


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

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


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

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


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

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


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

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

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

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

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

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

Graph for distinct sums of the integers 0 to 4

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

Graph for distinct sums of the integers 0 to 3

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


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

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

Graph for sums from 1 binary digit

Graph for sums from 2 binary digits

Graph for sums from 3 binary digits

Graph for sums from 4 binary digits

Graph for sums from 5 binary digits

Graph for sums from 6 binary digits

Graph for sums from 7 binary digits

Graph for sums from 8 binary digits

Graph for sums from 9 binary digits

Graph for sums from 10 binary digits

Graph for sums from 11 binary digits

Graph for sums from 12 binary digits

Graph for sums from 13 binary digits

Graph for sums from 14 binary digits

Graph for sums from 15 binary digits

Graph for sums from 16 binary digits

Graphs for 1 to 16 binary digits (animated)

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

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

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

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

Post-Performative Post-Scriptum

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


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

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

Primal Stream

by in Mathematics, Prime numbers and tagged , , , , , , , | Leave a comment

• 3, 7, 31, 127, 8191, 131071, 524287, 2147483647, 2305843009213693951, 618970019642690137449562111, 162259276829213363391578010288127, 170141183460469231731687303715884105727 — A000668, Mersenne primes (primes of the form 2^n – 1), at the Online Encyclopedia of Integer Sequences

• 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161, 74207281, 77232917, 82589933 — A000043, Mersenne exponents: primes p such that 2^p – 1 is prime. Then 2^p – 1 is called a Mersenne prime. […] It is believed (but unproved) that this sequence is infinite. The data suggest that the number of terms up to exponent N is roughly K log N for some constant K.

• The largest known prime number (as of May 2022) is 282,589,933 − 1, a number which has 24,862,048 digits when written in base 10. It was found via a computer volunteered by Patrick Laroche of the Great Internet Mersenne Prime Search (GIMPS) in 2018. — Largest known prime number

Root Pursuit

by in √2, Base Behavior, Integer Sequences, Irrational numbers, Mathematics, Powers, Square root of 2, Square Roots and tagged , , , , , , , , , , , , , , , , , , | Leave a comment

Roots are hard, powers are easy. For example, the square root of 2, or √2, is the mysterious and never-ending number that is equal to 2 when multiplied by itself:

• √2 = 1·414213562373095048801688724209698078569671875376948073...

It’s hard to calculate √2. But the powers of 2, or 2^p, are the straightforward numbers that you get by multiplying 2 repeatedly by itself. It’s easy to calculate 2^p:

• 2 = 2^1
• 4 = 2^2
• 8 = 2^3
• 16 = 2^4
• 32 = 2^5
• 64 = 2^6
• 128 = 2^7
• 256 = 2^8
• 512 = 2^9
• 1024 = 2^10
• 2048 = 2^11
• 4096 = 2^12
• 8192 = 2^13
• 16384 = 2^14
• 32768 = 2^15
• 65536 = 2^16
• 131072 = 2^17
• 262144 = 2^18
• 524288 = 2^19
• 1048576 = 2^20
[...]

But there is a way to find √2 by finding 2^p, as I discovered after I asked a simple question about 2^p and 3^p. What are the longest runs of matching digits at the beginning of each power?

• 131072 = 2^17
• 129140163 = 3^17
• 1255420347077336152767157884641... = 2^193
• 1214512980685298442335534165687... = 3^193
• 2175541218577478036232553294038... = 2^619
• 2177993962169082260270654106078... = 3^619
• 7524389324549354450012295667238... = 2^2016
• 7524012611682575322123383229826... = 3^2016

There’s no obvious pattern. Then I asked the same question about 2^p and 5^p. And an interesting pattern appeared:

• 32 = 2^5
• 3125 = 5^5
• 316912650057057350374175801344 = 2^98
• 3155443620884047221646914261131... = 5^98
• 3162535207926728411757739792483... = 2^1068
• 3162020133383977882730040274356... = 5^1068
• 3162266908803418110961625404267... = 2^127185
• 3162288411569894029343799063611... = 5^127185

The digits 31622 rang a bell. Isn’t that the start of √10? Yes, it is:

• √10 = 3·1622776601683793319988935444327185337195551393252168268575...

I wrote a fast machine-code program to find even longer runs of matching initial digits. Sure enough, the pattern continued:

• 316227... = 2^2728361
• 316227... = 5^2728361
• 3162277... = 2^15917834
• 3162277... = 5^15917834
• 31622776... = 2^73482154
• 31622776... = 5^73482154
• 3162277660... = 2^961700165
• 3162277660... = 5^961700165

But why are powers of 2 and 5 generating the digits of √10? If you’re good at math, that’s a trivial question about a trivial discovery. Here’s the answer: We use base ten and 10 = 2 * 5, 10^2 = 100 = 2^2 * 5^2 = 4 * 25, 10^3 = 1000 = 2^3 * 5^3 = 8 * 125, and so on. When the initial digits of 2^p and 5^p match, those matching digits must come from the digits of √10. Otherwise the product of 2^p * 5^p would be too large or too small. Here are the records for matching initial digits multiplied by themselves:

• 32 = 2^5
• 3125 = 5^5
• 3^2 = 9

• 316912650057057350374175801344 = 2^98
• 3155443620884047221646914261131... = 5^98
• 31^2 = 961

• 3162535207926728411757739792483... = 2^1068
• 3162020133383977882730040274356... = 5^1068
• 3162^2 = 9998244

• 3162266908803418110961625404267... = 2^127185
• 3162288411569894029343799063611... = 5^127185
• 31622^2 = 999950884

• 316227... = 2^2728361
• 316227... = 5^2728361
• 316227^2 = 99999515529

• 3162277... = 2^15917834
• 3162277... = 5^15917834
• 3162277^2 = 9999995824729

• 31622776... = 2^73482154
• 31622776... = 5^73482154
• 31622776^2 = 999999961946176

• 3162277660... = 2^961700165
• 3162277660... = 5^961700165
• 3162277660^2 = 9999999998935075600

The square of each matching run falls short of 10^p. And so when the digits of 2^p and 5^p stop matching, one power must fall below √10, as it were, and one must rise above:

• 3 162266908803418110961625404267... = 2^127185
• 3·162277660168379331998893544432... = √10
• 3 162288411569894029343799063611... = 5^127185

In this way, 2^p * 5^p = 10^p. And that’s why matching initial digits of 2^p and 5^p generate the digits of √10. The same thing, mutatis mutandis, happens in base 6 with 2^p and 3^p, because 6 = 2 * 3:

• 2.24103122055214532500432040411... = √6 (in base 6)

• 24 = 2^4
• 213 = 3^4
• 225522024 = 2^34 in base 6 = 2^22 in base 10
• 22225525003213 = 3^34 (3^22)
• 2241525132535231233233555114533... = 2^1303 (2^327)
• 2240133444421105112410441102423... = 3^1303 (3^327)
• 2241055222343212030022044325420... = 2^153251 (2^15007)
• 2241003215453455515322105001310... = 3^153251 (3^15007)
• 2241032233315203525544525150530... = 2^233204 (2^20164)
• 2241030204225410320250422435321... = 3^233204 (3^20164)
• 2241031334114245140003252435303... = 2^2110415 (2^102539)
• 2241031103430053425141014505442... = 3^2110415 (3^102539)

And in base 30, where 30 = 2 * 3 * 5, you can find the digits of √30 in three different ways, because 30 = 2 * 15 = 3 * 10 = 5 * 6:

• 5·E9F2LE6BBPBF0F52B7385PE6E5CLN... = √30 (in base 30)

• 55AA4 = 2^M in base 30 = 2^22 in base 10
• 5NO6CQN69C3Q0E1Q7F = F^M = 15^22
• 5E63NMOAO4JPQD6996F3HPLIMLIRL6F... = 2^K6 (2^606)
• 5ECQDMIOCIAIR0DGJ4O4H8EN10AQ2GR... = F^K6 (15^606)
• 5E9DTE7BO41HIQDDO0NB1MFNEE4QJRF... = 2^B14 (2^9934)
• 5E9G5SL7KBNKFLKSG89J9J9NT17KHHO... = F^B14 (15^9934)
[...]
• 5R4C9 = 3^E in base 30 = 3^14 in base 10
• 52CE6A3L3A = A^E = 10^14
• 5E6SOQE5II5A8IRCH9HFBGO7835KL8A = 3^3N (3^113)
• 5EC1BLQHNJLTGD00SLBEDQ73AH465E3... = A^3N (10^113)
• 5E9FI455MQI4KOJM0HSBP3GG6OL9T8P... = 3^EJH (3^13187)
• 5E9EH8N8D9TR1AH48MT7OR3MHAGFNFQ... = A^EJH (10^13187)
[...]
• 5OCNCNRAP = 5^I in base 30 = 5^18 in base 10
• 54NO22GI76 = 6^I (6^18)
• 5EG4RAMD1IGGHQ8QS2QR0S0EH09DK16... = 5^1M7 (5^1567)
• 5E2PG4Q2G63DOBIJ54E4O035Q9TEJGH... = 6^1M7 (6^1567)
• 5E96DB9T6TBIM1FCCK8A8J7IDRCTM71... = 5^F9G (5^13786)
• 5E9NM222PN9Q9TEFTJ94261NRBB8FCH... = 6^F9G (6^13786)
[...]

So that’s √10, √6 and √30. But I said at the beginning that you can find √2 by finding 2^p. How do you do that? By offsetting the powers, as it were. With 2^p and 5^p, you can find the digits of √10. With 2^(p+1) and 5^p, you can find the digits of √2 and √20, because 2^(p+1) * 5^p = 2 * 2^p * 5^p = 2 * 10^p:

•  √2 = 1·414213562373095048801688724209698078569671875376948073...
• √20 = 4·472135954999579392818347337462552470881236719223051448...

• 16 = 2^4
• 125 = 5^3
• 140737488355328 = 2^47
• 142108547152020037174224853515625 = 5^46
• 1413... = 2^243
• 1414... = 5^242
• 14141... = 2^6651
• 14142... = 5^6650
• 141421... = 2^35389
• 141420... = 5^35388
• 4472136... = 2^162574
• 4472135... = 5^162573
• 141421359... = 2^3216082
• 141421352... = 5^3216081
• 447213595... = 2^172530387
• 447213595... = 5^172530386
[...]

God Give Me Benf’

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

In “Wake the Snake”, I looked at the digits of powers of 2 and mentioned a fascinating mathematical phenomenon known as Benford’s law, which governs — in a not-yet-fully-explained way — the leading digits of a wide variety of natural and human statistics, from the lengths of rivers to the votes cast in elections. Benford’s law also governs a lot of mathematical data. It states, for example, that the first digit, d, of a power of 2 in base b (except b = 2, 4, 8, 16…) will occur with the frequency logb(1 + 1/d). In base 10, therefore, Benford’s law states that the digits 1..9 will occur with the following frequencies at the beginning of 2^p:

1: 30.102999%
2: 17.609125%
3: 12.493873%
4: 09.691001%
5: 07.918124%
6: 06.694678%
7: 05.799194%
8: 05.115252%
9: 04.575749%

Here’s a graph of the actual relative frequencies of 1..9 as the leading digit of 2^p (open images in a new window if they appear distorted):

And here’s a graph for the predicted frequencies of 1..9 as the leading digit of 2^p, as calculated by the log(1+1/d) of Benford’s law:

The two graphs agree very well. But Benford’s law applies to more than one leading digit. Here are actual and predicted graphs for the first two leading digits of 2^p, 10..99:

And actual and predicted graphs for the first three leading digits of 2^p, 100..999:

But you can represent the leading digit of 2^p in another way: using an adaptation of the famous Ulam spiral. Suppose powers of 2 are represented as a spiral of squares that begins like this, with 2^0 in the center, 2^1 to the right of center, 2^2 above 2^1, and so on:

←←←⮲
432↑
501↑
6789

If the digits of 2^p start with 1, fill the square in question; if the digits of 2^p don’t start with 1, leave the square empty. When you do this, you get this interesting pattern (the purple square at the very center represents 2^0):

Ulam-like power-spiral for 2^p where 1 is the leading digit

Here’s a higher-resolution power-spiral for 1 as the leading digit:

Power-spiral for 2^p, leading-digit = 1 (higher resolution)

And here, at higher resolution still, are power-spirals for all the possible leading digits of 2^p, 1..9 (some spirals look very similar, so you have to compare those ones carefully):

Power-spiral for 2^p, leading-digit = 1 (very high resolution)

Power-spiral for 2^p, leading-digit = 2

Power-spiral for 2^p, ld = 3

Power-spiral for 2^p, ld = 4

Power-spiral for 2^p, ld = 5

Power-spiral for 2^p, ld = 6

Power-spiral for 2^p, ld = 7

Power-spiral for 2^p, ld = 8

Power-spiral for 2^p, ld = 9

Power-spiral for 2^p, ld = 1..9 (animated)

Now try the power-spiral of 2^p, ld = 1, in some other bases:

Power-spiral for 2^p, leading-digit = 1, base = 9

Power-spiral for 2^p, ld = 1, b = 15

You can also try power-spirals for other n^p. Here’s 3^p:

Power-spiral for 3^p, ld = 1, b = 10

Power-spiral for 3^p, ld = 2, b = 10

Power-spiral for 3^p, ld = 1, b = 4

Power-spiral for 3^p, ld = 1, b = 7

Power-spiral for 3^p, ld = 1, b = 18

Elsewhere Other-Accessible…

• Wake the Snake — an earlier look at the digits of 2^p

Wake the Snake

by in √2, Base Behavior, Infinity, Integer Sequences, Language, Mathematics, Powers, Square root of 2 and tagged , , , , , , , , , , , , , | Leave a comment

In my story “Kopfwurmkundalini”, I imagined the square root of 2 as an infinitely long worm or snake whose endlessly varying digit-segments contained all stories ever (and never) written:

• √2 = 1·414213562373095048801688724209698078569671875376948073…

But there’s another way to get all stories ever written from the number 2. You don’t look at the root(s) of 2, but at the powers of 2:

• 2 = 2^1 = 2
• 4 = 2^2 = 2*2
• 8 = 2^3 = 2*2*2
• 16 = 2^4 = 2*2*2*2
• 32 = 2^5 = 2*2*2*2*2
• 64 = 2^6 = 2*2*2*2*2*2
• 128 = 2^7 = 2*2*2*2*2*2*2
• 256 = 2^8 = 2*2*2*2*2*2*2*2
• 512 = 2^9 = 2*2*2*2*2*2*2*2*2
• 1024 = 2^10
• 2048 = 2^11
• 4096 = 2^12
• 8192 = 2^13
• 16384 = 2^14
• 32768 = 2^15
• 65536 = 2^16
• 131072 = 2^17
• 262144 = 2^18
• 524288 = 2^19
• 1048576 = 2^20
• 2097152 = 2^21
• 4194304 = 2^22
• 8388608 = 2^23
• 16777216 = 2^24
• 33554432 = 2^25
• 67108864 = 2^26
• 134217728 = 2^27
• 268435456 = 2^28
• 536870912 = 2^29
• 1073741824 = 2^30
[...]

The powers of 2 are like an ever-lengthening snake swimming across a pool. The snake has an endlessly mutating head and a rhythmically waving tail with a regular but ever-more complex wake. That is, the leading digits of 2^p don’t repeat but the trailing digits do. Look at the single final digit of 2^p, for example:

• 02 = 2^1
• 04 = 2^2
• 08 = 2^3
• 16 = 2^4
• 32 = 2^5
• 64 = 2^6
• 128 = 2^7
• 256 = 2^8
• 512 = 2^9
• 1024 = 2^10
• 2048 = 2^11
• 4096 = 2^12
• 8192 = 2^13
• 16384 = 2^14
• 32768 = 2^15
• 65536 = 2^16
• 131072 = 2^17
• 262144 = 2^18
• 524288 = 2^19
• 1048576 = 2^20
• 2097152 = 2^21
• 4194304 = 2^22
[...]

The final digit of 2^p falls into a loop: 2 → 4 → 8 → 6 → 2 → 4→ 8…

Now try the final two digits of 2^p:

• 02 = 2^1
• 04 = 2^2
• 08 = 2^3
• 16 = 2^4
• 32 = 2^5
• 64 = 2^6
• 128 = 2^7
• 256 = 2^8
• 512 = 2^9
• 1024 = 2^10
• 2048 = 2^11
• 4096 = 2^12
• 8192 = 2^13
• 16384 = 2^14
• 32768 = 2^15
• 65536 = 2^16
• 131072 = 2^17
• 262144 = 2^18
• 524288 = 2^19
• 1048576 = 2^20
• 2097152 = 2^21
• 4194304 = 2^22
• 8388608 = 2^23
• 16777216 = 2^24
• 33554432 = 2^25
• 67108864 = 2^26
• 134217728 = 2^27
• 268435456 = 2^28
• 536870912 = 2^29
• 1073741824 = 2^30
[...]

Now there’s a longer loop: 02 → 04 → 08 → 16 → 32 → 64 → 28 → 56 → 12 → 24 → 48 → 96 → 92 → 84 → 68 → 36 → 72 → 44 → 88 → 76 → 52 → 04 → 08 → 16 → 32 → 64 → 28… Any number of trailing digits, 1 or 2 or one trillion, falls into a loop. It just takes longer as the number of trailing digits increases.

That’s the tail of the snake. At the other end, the head of the snake, the digits don’t fall into a loop (because of the carries from the lower digits). So, while you can get only 2, 4, 8 and 6 as the final digits of 2^p, you can get any digit but 0 as the first digit of 2^p. Indeed, I conjecture (but can’t prove) that not only will all integers eventually appear as the leading digits of 2^p, but they will do so infinitely often. Think of a number and it will appear as the leading digits of 2^p. Let’s try the numbers 1, 12, 123, 1234, 12345…:

• 16 = 2^4
• 128 = 2^7
• 12379400392853802748... = 2^90
• 12340799625835686853... = 2^1545
• 12345257952011458590... = 2^34555
• 12345695478410965346... = 2^63293
• 12345673811591269861... = 2^4869721
• 12345678260232358911... = 2^5194868
• 12345678999199154389... = 2^62759188

But what about the numbers 9, 98, 987, 986, 98765… as leading digits of 2^p? They don’t appear as quickly:

• 9007199254740992 = 2^53
• 98079714615416886934... = 2^186
• 98726397006685494828... = 2^1548
• 98768356967522174395... = 2^21257
• 98765563827287722773... = 2^63296
• 98765426081858871289... = 2^5194871
• 98765430693066680199... = 2^11627034
• 98765432584491513519... = 2^260855656
• 98765432109571471006... = 2^1641098748

Why do fragments of 123456789 appear much sooner than fragments of 987654321? Well, even though all integers occur infinitely often as leading digits of 2^p, some integers occur more often than others, as it were. The leading digits of 2^p are actually governed by a fascinating mathematical phenomenon known as Benford’s law, which states, for example, that the single first digit, d, will occur with the frequency log10(1 + 1/d). Here are the actual frequencies of 1..9 for all powers of 2 up to 2^101000, compared with the estimate by Benford’s law:

1: 30% of leading digits ↔ 30.1% estimated
2: 17.55% ↔ 17.6%
3: 12.45% ↔ 12.49%
4: 09.65% ↔ 9.69%
5: 07.89% ↔ 7.92%
6: 06.67% ↔ 6.69%
7: 05.77% ↔ 5.79%
8: 05.09% ↔ 5.11%
9: 04.56% ↔ 4.57%

Because (inter alia) 1 appears as the first digit of 2^p far more often than 9 does, the fragments of 123456789 appear faster than the fragments of 987654321. Mutatis mutandis, the same applies in all other bases (apart from bases that are powers of 2, where there’s a single leading digit, 1, 2, 4, 8…, followed by 0s). But although a number like 123456789 occurs much frequently than 987654321 in 2^p expressed in base 10 (and higher), both integers occur infinitely often.

As do all other integers. And because stories can be expressed as numbers, all stories ever (and never) written appear in the powers of 2. Infinitely often. You’ll just have to trim the tail of the story-snake.

Power Trap

by in Integer Sequences, Mathematics, Zeroes and tagged , , , , , , , | Leave a comment

Back in 2015, in an article called “Power Trip”, I looked at an unfamiliar sequence created by deleting zeroes from a familiar sequence. And I made a serious but fortunately-not-fatal error in my reasoning. The familiar sequence was powers of 2:

• 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576…

This is what happens when you delete the zeroes from the powers of 2 (and carry on multiplying by two):

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…


I pointed out that this new sequence has to repeat, because deleting zeroes prevents n growing beyond a certain size. Eventually, then, a number will repeat and the sequence will fall into a loop: “This happens at step 526 with 366784, which matches 366784 at step 490.”

But that’s deleting every zero. What happens if you delete every second zero? That is, you start with a zero-count, zc, of 0. When you meet the first zero in the sequence, zc = zc + 1 = 1. When you meet the second zero in the sequence, zc = zc + 1 = 2. So you delete that second zero and reset zc to 0. 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. The sequence for zc=2 looks 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

Again, the sequence has to repeat and I claimed that it did so “at step 9134 with 5458864, which matches 5458864 at step 4166”. I also said that I hadn’t found the loop for the delete-every-third-zero sequence, where zc=3. Coming back to this type of sequence in 2021, I wrote a much faster machine-code program to see if I could find the answer for zc=3. And I thought that I had. My program said that the sequence for zc=3 repeats at step 166369 with 6138486272, which matches 6138486272 at step 25429.

Or does it repeat? Does it match? In 2021 I suddenly realized that I had neglected to consider something vital back in 2015: whether the zero-count was the same when the sequence appeared to repeat. Take the zc=2 sequence. If zc=0 at at step 4166 and zc=1 at 9134 (or vice versa), the sequence isn’t in a loop, because it will be deleting a different set of zeroes after step 4166 than it is after step 9134.

I checked whether the zero-count for that sequence is the same when the sequence appears to repeat. Fortunately, it is the same and the zero-delete sequence for zc=2 does indeed begin looping “at step 9134 with 5458864, which matches 5458864 at step 4166”.

So my error wasn’t fatal for the zc=2 sequence. But what about the zc=3 sequence? Alas, the zero-count is different for 6138486272 at step 166369 than for 6138486272 at step 25429. The sequence doesn’t behave the same after those steps and hasn’t looped. I needed to find the n1 = n2 for steps s1 and s2 where zc1 = zc2. And even with the much faster machine-code program it took some time. But I can now say that 958718377984 at step 379046, with zc=0, matches 958718377984 at step 200906, with zc=0.

Z-Fall

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

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

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

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

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

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


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

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


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

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

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


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

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


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

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


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

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


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

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


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

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

For Revver and Fevver

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

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

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…