「プロジェクトオイラー解説問38」の編集履歴(バックアップ)一覧に戻る

プロジェクトオイラー解説問38 - (2014/02/15 (土) 01:35:00) のソース

*Problem 38 「パンデジタル倍数」 †
192 に 1, 2, 3 を掛けてみよう.

192 × 1 = 192
192 × 2 = 384
192 × 3 = 576

積を連結することで1から9の パンデジタル数 192384576 が得られる. 192384576 を 192 と (1,2,3) の連結積と呼ぶ.

同じようにして, 9 を 1,2,3,4,5 と掛け連結することでパンデジタル数 918273645 が得られる. これは 9 と (1,2,3,4,5) との連結積である.

整数と (1,2,...,n) (n > 1) との連結積として得られる9桁のパンデジタル数の中で最大のものはいくつか?


解法
まずは1を書けるのですから求める先頭数字は9であることを期待します。
xを何らかの一文字の数字とすると

9xの場合、*1*2,*3,*4,で2桁 3桁 3桁 3桁と計11桁で9桁が得られません。
9xxも   *1,*2,*3で3桁4桁4桁 計11桁です。 
9xxxx*1、*2で10桁を超えます。

よって残るのは9xxxの4桁となります。
ここからはn桁目を9xxxの左からn桁目とします。

まず9xxx*1と9xxx*2の結合を考えると
9xxx18xxx
となります。

すると2桁目は繰り上がると18が19になるので5,6,7,8,9は入りませんし0は0*1=0でパンデジタル数の条件に反します。

2桁目は2か3か4しか入りませんが4は2倍すると8で8とかぶり3桁目からの桁上りがあると9になりこれもダメ。

よって2桁目は2か3となります。
3桁目と4桁目は2,3,6,7しか入りません。
ここから大きな数から検討します。

2桁目が3だとします。
3桁目が7だと繰り上がって2桁目は3*2+1=7で7が重複するので駄目です。
3桁目が6だと4桁目は5を作るために7となります。
9367 18734
で7が重複します。

3桁目が2だと。
5を作るために4桁目を7にしないといけません。
よって答えは
9327と18654
932718654となります。
9より小さい数を1桁目に持ってくると必ず932718645より小さくなるのでこれですべての場合を検討したことになります。