PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 145 / reversibleな数

n + reverse(n) の各桁が奇数のみであるような n が存在する。たとえば 36 + 63 = 99, 409 + 904 = 1313 である。この性質を持つ数を reversible と呼ぶことにする。36, 63, 409, 904は revesible である。先頭の0は n でも reverse(n) でも許されない。

1000未満には120個の reversible な数が存在する。

10億(10^9)未満にはいくつの reversible な数が存在するか?

Problem 145 - Project Euler


まずは brute にやってみました。奇数判定は「各桁の数字の積が奇数かどうか」で行います。

10^5未満まではこの方法で瞬時に答えが出ますが,10^9は遠いです。もう少し数学的につめてから計算させます。

「n の首位の数字と一の位の数字は偶奇が異なる」は明らかですが,途中の繰り上がりはどうなっているのでしょうか。reversible な数の実例を見てみましょう。3桁の場合,「十の位は0〜4」「一の位で繰り上がりがおきる」などが見てとれます。


以下,n + reverse(n)= S とおきます。

1桁のとき

S=a+a=2a のように必ず偶数になるので0個。

2桁のとき

ab+ba の形。1の位に注目すると

b+a=(1桁の奇数)または10+(1桁の奇数)

ここで繰り上がると十の位の足し算が a+b+1 になって,Sの十の位が偶数になります。よってa, bはどちらも0ではなく,和が1桁の奇数です。

(1,2),(1,4),(1,6),(1,8),(2,3),(2,5),(2,7),(3,4),(3,6),(4,5)

これらの反転もあるので10*2=20個。

3桁のとき

abc+cba の形。十の位の足し算が b+b だと Sの十の位が偶数になるので c+a は繰り上がります。c+a=11, 13, 15, 17の各場合を書き出すと20通りあります。

Sの十の位の足し算は b+b+1 です。ここで繰り上がると S の百の位が偶数になるので b は0以上4以下の数です。

以上より 3桁の数は 20*5=100個。

4桁のとき

abcd+dcbaの形。

  • a+d=(1桁の奇数。0は不可) → 20個
  • b+c=(1桁の奇数。0も可) → 30個

合計 20*30=600個。

5桁のとき

abcde+edcbaの形。百の位のc+cに注目すると,十の位のd+bは繰り上がります。詳細は省略しますが,このとき Sの一の位と一万の位が両方奇数になることはありません。よって0個。

6桁のとき

abcdef+fedbca。4桁のときとほぼ同じです。

  • a+f=(1桁の奇数。0は不可) → 20個
  • b+e=(1桁の奇数。0も可) → 30個
  • c+d=(1桁の奇数。0も可) → 30個

合計 20*30*30=18,000個。

7桁のとき

abcdefg+gfedcbaの形。千の位の d+d に注目すると e+cは繰り上がります。

  • a+g=(1桁の奇数。0は不可) → 20個
  • b+f=(1桁の偶数。0も可) → 25個
  • c+e=(2桁の奇数。0も可) → 20個
  • d=(0〜4のどれか) → 5個

全部かけて計50,000個。

8桁のとき

6桁のときと同様です。
20*30^3=540,000個。

一般に桁数が2kのときは 20*30^(k-1) 個になります。

9桁のとき

abcdefghi+ihgfedcbaの形。一万の位の e+e に注目して偶奇と繰り上がりを調べていくと,5桁のときと同様に0個だとわかります。

以上の和をとって608720個。

手計算で解けてしまいましたが,一応 Mathematica でも計算しておきます。Piecewise を使って桁数が「偶数」「4で割って余り1」「4で割って余り3」のときの式を作って足しあわせます。