「プロジェクトオイラー問３８」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー問３８ - (2014/02/15 (土) 17:52:22) のソース

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の場合、*１*２,*３,*4,で２桁　３桁　３桁　３桁と計11桁で９桁が得られません。 
9xxも　　 *１,*２,*３で３桁４桁４桁　計１１桁です。　 
9ｘｘｘｘ*1、*２で１０桁を超えます。

よって残るのは9ｘｘｘの４桁となります。 
ここからはｎ桁目を9ｘｘｘの左からｎ桁目とします。

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

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

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

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

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

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