Number theory at the card table

Mental division by 7 ♦

The fact 8 shuffles restore a deck to its original order is a kind of cycle. If you were to do 16 shuffles, you’d also end up at the same place.

One of the places that cycles first show up when learning mathematics in school is in the decimal expansions of fractions. Here’s all the fractions with 1 as their numerator, up to twelfths:

(here, a vertical bar over a section of the number indicates that it repeats forever from that point). The ugliest-looking and most difficult to remember of these is definitely $1/7 = 0.\overline{142857}$. As you might expect, the situation isn’t any better for any of the other sevenths:

If you look for a moment, you might be able to spot the structure here. It helps if you reorder from the numerators being $1,2,3,4,5,6$ to the numerators being $1,3,2,6,4,5$:

Now it’s the same cycle every time, but successively shifted one decimal place. This observation forms the basis of a mental calculation trick called “magic sevenths”, which allows you to work out the decimal expansion of any division by seven, almost instantly. Here’s how you can do it:

First, memorise the “cycle list” $1,4,2,8,5,7$ and the “offset list” $1,3,2,6,4,5$. Suppose you need to calculate the decimal expansion for something like $65/7$. First you, reduce it from a “top heavy” fraction into a mixed fraction:

In other words, find the quotient and remainder. In this case, the quotient is $9$, and the remainder is $2$.

Then the cycle and offset list give you a recipe for the expansion of $2/7$: $2$ is in the 3rd place of the offset list, so you begin the cycle three places along the cycle to obtain: $2,8,5,7,1,4$. This means that $2/7 = 0.285714$. Then to get the final result for $65/7$, you stick together the $9$ and $2/7$:

This is equivalent to a program like:

cycle   = "142857"
offsets = "132645"

# The inputs
numerator   = 65
denominator = 7

# Here "//" is integer division
quotient  = numerator // denominator
remainder = numerator % denominator

start_pos = offsets.index(str(remainder))

# Modify the cycle to start at 
new_cycle = cycle[start_pos:] + cycle[:start_pos]

print(remainder)
print(".")

while True:
  print(new_cycle)

There are spades of questions you could ask about this:

• Why is the cycle six numbers long?
• What happens in fractions other than sevenths?
• What happens if instead of decimal you use some other base, like binary?
• Where do the offset list and cycle list come from?

It turns out that these questions are intimately related to the questions raised about perfect riffle shuffling.

Division by other numbers and in other bases ♦

A few moments ago we were considering the “magic sevenths”:

This raised the following questions:

• Why is the cycle six numbers long?
• What happens in fractions other than sevenths?
• What happens if instead of decimal you use some other base, like binary?
• Where do the offset list and cycle list come from?

The answer to the first question is not just that because 6 is one less than 7. This is evident looking at fractions with other denominators. For example, thirteenths have more complex behaviour:

Here there are in fact there are two cycles: one for fractions with numerator $1, 3, 4, 9, 10, 12$ and one for the others: $2, 5, 6, 7, 8, 11$. You could use this to come up with a “magic thirteenths” trick based on this for calculating divisions by thirteen exactly, and it would only be marginally more useless than the trick for sevenths.

But why do these cycles in the first place? Going back to sevenths, things are clearer if you probe the digits in the expansion by multiplying by 10 to shift the decimal point one place across:

Or, using fractions:

Equating the right hand sides of both of these equations says that:

So after subtracting 1 from both sides, this explains why $3/7 = 0.\overline{428571}$. To verify that the cycle continues on, multiplying by 10 again shows that:

and so similarly $2/7 = 0.\overline{428571}$. This process explains the numbers in the original “offset list”: $1, 3, 2, 6, 4, 5$.

The reason it repeats after 6 digits is that if you multiply $1/7$ by $10^6 = 1,000,000$ to shift the decimal place along 6 times, you get:

Since $142,857.\overline{142857} = 142,857 + 1/7$, this cycle must repeat after six decimal digits.

Similarly, this also explains the two cycles of length 6 for thirteenths. Since the cycle also appears to be 6 digits long, multiplying again by $10^6$ shows:

Furthermore, the other cycle starting with $2/13$ also repeats after 6 digits:

You also need to be careful to check that the cycle doesn’t repeat after three digits, which can be checked by multiplying by $10^3$; this doesn’t lead you back to the fraction you started with.

You can explore fractions like this in other bases. Consider the binary expansion of $1/3$:

(here the subscripts indicate the base that should be used to interpret the expression). To shift the “binary point”, you multiply by two. So to shift two places, you multiply by $2^2$:

If you can spot the modular arithmetic lurking behind the scenes here, then maybe connection between repeating fractions and perfect riffle shuffling should be becoming clear. But first, the initial question: why exactly 8 riffle shuffles?

Why exactly does this fraction cycle like it does? ♦

For the final piece of the puzzle, let’s link this to the behaviour of cycling fractions in base 2. A moment ago, we saw that the reason that $1/3$ has a 2-bit cycling binary expansion is because:

In the general case, a fraction $1/m$ will cycle with period $s$ in binary if shifting the binary point $s$ places gives you a whole part $w$ plus the original fraction back:

This is equivalent to saying that dividing $2^s$ by $m$ has quotient $w$ and remainder $1$. For example in the case of $2^2/3$, has whole part $1$ and remainder $1$.

But the condition that “dividing $2^s$ by $m$ has quotient $w$ and remainder $1$” is exactly the following condition in modular arithmetic:

Which is almost exactly the condition we had for perfect riffle shuffling! If $m = 51$, then the first non-zero $s$ for which the equation

holds is $s = 8$ – this corresponds exactly with the fact that the binary expansion of $1/51$ repeats with period 8!