・大捜索                                GAI 氏

 ここに、ある20桁の自然数Nがある。「上k桁がkの倍数」(k=1〜20)を満たすものを探せ
るか?あらゆる手段(検索作業も含む)を講じても可。


 らすかるさんからのコメントです。(令和4年6月3日付け)

 20桁だと、条件を満たすものが44個もあります。桁数の最大は25桁で、値は、

  3608528850368400786036725

です。


 GAI さんからのコメントです。(令和4年6月3日付け)

 44個の中に、偶数の数だけのdigitsで構成されたものはありますか?


 らすかるさんからのコメントです。(令和4年6月3日付け)

 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個

 この数列は「A143671」にありましたが、こちらでは1桁の「0」も入れているようで、1桁が
10個になっています。


 GAI さんからのコメントです。(令和4年6月3日付け)

 もともとこの疑問に突き当たったのが、1〜9の数字を一個ずつ含む9桁の数があり、
「上k桁がkの倍数」(k=1〜20)を満たすものを探すと、381654729である、という記事でした。

 何とかこれをプログラムを使って探し出そうと試みて、苦心惨憺の末5分ほどの運用時間
で結果が手に入った。

 実行させる前に、9!の全順列を準備したり、上からk桁で切り取る作業をやらせたりと、
言ってみれば全検索を掛けた上での作業でした。

 これらについて更に調べてみると、別にプログラムに頼らずとも論理的に導けている記事
もありました。

 そして、そこに話題が広がり、例の偶数{0,2,4,6,8}だけを使った20桁の整数

  48000688208466084040

が紹介されていました。

 はて、9桁でもあれだけ候補がありながら、これが20桁ともなると、5^20=95367431640625
ととても全検索を掛けようにも時間がいくらあっても無理だ!

 そこで例の出題になったという経緯でした。

 それに対し、らすかるさんのこの結果です。これが如何に天文学的膨大な対象を処理され
ているか、想像しただけでも腰が抜けそうです。しかも半日もかからない時間で処理済みと
なっている。

 コンピュータさえあれば計算はあっという間に出来るだろうと思われるかも知れませんが、
そのオーダーが25桁などの桁になれば、とてもとても時間がかかります。

 以前コンピュータが高性能なのだろうと思っていたら、らすかるさんから、普通の使用のも
のを使っていますとの返事を頂いているので、これは正しくプログラム力の成せる技でしか
ありません。(しかし神業としか思えません。)

 もしかして、論理的に出せる数値なんですか?


 らすかるさんからのコメントです。(令和4年6月3日付け)

 論理的に出すのは候補が多すぎておそらく大変だと思います。上から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秒です。


 GAI さんからのコメントです。(令和4年6月4日付け)

 らすかるさんの「全桁数全通りで約0.13秒です。」のコメントを見て、改めてプログラムを見
直してみたら、全体から選ぶんじゃなく、その条件を満たす数を小さい順に構成していけば
いいんだ!という決定的にお門違いの攻め方をしていたことに気付きました。

 改めてプログラムを組んでみたら(3行程度)、まさに1秒もかからない時間で各桁の個数
と具体的整数をすべて計算してくれますね。

 25桁までは存在し、その後は構成できないとは初めて認識できました。



  以下、工事中!



              投稿一覧に戻る