Python初心者です。
以下の式を割り切れるような素数pを求めるという問題を解きたいのですが、レピュニット数(と思われる)をPythonでどのように作って処理すればいいのかわかりません。
1+10+10^2+・・・+10^(p-1)
色々調べてみたのですがわからないままです。
回答、アドバイスいただければと思います。
※ネタバレ注意:この回答は「どのような素数 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 の整数は任意精度なのでそのまま代入してあげればその後の計算もよしなに行ってくれます(ただし計算に時間がかかるかもしれません)。実際、Python のドキュメントにも次のように書かれています:
https://docs.python.org/ja/3/library/stdtypes.html#numeric-types-int-float-complex
整数には精度の制限がありません。
という訳でとりあえず何も気にせずにプログラムを書いてみましょう。まずは n = 1+10+10^2+...+10^(p-1) が無いと話にならないのでこれを計算してみます。定義の式からして繰り返し足し算する形になっているので、for 文を使えば計算できそうです。たとえば下のように書けます。
def repunit(p):
n = 0
for i in range(p):
n += 10 ** i
return n
実際に結果を出力してみるとこんな感じです。
for p in [2, 3, 5, 7, 11]:
print(p, repunit(p))
2 11
3 111
5 11111
7 1111111
11 11111111111
良さそうですね。後は実際に p
で割った余りを求めればその p
が条件を満たすのかどうかが分かります。素数は無限個あるので、とりあえず 100 より小さい素数までで試してみました。
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)
実行結果:Wandbox
p = 3 のとき以外は割り切れていなさそうです。
さて、とりあえず今回は定義に沿ってそのまま n = 1+10+10^2+...+10^(p-1) を計算してみましたが、この計算方法だと p 回繰り返さないといけないため p が大きくなるにつれ n を求めるのに時間がかかってしまいます(実際に p を大きくして計算させてみてください)。もっと直接的に求めることはできないでしょうか。
n = 1+10+10^2+...+10^(p-1) は等比数列の和として見ることができます。したがって分数の形に書き直すことができて、n = (10^p - 1) / 9 です。言い方を変えると、1 がたくさん並んだ数を作るには、1000...000 から 1 引いて 9 で割れば良いです。
この考え方で関数を作り直すとこうなります。
def repunit(p):
return (10 ** p - 1) // 9
この関数を使えば、そこそこ大きめの素数に対しても現実的な時間で計算ができます。無茶苦茶大きな素数に対してはこの方法でも時間や空間(メモリ)が足りなくなってくるので、別の方法を考える必要があるでしょう。たとえば筆算を自分でやるなど。
※ここからネタバレです。
ところでここまで考える内に、元々の問題は「素数 p は n = (10^p - 1) / 9 を割り切れるか?」という形に変えることができました。プログラムを実行する限りは割り切れることが無さそうですが、p をどんどん大きくしていっても割り切れないのでしょうか?
p が 10 より大きいときを考えてみましょう。p は 10 より大きな素数なので、10 と p は互いに素です。したがってフェルマーの小定理より 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 のみです。
int('1' * p)
とできます。