74781


Python初心者です。

以下の式を割り切れるような素数pを求めるという問題を解きたいのですが、レピュニット数(と思われる)をPythonでどのように作って処理すればいいのかわかりません。

[code]

    1+10+10^2+・・・+10^(p-1)
    
[/code]

色々調べてみたのですがわからないままです。  
回答、アドバイスいただければと思います。


CC BY-SA 4.0
2021-03-20T07:25:33.353
74777
2021-03-20T11:31:34.423
2021-03-20T09:58:19.953
19110
question
python
Pythonを使ってレピュニット数を表現し、整数問題を解きたい


> int('1' * p)

と書くことで解決いたしました。  
コメントくださった方、ありがとうございました。


CC BY-SA 4.0
2021-03-20T09:17:36.590
74779
2021-03-20T09:17:36.590
74777
answer


※ネタバレ注意：この回答は「どのような素数 p
が質問文の条件を満たすのか」についてネタバレを書いてしまっています。もしご自身で解きたい場合はご注意ください。

短い答え：Python であれば、定義にそって for 文で足し上げていくだけでとりあえずは大丈夫です。

以下、長い答えです。

## プログラムで検算してみる

素数 p について、n = 1+10+10^2+...+10^(p-1) を p
が割り切ることができるのかどうかについて考えてみましょう。試しに手で計算してみます。p = 2 のときは n = 11 であり、割り切れません。p = 3
のときは n = 111 であり、割り切れます。p = 5 のときは n = 11111 であり、割り切れません。p = 7 のときは n =
1111111 であり、割り切れません。とりあえず割り切れるときと割り切れないときがあることは分かりました。

このようなことをプログラムで計算してみましょう。一般に n = 1+10+10^2+...+10^(p-1) という数は p
が大きくなるにつれてどんどん大きくなっていきます。多くのプログラミング言語では大きな整数をそのままは扱えないので注意が必要ですが、Python
の整数は[任意精度](https://ja.wikipedia.org/wiki/%E4%BB%BB%E6%84%8F%E7%B2%BE%E5%BA%A6%E6%BC%94%E7%AE%97)なのでそのまま代入してあげればその後の計算もよしなに行ってくれます（ただし計算に時間がかかるかもしれません）。実際、Python
のドキュメントにも次のように書かれています：

<https://docs.python.org/ja/3/library/stdtypes.html#numeric-types-int-float-
complex>

> 整数には精度の制限がありません。

という訳でとりあえず何も気にせずにプログラムを書いてみましょう。まずは n = 1+10+10^2+...+10^(p-1)
が無いと話にならないのでこれを計算してみます。定義の式からして繰り返し足し算する形になっているので、for
文を使えば計算できそうです。たとえば下のように書けます。

[code]

    def repunit(p):
        n = 0
        for i in range(p):
            n += 10 ** i
        return n
    
[/code]

実際に結果を出力してみるとこんな感じです。

[code]

    for p in [2, 3, 5, 7, 11]:
        print(p, repunit(p))
    
[/code]

[code]

    2 11
    3 111
    5 11111
    7 1111111
    11 11111111111
    
[/code]

良さそうですね。後は実際に `p` で割った余りを求めればその `p` が条件を満たすのかどうかが分かります。素数は無限個あるので、とりあえず 100
より小さい素数までで試してみました。

[code]

    PRIMES_LESS_THAN_100 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
    
    for p in PRIMES_LESS_THAN_100:
        mod = repunit(p) % p
        print(p, mod)
    
[/code]

実行結果：[Wandbox](https://wandbox.org/permlink/JanOEaEGaFldIgOO)

p = 3 のとき以外は割り切れていなさそうです。

## 他の表現方法を考える

さて、とりあえず今回は定義に沿ってそのまま n = 1+10+10^2+...+10^(p-1) を計算してみましたが、この計算方法だと p
回繰り返さないといけないため p が大きくなるにつれ n を求めるのに時間がかかってしまいます（実際に p
を大きくして計算させてみてください）。もっと直接的に求めることはできないでしょうか。

n = 1+10+10^2+...+10^(p-1)
は等比数列の和として見ることができます。したがって[分数の形に書き直すこと](https://ja.wikipedia.org/wiki/%E7%AD%89%E6%AF%94%E6%95%B0%E5%88%97#%E7%AD%89%E6%AF%94%E6%95%B0%E5%88%97%E3%81%AE%E5%92%8C)ができて、n
= (10^p - 1) / 9 です。言い方を変えると、1 がたくさん並んだ数を作るには、1000...000 から 1 引いて 9 で割れば良いです。

この考え方で関数を作り直すとこうなります。

[code]

    def repunit(p):
        return (10 ** p - 1) // 9
    
[/code]

この関数を使えば、そこそこ大きめの素数に対しても現実的な時間で計算ができます。無茶苦茶大きな素数に対してはこの方法でも時間や空間（メモリ）が足りなくなってくるので、別の方法を考える必要があるでしょう。たとえば筆算を自分でやるなど。

## 数学に戻って考えてみる

※ここからネタバレです。

ところでここまで考える内に、元々の問題は「素数 p は n = (10^p - 1) / 9
を割り切れるか？」という形に変えることができました。プログラムを実行する限りは割り切れることが無さそうですが、p
をどんどん大きくしていっても割り切れないのでしょうか？

p が 10 より大きいときを考えてみましょう。p は 10 より大きな素数なので、10 と p
は互いに素です。したがって[フェルマーの小定理](https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A7%E3%83%AB%E3%83%9E%E3%83%BC%E3%81%AE%E5%B0%8F%E5%AE%9A%E7%90%86)より
10^(p-1) を p で割った余りは 1 です。したがって 10^p - 1 を p で割った余りは 9 です。つまり n = (10^p - 1) /
9 を p で割った余りは 1 であり、割り切れません。

p が 10 以下のときは、p = 2, 3, 5, 7 を考えれば良いです。実際に手で計算してみると p = 3 のとき以外は割り切れません。p = 3
のときだけ割り切れます。

したがって、n を割り切るような素数 p は 3 のみです。


CC BY-SA 4.0
2021-03-20T09:48:33.637
74781
2021-03-20T11:31:34.423
2021-03-20T11:31:34.423
19110
19110
74777
answer