FC2ブログ

Welcome to my blog

[485] 2の累乗の最高位の数字

ヤドカリ

ヤドカリ


'


[485] 2の累乗の最高位の数字


 2196>1059,2485<10146 です。

 n=1,2,3,……,5000 として、2n を十進法で表したとき最高位(先頭)の数字が1となるものの個数は?

 また、最高位の数字が4となるものの個数は?


★ 解答説明は こちら です。

スポンサーサイト



Comments 20

There are no comments yet.
ヤドカリ  
No title

> スモークマン様
鍵コメの解答、正解です
解答を有難う御座います。♪

uch*n*an  
No title

>ご指摘の件ですが、log2に近い値として、
>小さい方は、59/196,205/681,351/1166,497/1651,643/2136,……
>大きい方は、87/289,146/485,789/2621,1432/4757,……
この近似分数列の求め方に興味があります。宜しかったら教えてもらえませんか?

たけちゃん  
No title

横から失礼します.

ヤドカリさんの分数列を見ると,
例えば次のようなプログラムの(途中からの)出力と一致します.

LET k=LOG10(2)
LET a=0
LET b=1
PRINT "小さい方"
FOR i=1 TO 5000
LET x=INT(k*i)
IF x*b>a*i THEN
LET a=x
LET b=i
PRINT a;"/";b
END IF
NEXT I
PRINT "大きい方"
LET a=1
LET b=1
FOR i=1 TO 5000
LET x=INT(k*i)+1
IF x*b<a*i THEN
LET a=x
LET b=i
PRINT a;"/";b
END IF
NEXT I
END

私は,log10(2) の連分数展開を元に近似分数を求めました.

ヤドカリ  
No title

uch*n*anさん、改善された解答を有難う御座います。
近似分数の件ですが、UBASIC でプログラムを組んで求めました。
100 A=1
110 M=9.9
120 N=1.01
130 for I=1 to 8000
140 A=A*2
150 B=A/10^(alen(A)-1)
160 if B<M then 190
170 M=B
180 print B;alen(A);"/";I;"=";alen(A)/I
190 if B>N then 220
200 N=B
210 print B;alen(A)-1;"/";I;"=";(alen(A)-1)/I
220 next
230 end
なお、alen( ) は十進法での桁数です。

ヤドカリ  
No title

たけちゃんさん、コメントを有難う御座います。
私は LOG10(2) の値を使わずに、単純に2の累乗と 10の累乗を比べて求めました。
言語が違いますが、大体分かって頂けると思います。

ヤドカリ  
No title

> sbr*d4*5様
鍵コメの解答、正解です
解答を有難う御座います。
表にすれば変化が良く分かりますね。

uch*n*an  
No title

そうですか,プログラムですか。ちょっと残念。
b/a < (b + d)/(a + c) < d/c を使ったのかな,と思ったのですが,
実際の log_10(2) の値との大小比較ができないと,うまく近似を絞り込めそうにないので,
何か面白い評価法があるのかな,と思ったのですが。

uch*n*an  
No title

>私は,log10(2) の連分数展開を元に近似分数を求めました.
連分数展開はどうやって求めたのでしょうか?
log10(2) の値を使ったのでしょうか?
それだと,確かに求まりますが,あまり面白くはないですよね...

ヤドカリ  
No title

uch*n*anさん、コメントを有難う御座います。
底が10だとテーラー展開も綺麗な式になりません。
複雑なことをするより、残念かも知れませんが、
単純に2の累乗と 10の累乗で近い値のものを見つけるのが早いと思います。

たけちゃん  
No title

連分数展開も(残念ながら)計算機でやりました.
面白いかと言われると,ちょっと困りますが...

log10(2)やlog(2)/log(10)を使う手もありましたが,
実際は,次のプログラムでやってます.

LET a=10
LET b=2
FOR i=1 TO 10
LET n=0
DO WHILE a>b
LET a=a/b
LET n=n+1
loop
PRINT n
LET w=a
LET a=b
LET b=w
NEXT I
END

連分数展開は,近似分数を求めるには大変強力だと感じています.

uch*n*an  
No title

