Rotate to Double

“ASICs and B6 are making me sea sicks.”

                                  White Board in Derby

Suppose we wish to find an integer, expressed in decimal notation, such that rotating the digits one place to the right doubles the number. Thus we seek a j-digit integer N and a single digit d such that

From this we get the condition

Clearly d is co-prime to 19, so 19 must divide 10^j – 2, meaning that 10^j must be congruent to 2 modulo 19. Now, for convenience we define the integer ϕ = 10N+1, which implies N = (ϕ−1)/10. Substituting this into the above expression, multiplying through by 10, and putting d=1 (as a trial), gives

and hence

Consequently, 10^j+1 – 1 must be divisible by 19, which first occurs with j=17 (because the period of 10 modulo 19 is 18). Thus we have

By construction, these are the repeating digits of 1/19 = 0.0526315… We have expressed this as an 18-digit number by including a leading zero. As discussed in another note, if g divides both an 18-digit number ϕ and 10¹⁸ – 1, then g also divides all the rotations of ϕ. For example, the first rightward rotation of ϕ is

In fact, beginning with ϕ itself, each of the rightward rotations is of the form kϕ for some k from 1 to 18, where the k factors are

Each number in this sequence is simply double the previous number modulo 19. Also, the least significant digit of each of these is equal to the digits of ϕ, from least to most significant. Solutions of the original problem are given by consecutive numbers in the ratio 1:2, so we have the solutions 1:2, 2:4, 4:8, 7:14, 9:18, 3:6, 6:12, and 5:10.

We also note that the shifted cycle of digits of ϕ is the 9’s complement of itself, i.e.,

Naturally this doesn’t just apply to the base 10. For example, in the base B=6 we can generate the sequence of numbers by doubling modulo 2B−1 = 11, which gives

These values, modulo 6, give the digits of ϕ, so we have (in the base 6)

Again, by construction, these are the repeating digits (in base 6) of 1/11 = 0.031345…  The successive rightward rotations of this number give 2ϕ, 4ϕ, 8ϕ, 5ϕ, 10ϕ, 9ϕ, 7ϕ, 3ϕ, and 6ϕ. Thus solutions of the original problem correspond to 1:2, 2:4, 4:8, 5:10, and 3:6.

In this way we can easily find the minimal “rotate to double” solutions for each base B. The table below shows these solutions for the bases from 2 to 10.

In each case, the digits from least to most significant consist of the sequence of powers 2⁰, 2¹, 2², 2³, … evaluated modulo 2B−1, and then the result of that is evaluated modulo B. For example, with B=10, the 7^th place digit (i.e., the coefficient of 10⁷) is given by evaluating 2⁷ = 128 modulo 19, which gives 14, and then evaluating this modulo 10, which gives 4. Note that this two-stage modulo operation is different than just evaluating 2⁷ modulo 10.  The number of digits in these minimal solutions just corresponds to the order of 2 modulo 2B−1, so if 2B−1 is a prime p the number of digits is a divisor of p−1 = 2(B−1). If 2B−1 is composite, the number of digits depends on the order of 2 modulo the prime factors. These solutions are just the repeating digits of 1/(2B−1) written in the base B.

This approach isn’t limited to doubling, it can be applied to any ratio. For example, remaining in the base B=6, we can find numbers whose rotations give triples by generating the powers of 3 modulo 3(6)−1 = 17, which gives

These values, modulo 6, give the digits of ϕ, so we have (in the base 6)

These are the repeating digits (in base 6) of 1/17, as shown by the identity

The successive rightward rotations of this ϕ give 3ϕ, 9ϕ, 10ϕ, 13ϕ, 5ϕ, 15ϕ, 11ϕ, 16ϕ, 14ϕ, 8ϕ, 7ϕ, 4ϕ, 12ϕ, 2ϕ, and 6ϕ. Thus the tripling rotations correspond to 1:3, 3:9, 5:15, 4:12, and 2:6.

In general, to find the minimal solutions that rotating the number in base B one digit to the right increases the number by a factor c, we simply evaluate c⁰, c¹, c², c³, … modulo cB−1 (which gives the multiples of ϕ), and then evaluate those numbers modulo B to give the digits from least to most significant. (The most significant will be 0). These are always the repeating digits of 1/(cB−1).

Return to MathPages Main Menu