Ｓ（Ｈ）さんからのコメントです。（平成２９年１月３０日付け）
６^123467＝1000993177..........197300736 です。
Seiichi Manyamaさんからのコメントです。（平成２９年１月３０日付け）
1000 できりが良かったので、出題しました。
ＧＡＩさんからのコメントです。（平成２９年１月３０日付け）
これから上４桁が1000となる ２^a、３^b、５^c、７^d のときの a、b、c、d を探すと？は興味
がでますね。これを数式で探すことができないものでしょうか。
らすかるさんからのコメントです。（平成２９年１月３０日付け）
数式で探すのは難しいと思いますが、簡単なアルゴリズムで探せます。
log[10]1.001=0.000434077… 、t=log[10]2=0.30102999… とすると、 3＜1/t＜4
t の自然数倍のうち4倍まででは小数部が最も大きいのが3t、最も小さいのが4t
3t+4t=7t の小数部は（ここまでで）最小(0.1072…)
最小が更新されたので最大が3t、最小が7t
3t+7t=10t の小数部は最小(0.0102…)
最小が更新されたので最大が3t、最小が10t
3t+10t=13t の小数部は最大(0.9133…)
最大が更新されたので最大が13t、最小が10t（以下このコメント省略）
（最大と最小を足すたびに最大か最小のどちらかが更新されます。）
13t+10t=23tの小数部は最大(0.9236…) 、23t+10t=33tの小数部は最大(0.9339…)
以下同様に処理
33t+10t=43t(0.9442…)、 43t+10t=53t(0.9545…)、 53t+10t=63t(0.9648…)、
63t+10t=73t(0.9751…)、 73t+10t=83t(0.9854…)、 83t+10t=93t(0.9957…)、
93t+10t=103t(0.0060…) ここで最小が更新される
93t+103t=196t(0.0018…)
93t+196t=289t(0.9976…)、 289t+196t=485t(0.9995…)、 485t+196t=681t(0.0014…)
485t+681t=1166t(0.0009…)、 485t+1166t=1651t(0.0005…)、 485t+1651t=2136t(0.00007…)
ここで初めて小数部がlog[10]1.001未満になりましたので、２^aの上位4桁が1000になる最小
のaは、2136です。
３^b も同様に考えると、
t=log[10]3=0.47712125… とすると、 2＜1/t＜3 なので、2t と 3t から始めます。
2t+3t=5t(0.3856…)、 2t+5t=7t(0.3398…)、 2t+7t=9t(0.2940…)、(中略)、
2t+19t=21t(0.0195…)、 2t+21t=23t(0.9737…)、 23t+21t=44t(0.9933…)、
44t+21t=65t(0.0128…)、 44t+65t=109t(0.0062…)、 44t+109t=153t(0.9995…)
153t+109t=262t(0.0057…)、 153t+262t=415t(0.0053…)、153t+415t=568t(0.0048…)、
(中略)、 153t+1792t=1945t(0.0008…)、 153t+1945t=2098t(0.0003…)
ここで初めて小数部がlog[10]1.001未満になりましたので、３^bの上位4桁が1000になる最
小のbは、2098です。
５^cは、
t=log[10]5=0.69897000… とすると、 1＜1/t＜2 なので、t と 2t から始めます。
が、log[10]5=1-log[10]2なので、log[10]2の途中経過が使えます。
log[10]2のときの289t(0.9976…)と681t(0.0014…)を使うことにすると、
log[10]5では681t(0.9985…)と289t(0.0023…)
681t+289t=970t(0.0009…)、 681t+970t=1651t(0.9994…)、 1651t+970t=2621t(0.0003…)
log[10]1.001未満になりましたので、５^cの上位4桁が1000になる最小のcは、2621です。
７^dは、
t=log[10]7=0.84509804…、 1＜1/t＜2
t+2t=3t(0.5352…)、 t+3t=4t(0.3803…)、 t+4t=5t(0.2254…)、 t+5t=6t(0.0705…)、
t+6t=7t(0.9156…)、 7t+6t=13t(0.9862…)、 13t+6t=19t(0.0568…)、 13t+19t=32t(0.0431…)、
13t+32t=45t(0.0294…)、 13t+45t=58t(0.0156…)、 13t+58t=71t(0.0019…)、
13t+71t=84t(0.9882…)、 84t+71t=155t(0.9901…)、 155t+71t=226t(0.9921…)、
226t+71t=297t(0.9941…)、 297t+71t=368t(0.9960…)、 368t+71t=439t(0.9980…)、
439t+71t=510t(0.0000004…)
よって、７^dの上位4桁が1000になる最小のdは、510です。
log[10](7^510)=431.0000004072…と整数に近いため、7^510=1.000000937776…×10^431
と上位7桁が1000000になっています。
Seiichi Manyamaさんからのコメントです。（平成２９年１月３０日付け）
皆さん、回答がはやいですね。解法はらすかるさんの方法がベストだと思いますので、後
はプログラミングだけの問題だと思われます。
DD++さんからのコメントです。（平成２９年１月３１日付け）
先日、log[10]2 を手計算で求める際に私が使った方法ですね。有効数字増やすと、2136
のときはギリギリ次の桁に届いていたんですね、なるほど。
ＧＡＩさんからのコメントです。（平成２９年１月３１日付け）
７^n の上４桁が「1234」になるときのｎを求めるアルゴリズムは、どの様になるのですか？
DD++さんからのコメントです。（平成２９年１月３１日付け）
とりあえず、手計算と電卓と有効数字15桁くらいの常用対数計算（wolfram先生による）の
力で、７^1401686 = 1.2340007498……*10^1184562 を見つけました。問題は、これが最小
かどうかですが、はたして。
Seiichi Manyamaさんからのコメントです。（平成２９年１月３１日付け）
Ｗｅｂサイト「A018866」の「1234」のところに「1401686」が載っていますので、最小と思われ
ます。ちなみに、 ７^1622006 = 12345… のようですね。
DD++さんからのコメントです。（平成２９年１月３１日付け）
OEIS は、こんなのまでカバーしているんですね。というわけで合っているようなので、使っ
たアルゴリズムを公開します。多分どんな場合でもちゃんと出るはず。
その前にまず、らすかるさんのアルゴリズムを若干修正しておきます。どこをスタートにす
べきかは、1/t の整数部分ではなく、正しくは Max[1/t,1/(1-t)] の整数部分で決まります。
７^d のとき、6t と 7t からスタートしているのは、6＜1/(1-t)＜7 だからですね。
（５^c のときは、3t と 4t から始めるのが正解。そして、これとは無関係ですが、後半にも誤
りがあって、c=2621 の最小保証ができていないような……）
それで、７^d で、「1234」から始まる初めての数を求める方法。コンピュータで計算するとし
て、log の近似値は必要な精度で手に入る前提とすると以下でいけます。
まず、先頭が1000……になる数を探す、らすかるさんのアルゴリズムをあらかじめ実行し、
途中に登場した数を全て保持しておきます。
log[10]1.234 = 0.0913152…… 、log[10]1.234 = 0.0916670……
なので、先に実行したアルゴリズムの計算途中に出てきた数を使って、小数部をこの間に
入れることを目指します。
t から 7t までで小数部が一番近いのは、6t (0.0705)
目標より小さいので、スタート2つの最小側である 6t を加算して、12t (0.1411)。
目標より大きいので、6t 以降で最大を更新した 13t を加算して、25t (0.1274)。
まだ目標より大きいので、さらに 13t を加算して、38t (0.1137)。
まだ目標より大きいので、さらに 13t を加算して、51t (0.1000)。
まだ目標より大きいので、さらに 13t を加算して、64t (0.0862)。
目標より小さいので、13t 以降で最小を更新した数を加算しますが、19t、32t、45t、58t、
71t と5連続の最小更新なので、以下のようにします。
(A) まず、目標を行き過ぎないように限界まで 19t を加えます。
（今回は1回で行き過ぎるのでスキップ）
(B) 次に、目標範囲に収まるものがあれば、その中で最も t の係数が小さいものを選び、
加えます。（今回はありません）
(C) 目標範囲に収まるものがない場合は、行き過ぎるもののなかで最も t の係数が大きい
ものを選び、加えます。（今回は 71t では届かないので 58t を加えます）
ということで、122t (0.1019)。
目標より大きいので、71t 以降で最大を更新した数を加えますが、ここも 84t から 439t ま
で6連続の最大更新なので、同様の方針を取ります。
84t は1回加えるだけで行き過ぎるので (A) はスキップ。しかし 155t では目標に届かない
ので、(C) では結局 84t を加えます。
ということで、 206t (0.09019)。
さて、次は 439t 以降で最小を更新した数を加えます。候補は、510t の1つだけなので、単
純にひたすら足します。
すると、(206+510*2747)t = 1401176t (0.0913150) までは届かず、
(206+510*2748)t = 1401686t (0.0913154) で目標範囲に入ります。
ということで、初めて先頭が「1234」となるのは、７^1401686 = 1.2340007498……*10^1184562
です。
「12345」についても、 log1.2345 = 0.0914911…… 、log1.2346 = 0.0915263…… を使うと、
同じ段階で、(206+510*3179)t = 1621496t (0.0914909) までは届かず、
(206+510*3180)t = 1622006t (0.0914913) で目標範囲に入ります。
らすかるさんからのコメントです。（平成２９年１月３１日付け）
どこをスタートにすべきかは、1/t の整数部分ではなく、正しくは Max[1/t,1/(1-t)] の整数
部分で決まります。
1/tの整数部分で問題なさそうな気がしますが、何か問題がありますか？
# 1/tとかしているのはtの値が小さいときに無駄な手順が多くなるのを防ぐためであって、基
本的には常にtと2tから始めても問題ないと思います・・・
そして、これとは無関係ですが後半にも誤りがあって c=2621 の最小保証ができていない
ような……
見直しても誤りの箇所が見つけられなかったのですが、どこに誤りがあるか教えて頂けま
せんか。
DD++さんからのコメントです。（平成２９年１月３１日付け）
そもそもなぜ t=log[10]2 に対して 1/t の整数部を考えるかといえば、小数部分を t ずつ
足していくと区間(0，1) で右へ右へと移動してから初めて逆サイドに移動するタイミングだか
らですよね。しかし、t=log[10]7 の場合は最初から点が左へ左へ 1-t ずつ移動していくので、
逆サイドに移動するタイミングは 1/(1-t) の整数部で計算しないといけないと思います。
（追記：あー、確かにおかしな結果に行き着くわけではないですね。「そういう目的で 1/t を
用いるなら、同様に t が 1 に近い場合も考慮して 1/(1-t) との大きい方で実行しな
いと片手落ちである」という主張にしておきます）
見直しても誤りの箇所が見つけられなかったのですが、どこに誤りがあるか教えて頂けま
せんか。
289t と 681t を流用していますが、２^aの計算では「289tが最大を更新」「485tが最大を更
新」「681tが最小を更新」の順に起こっているので、「最大が289tかつ最小が681t」という瞬間
は一度も発生していません。485tと681tのように、同時に最大最小であったペアで使わなけ
ればcの最小性は保証できないと思います。
実際、970*log[10]5 = 678.000904 が小数部の最小を更新したかのようになっていますが、
485*log[10]5 = 339.000452 なので小数部は最小になっていません。
らすかるさんからのコメントです。（平成２９年１月３１日付け）
元々tより小さい0に近い値を探すのが目的ですが、1/tを用いていれば最初に条件を満た
す値を取り逃すことはあり得ませんよね。しかし、1/(1-t)にしてしまうと、例えばt=0.97で目的
の範囲が「0.1以下」の場合に「最小の値」を取り逃してしまうと思います。
485tと681tのように、同時に最大最小であったペアで使わなければcの最小性は保証でき
ないと思います。
全くおっしゃる通りです。５^cの方だけ見ていたので誤りに気付きませんでした。
DD++さんからのコメントです。（平成２９年１月３１日付け）
そうか、1000……の形に特化したバージョンだとそういうことも起こるんですね、失礼しまし
た。私の中では最初から数字の並びを一般化した形で考えていたので、後半手順で一回逆
サイドに飛ぶまでの最良近似から再スタートする部分が存在する前提で考えてしまっていま
した。
ＧＡＩさんからのコメントです。（平成２９年２月１日付け）
候補は 510t の1つだけなので、単純にひたすら足します。
７^n=1234･･･ を満たすｎがなかなか探し出せなかったのは、たまたま
510*log[10]7=431.00000040727098･･･ と圧倒的に510倍の時に小数部分がとても小さい値
に収まっていたためなんですね。
手計算ではややこしい（最大、最小を入れ替え狭めていく）ので、とにかく小数部分を範囲
内に収めてしまえとばかりプログラム的にやってみたら
gp> F(p)={s1=log(1.23399)/log(10);s2=log(1.23401)/log(10);}\
for(n=1,10^7,t=frac(n*log(p)/log(10));if(s1<t && t<s2,print(n)))
gp> F(7) から
1397096 、1397606 、・・・ 、8770973 、8771483
gp> F(p)={s1=log(1.233999)/log(10);s2=log(1.234001)/log(10);}\
gp> F(7)から
1401176 、1401686 、・・・ 、6312334 、8767403
gp> F(p)={s1=log(1.2339999)/log(10);s2=log(1.2340001)/log(10）;}\
gp> F(7)から
3856755
の結果で出力され、正解の1401686を逃してしまいました。（２段目で一つ一つ点検すれば
見つけられるかも・・・）理論が如何に大切であるか、思い知らされます。
DD++さんからのコメントです。（平成２９年２月１日付け）
なぜ s1=log(1.23399) にしたのですかね？この場合 123399 から始まるのが混入しますし、
123402 とかから始まるのは弾かれてしまうと思います。
s1=log(1.234)/log(10)、s2=log(1.235)/log(10) でやってはダメだったのですか？
ＧＡＩさんからのコメントです。（平成２９年２月１日付け）
あ〜〜〜〜勘違いしていました。s1=log(1.234)/log(10)、s2=log(1.235)/log(10) で走らせた
ら数秒で（→ 出力結果） 1401686 、1402196 、・・・ 、1405766 、 ･･･ と、1401686をス
タートに510の等差数列でズラズラと並びました！このプログラムで任意のp^nの上位が探し
たい値になる最小のnを求めるものに利用できるのですね。
DD++さんからのコメントです。（平成２９年２月１日付け）
ほどほどの大きさのｎで見つかる場合は、ですけどね。最初に条件を満たすのが n≒10^20
くらいだったりすると単純な力任せでは難しいでしょう。
