## Description

This article is from the Puzzles FAQ,
by Chris Cole chris@questrel.questrel.com and Matthew Daly
mwdaly@pobox.com with numerous contributions by others.

# 76 arithmetic/digits/rotate.p

Find integers where multiplying them by single digits rotates their digits

one position, so that the last digit become the first digit.

arithmetic/digits/rotate.s

2 105263157894736842

3 1034482758620689655172413793

4 102564 153846 179487 205128 230769

5 142857 102040816326530612244897959183673469387755

6 1016949152542372881355932203389830508474576271186440677966

1186440677966101694915254237288135593220338983050847457627

1355932203389830508474576271186440677966101694915254237288

1525423728813559322033898305084745762711864406779661016949

7 1014492753623188405797 1159420289855072463768 1304347826086956521739

8 1012658227848 1139240506329

9 10112359550561797752808988764044943820224719

In base B, suppose you have an N-digit answer A whose digits are

rotated when multiplied by K. If D is the low-order digit of A, we

have

(A-D)/B + D B^(N-1) = K A .

Solving this for A we have

D (B^N - 1)
A = ----------- .
B K - 1

In order for A >= B^(N-1) we must have D >= K. Now we have to find N

such that B^N-1 is divisible by R=(BK-1)/gcd(BK-1,D). This always has

a minimal solution N0(R,B)<R, and the set of all solutions is the set

of multiples of N0(R,B). N0(R,B) is the length of the repeating part

of the fraction 1/R in base B.

N0(ST,B)=N0(S,B)N0(T,B) when (S,T)=1, and for prime powers, N0(P^X,B)

divides (P-1)P^(X-1). Determining which divisor is a little more

complicated but well-known (cf. Hardy & Wright).

So given B and K, there is one minimal solution for each

D=K,K+1,...,B-1, and you get all the solutions by taking repetitions

of the minimal solutions.

Continue to: