巡回数とは

巡回数(Wikipedia)にあるように「2倍、3倍、4倍...と乗算したときに、その各桁の数を順序を崩さずに巡回させた数になる整数である。ダイヤル数ともいう」。142857はよく知られていますが、それ以降の求め方は見当たらなかったので今回調べてみました。（ただし142857以外の巡回数は先頭に$0$が付きます）

生成の方法に関してはCyclic Number (Wolfram MathWorld)に記述がありました。

Cyclic Numberは"full reptend primes"から生成される

とありそのFull Reptend Primeとは何かを見ると、

10が原始根になる素数pはFull Reptendである

とあります。これはどこかで聞いたなと思って調べてみると、自分の記事【Project Euler】Problem 26: 循環小数で書いた、$1/p$が最長の循環小数になる条件と同じであることに気づきました。

巡回数の生成アルゴリズム

従って結論から言うと10が原始根になる素数pに対して以下の式で巡回数が求まります。

CyclicNumber = \frac{10^{p-1}-1}{p}

100以下の素数で生成すると以下のようになります。基本的には$1/p$の循環小数の循環節と同じなので$p=17$以降は先頭に$0$が付き、これを含めて巡回します。

from sympy.ntheory import is_primitive_root
from sympy import primerange

for p in primerange(7,10**2):
  if is_primitive_root(10, p):
    print(f"{p}:{(10**(p-1)-1)//p:0{p-1}}")
# 7:142857
# 17:0588235294117647
# 19:052631578947368421
# 23:0434782608695652173913
# 29:0344827586206896551724137931
# 47:0212765957446808510638297872340425531914893617
# 59:0169491525423728813559322033898305084745762711864406779661
# 61:016393442622950819672131147540983606557377049180327868852459
# 97:010309278350515463917525773195876288659793814432989690721649484536082474226804123711340206185567

ただ$p-1$の桁数がどんどん増えてしまうのでちょっと面白味がなくなってしまいますが、少し視点を変えた例題を考えてみます。

【例題 1】下４桁が6789になるような最小の巡回数を生成する素数を求めよ

$10^4$で割った余りが6789ということなので、以下の式を満たす最小の$p$がその解です。巡回数その物を求める必要はありません

 \frac{10^{p-1}-1}{p} = \frac{-1}{p} = 6789 \pmod{10^4} \\

プログラムですが$p$が分母に来ているのでmod_inverseを使います。

from sympy.ntheory import is_primitive_root
from sympy import primerange, mod_inverse

M = 10**4
for p in primerange(7,10**6):
  if is_primitive_root(10, p) and (mod_inverse(p,M)*(-1)%M) == 6789 : 
    print(p)
    break
# 49891

【例題 2】下４桁が6789になるような最小の巡回数の数字和（各桁の和）を求めよ

今度こそ巡回数$(49891-1)$桁すべてを求める必要があるように見えますが。実は巡回数の数字和にはある規則性があります。具体的に100以下の素数から生成された巡回数の数字和を求めて桁数$p-1$で割ってみると必ず$4.5$となり、その規則はそれ以降の巡回数にも適用されます。

def digitsum(n):
  return sum(map(int,str(n)))
for p in primerange(7,10**2):
  if is_primitive_root(10, p):
    cn = (10**(p-1)-1)//p
    ds = digitsum(cn)
    print(f"p={p:2}:digit sum={ds:3} / {ds/(p-1)} per digit")
# p= 7:digit sum= 27 / 4.5 per digit
# p=17:digit sum= 72 / 4.5 per digit
# p=19:digit sum= 81 / 4.5 per digit
# p=23:digit sum= 99 / 4.5 per digit
# p=29:digit sum=126 / 4.5 per digit
# p=47:digit sum=207 / 4.5 per digit
# p=59:digit sum=261 / 4.5 per digit
# p=61:digit sum=270 / 4.5 per digit
# p=97:digit sum=432 / 4.5 per digit

従って例題 2の以下のように電卓で答えを出すことが出来ました。

(49891-1)*4.5 = 224505

（開発環境：Google Colab）

この記事はProject Euler: Problem 358 Cyclic numbersを解くのに役に立ちます。