たけちゃんさんへ
なるほど。
これは log を直接に使っておらず,頑張れば筆算でもある程度はできそうな気がするので,
プログラムであっても面白いです。
そもそも,近似値を求めるのに,真の値を使うのは本末転倒な気もしますしね。
ご教示,ありがとうございます。

uch*n*an  
No title

>頑張れば筆算でもある程度はできそうな気がするので,
これは,ちと厳しいようでした。普通の電卓を片手に,ならば何とかなりそう (^^;

ヤドカリ  
No title

たけちゃんさん、プログラムを有難う御座います。
小心者の私には、このプログラムは思いつきません。
「 LET a=a/b 」の行が、
どれぐらいの精度で計算しているのか分からないからです。
真似て UBASIC で下記のプログラムで分数計算(A=A//B の部分)しましたら、
3,3,9,2,2,4 を出力したあとオーバーフローしてしまいました。

100 A=10:B=2
110 for I=1 to 10
120 N=0
130 while A>B
140 A=A//B:N=N+1
150 wend
160 print N
170 swap A,B
180 next
190 end

なお、UBASIC は1変数で、十進法にして 2600桁扱える優れモノです。

ヤドカリ  
No title

uch*n*anさん、コメントを有難う御座います。
割り算の部分の計算が大変ですね。

uch*n*an  
No title

所詮,言語仕様や処理系の問題なので議論してもしょうがないですが,
たけちゃんさんのコード,十進ベーシック,で,
分数計算が可能な有理数モードでは問題なく動くようです。

たけちゃん  
No title

ヤドカリさん,計算精度についてのご指摘ありがとうございます.

uch*n*anさんのおっしゃるように,十進ベーシックの有理数モードは,
桁数制限がないので,それでやれば安心です.
ただ,実験としてループの回数を増やすと,
3, 3, 9, 2, 2, 4, 6, 2, 1, 1, 3, 1
の次の値の出力(10進100桁モードの出力から,多分18)
で,時間がかかりすぎて,止まったように見えました.

UBASIC でも,「有理数演算は魔物です」との
作者のコメントが確かどこかにあったような覚えがあります.
(UBASIC は,以前はよく使っていました)

「有理数」といった安全な世界では計算量が増え,
そうでない世界では誤差評価が難しい...悩ましいところですね.

余談ながら,正式名称が「(仮称)十進BASIC」ということでいいのですかね.

ヤドカリ  
No title

uch*n*anさん、コメントを有難う御座います。
十進ベーシックがどれだけの能力を持っているのか知りませんでしたので、
昨日のようなコメントになりました。
桁数制限がないのですね。非常に有力なツールだということを知りました。
時間を見つけて勉強する必要がありそうです。

ヤドカリ  
No title

たけちゃんさん、コメントを有難う御座います。
貴殿のコメントで「(仮称)十進BASIC」が非常に優れていることがわかりました。

> 「有理数」といった安全な世界では計算量が増え,
> そうでない世界では誤差評価が難しい...悩ましいところですね.
私もそう思います。
UBASIC でオーバーフローして止まった所で、AやBの値を見たら、
分子分母の境目を見つけるのに苦労するほどの分数になりました。

桁数制限がないのであれば、2の累乗と10の累乗の近い値を直接比べても、
かなりな近似分数が算出できると思いますが、
同じ近似分数を得るのにどちらが速いかも興味のある所です。
「(仮称)十進BASIC」を私がマスターしてからの話ですが……。

uch*n*an  
No title

残念ながら,スピードは,一般に,「(仮称)十進BASIC」の方が遅いと思います。
また,整数だけの計算では,いろいろと制限が付くことも多く,
組み込み関数も UBASIC の方が強力だと思います。
一方,言語仕様や処理系の使い勝手は「(仮称)十進BASIC」の方がいいと思います。
まぁ,同じ BASIC 系の言語なのですぐに覚えられますから,
両方を覚えておいて使い分けるのがベストのような気がします。

ヤドカリ  
No title

uch*n*anさん、コメントを有難う御座います。
UBASIC は MS-DOS 上で動くように設計されていますので、
今となっては使い勝手が悪いですね。
「(仮称)十進BASIC」はもっと進化してスピードも上がることでしょう。
組み込み関数がどれ位使えるのかわからず、
「(仮称)十進BASIC」を使う気持ちになりませんでしたが、
これからは覚える必要がありそうです。