MENU
158,774

スレッドNo.83

大捜索

ここにある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個になっています。

引用して返信編集・削除(編集済: 2022年06月03日 16:00)

もともとこの疑問に突き当たったのが
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桁までは存在し、その後は構成できないとは初めて認識できました。

引用して返信編集・削除(未編集)

このスレッドに返信

このスレッドへの返信は締め切られています。

ロケットBBS

Page Top