大捜索
ここにある20桁の自然数Nがある。
「上k桁がkの倍数」(k=1~20)
を満たすものを探せるか?
あらゆる手段(検索作業も含む)を講じても可
20桁だと条件を満たすものが44個もあります。
桁数の最大は25桁で、値は
3608528850368400786036725
です。
44個の中に偶数の数だけのdigitsで構成されたものはありますか?
1つだけありました。
48000688208466084040です。
ちなみに、桁数別の個数は以下のようになります。
1桁: 9個
2桁: 45個
3桁: 150個
4桁: 375個
5桁: 750個
6桁: 1200個
7桁: 1713個
8桁: 2227個
9桁: 2492個
10桁: 2492個
11桁: 2225個
12桁: 2041個
13桁: 1575個
14桁: 1132個
15桁: 770個
16桁: 571個
17桁: 335個
18桁: 180個
19桁: 90個
20桁: 44個
21桁: 18個
22桁: 12個
23桁: 6個
24桁: 3個
25桁: 1個
この数列は↓こちらにありましたが、
http://oeis.org/A143671
こちらでは1桁の「0」も入れているようで、1桁が10個になっています。
もともとこの疑問に突き当たったのが
1~9の数字を一個ずつ含む9桁の数があり
「上k桁がkの倍数」(k=1~9)
を満たすものを探すと381654729である。
という記事でした。
何とかこれをプログラムを使って探し出そうと試みて
苦心惨憺の末5分ほどの運用時間で結果が手に入った。
実行させる前に9!の全順列を準備したり、上からk桁で
切り取る作業をやらせたりと、言ってみれば全検索を
掛けた上での作業でした。
これらについて更に調べてみると、別にプログラムに頼らずとも
論理的に導けている記事もありました。
そしてそこに話題が広がり
例の偶数{0,2,4,6,8}だけを使った20桁の整数(48000688208466084040)
が紹介されていました。
はて9桁でもあんだけ候補がありながら、これが20桁ともなると
5^20 = 95367431640625
ととても全検索を掛けようにも時間がいくらあっても無理だ!
そこで例の出題になったという経緯でした。
それに対し、らすかるさんのこの結果です。
これが如何に天文学的膨大な対象を処理されているか、想像しただけでも
腰が抜けそうです。
しかも半日もかからない時間で処理済みとなっている。
コンピュータさえあれば計算はあっという間に出来るだろうと思われるかも
知れませんが、そのオーダーが25桁などの桁になれば、とてもとても時間が
かかります。
以前コンピュータが高性能なのだろうと思っていたら、らすかるさんから
普通の使用のものを使っていますとの返事を頂いているので、これは正しく
プログラム力の成せる技でしかありません。(しかし神業としか思えません。)
もしかして、論理的に出せる数値なんですか?
論理的に出すのは候補が多すぎておそらく大変だと思います。
上から1桁ずつ増やして条件に当てはまるものだけその下の桁を
処理するようにすれば、時間は大してかかりません。
1桁目は1~9の9通り
2桁目は1桁目の9通りに対して各5通りなので2桁目までで45通り
3桁目はその45通りに対して3の倍数になるものなので150通り
(最初の2桁で合計が3の倍数である
12,18,24,30,36,42,48,54,60,66,72,78,84,90,96
の15個は3桁目が0,3,6,9の4通り、残りの30個は3通りずつなので
15×4+30×3=150通り)
4桁目は3桁目が偶数なら0,4,8の3通り、奇数なら2,6の2通り→375通り
5桁目は0か5なので4桁までの2倍の750通り
・・・
ちなみに私が作ったプログラムの実行時間は
全桁数全通りで約0.13秒です。
らすかるさんの全桁数全通りで約0.13秒です。
のコメントを見て、改めてプログラムを見直してみたら
全体から選ぶんじゃなく、その条件を満たす数を小さい順に構成していけばいいんだ!
という決定的にお門違いの攻め方をしていたことに気付きました。
改めてプログラムを組んでみたら(3行程度)まさに1秒もかからない時間で
各桁の個数と具体的整数をすべて計算してくれますね。
25桁までは存在し、その後は構成できないとは初めて認識できました。