When students learn about decimals, they’re told that every fraction either has a terminating decimal expansion or a repeating decimal expansion. The previous post gives a constructive proof of the converse: given a repeating fraction (in any base) it shows how to find what rational number it corresponds to.

Maybe you learned this so long ago that it seems obvious. But here’s a corollary that I don’t believe is so obvious.

For any positive integer n and for any integer b > 1, with n and b relatively prime, there is some number of the form b^k – 1 which is divisible by n.

So if I take some number, say 37, I can find a hexadecimal number consisting entirely of Fs which is divisible by 37. In fact FFFFFFFFF will do the trick. This is just the statement above with b = 16.

How does this follow from every rational number having a repeating decimal expansion?

Write 1/n as a repeating decimal in base b. (The assumption that n and b are relatively prime implies that the decimal repeats.) If the period of this decimal is k, then the previous post shows that 1/n is a multiple of 1/(b^k – 1). It follows that n is a divisor of b^k – 1.

Related post: A bevy of ones

My previous post ended with a discussion of repeating binary decimals such as

0.00110011…_two = 1/5.

For this post I’ll explain how calculations like that are done, how to convert a repeating decimal in any base to a fraction.

First of all, we only need to consider repeating decimals of the form

0.1_b, 0.01_b, 0.001_b, etc.

because every repeating decimal is an integer times an expression like one above. For example,

0.424242… = 42 × 0.010101…

You can think of that example as base 10, but it’s equally true in any base that has a 4, i.e. any base greater than 4.

Now suppose we have an expression

in base b.

We can see that this expressions is

by summing a geometric series.

So going back to our example above,

If we’re working in base 10, this equals 1/99. If we’re working in hexadecimal, this is 1/FF_hex = 1/255.

I’ll finish with a duodecimal example. Suppose we have

0.7AB7AB7AB…_twelve

and want to convert it to a fraction. We have

Or 1139/1727 in base 10.

Yesterday I wrote about the bits in powers of 3. That post had a low-resolution image, which has its advantages, but here’s a higher resolution image that also has its advantages.

The image looks chaotic. I say this in the colloquial sense, not in the technical sense as in period three implies chaos. I just mean that the image looks noisy.

And yet every vertical slice of this image is periodic! The last n bits of each row depend only on the last n bits of its predecessor, and there are only 2ⁿ possible last bits. Some pattern of last n bits must reappear eventually, and when it does, the pattern will repeat from that point on.

To make this easier to see, imagine rotating the image above counterclockwise by 90 degrees. The rows in the image below correspond to the columns in the image above. I’ll print both the bit values and an on/off visualization as in the previous couple posts.

Here’s the code that produced the image.

for k in range(6):
    bits = [(3**i & 2**k) >> k for i in range(64)]
    for bit in bits:
        print(bit, end='')
    print()  
    for bit in bits:
        print(chr(0x2588) if bit else ' ', end='')
    print("\n")

The array bits contains the first 64 bits in column number k, numbering columns from the right. That is, it contains the kth least significant bit of the first 64 powers of 3.

Now when I see a repeating pattern of digits, I think of decimal representations of rational numbers. If we put “0.” in front of the bit sequences above and think of them fractions, is there a pattern to these fractions?

In base two we have

    0.11111111... = 1
    0.01010101... = 1/3
    0.00000000... = 0
    0.00110011... = 1/5
    0.00011110... = 2/17

Can you detect a pattern in the rational numbers on the right side?

I was curious about the orders of the sporadic groups, specifically their prime factors, so I made a bar graph to show how often each factor appears.

To back up a little bit, simple groups are to groups roughly what prime numbers are to integers. Finite simple groups have been fully classified, and they fall into several infinite families of groups, except for 26 misfits, the so-called sporadic groups. The largest of these is nicknamed The Monster and has surprising connections to various areas of math.

One thing that jumps out  is that the order of every sporadic group is divisible by 2, 3, and 5. (In fact they’re all divisible by 120, i.e. by 2³, 3, and 5.) Another is that all the primes between 2 and 71 appear somewhere, except 53 and 61 are missing.

I don’t know whether there’s any significance to these patterns. Maybe they’re a simple consequence of things that people who work in this area know. I’m just noodling around here.

The Python code that produced the plot is given below.

Related posts

• The Monster
• Orders of the finite simple groups
• John Conway and the opposite of Parkinson’s law

from sympy import primefactors
from collections import Counter
import matplotlib.pyplot as plt

orders = [
    95040, 
    175560, 
    443520, 
    604800, 
    10200960, 
    17971200, 
    44352000, 
    50232960, 
    244823040, 
    898128000, 
    4030387200, 
    145926144000, 
    448345497600, 
    460815505920, 
    95766656000, 
    42305421312000, 
    64561751654400, 
    273030912000000, 
    51765179004000000, 
    90745943887872000, 
    4089470473293004800, 
    4157776806543360000, 
    86775571046077562880, 
    1255205709190661721292800, 
    4154781481226426191177580544000000, 
    808017424794512875886459904961710757005754368000000000
]

c = Counter()
for o in orders:
    for f in primefactors(o):
        c[f] += 1

factors = sorted(c.keys())
frequencies = [c[k] for k in factors]

fig, ax = plt.subplots()
ax.bar([str(f) for f in factors], frequencies)
ax.set_xlabel("prime factor")
ax.set_ylabel("Number of groups")
ax.set_title("Prime factors of sporadic group orders")

This post will look at the “tower of powers”

and ask what it means, when it converges, and how to compute it. Along the way I’ll tie in two recent posts, including one that should come as a surprise.

First of all, the expression is right-associative. That is, it is the limit of

x^(x^(x^…))

and not the limit of

((x^x)^x)^…)

This means we evaluate our tower from the top down, which is a little strange to think about. But if we interpreted our tower as left-associative, building the tower from the bottom up, the sequence would be much less interesting: the limit would be 1 for 0 < x ≤ 1, and infinity for x > 1.

A few weeks ago I wrote about the special case of x equal to the imaginary unit. I looked at the sequence

and the pattern the it makes in the complex plane.

We can see that the iterates converge to somewhere around 0.4 + 0.4i.

This post will replace i with a real number x. Leonard Euler discovered a long time ago that the “tower of power” converges for x between e^–e and e^1/e. See[1].

Furthermore, for those x‘s where the sequence converges, it converges to an expression involving the Lambert W function which I wrote about in my previous post.

The power tower can be written in Donald Knuth’s up arrow notation as the limit of

as n goes to infinity. The equation relating this limit to Lambert’s W function is

Let’s try this out numerically. Euler tells us the limit exists for x in the interval [e^–e ,  e^1/e] which is roughly [0.07, 1.44].

We’ll do this at the Python REPL. First we import functions to compute log and W.

    >>> from math import log
    >>> from scipy.special import lambertw as w

Now if we have correctly found our limit y, then x^y should equal y. The following shows that this is the case.

    >>> x = 0.07
    >>> y = -w(-log(x))/log(x)
    >>> y
    0.37192832251839264
    >>> x**y
    0.37192832251839264

    >>> x = 1.44
    >>> y = -w(-log(x))/log(x)
    >>> y
    2.3938117482029475
    >>> x**y
    2.393811748202947

By the way, we’ve said which real values of x cause the series to converge. But my first post on iterated powers looked at x = i. For which complex values does the series converge? I suspect the domain is a complicated fractal, but I don’t know that for sure.

Related posts

• i^i^i…
• Lambert W strikes again

[1] Brian Hayes. Why W? American Scientist. Vol 93, pp 104–109.