数学の力

京大生が数学の定理・公式の証明や入試問題の解説をするブログ.

プロジェクトオイラー4. ~ Largest palindrome product ~


スポンサードリンク

No.4 Largest palindrome product

問題.

Q. 回文数(palindrome number) とは, 左右どちらから読んでも同じになる数です. (例えば, 12021 や, 148841)

2桁の数2つの積として表される最大の回文数は,  9009=91\times 99 です.

3桁の数2つの積として表される最大の回文数はいくらか.

 

考え方とプログラム例(Python3)

1. 3桁の数の積のうち, 回文数になっているものを探す

2つの3桁の数を  p, q\quad(100\leqq p\leqq q<1000) として, その積  pq回文数になっているかを調べ, 積が最大となるものを出力します.

 

Max = [0, 0, 0]
for p in range(100, 1000):
    for q in range(p, 1000):
        n = p * q
        if str(n)[::-1] == str(n):
            if Max[0] < n:
                Max = [n, p, q]
print(str(Max[0]) + "=" + str(Max[1]) + "*" + str(Max[2]))

 

2. 6桁の回文数のうち, 3桁の数の積で書けるものを探す

3桁の数2つの積は5桁または6桁です.

(最小で 100\times 100=10000, 最大で 999\times 999 < 1000\times1000=1000000.)

 

最大のものを求めればよいので, 6桁の回文数を考えます.

 

6桁の回文数は, 1桁の数  a, b, c\quad (a\neq0) を使って, "abccba" の形で書けるので, それが3桁の数の積になっているかを調べます.

 

 a, b, c の値を減らしていくループを使うことで, はじめに3桁の数の積で書けるものが最大になり, そこで計算を終了できます. なので, 1. の方法よりも計算時間は早くなります.

 

import itertools
Max = 0
for a, b, c in itertools.product(range(9, 0, -1), range(9, -1, -1), range(9, -1, -1)):
    n = a * 100001 + b * 10010 + c * 1100
    p = 100
    while p ** 2 <= n:
        if n % p == 0 and 100 <= n / p and n / p < 1000:
            Max = [n, p, n/p]
            break
        p += 1
    if Max != 0:
    break
print(str(Max[0]) + "=" + str(Max[1]) + "*" + str(Max[2]))