1-Origin

この問題を解く上で重要な命題を紹介します．

• 正整数$x$を$2$倍して繰り上がりが発生したとき，繰り上がる桁は$1$桁だけでありその最高位は$1$である

まずこれを桁数に関する数学的帰納法で示します．

$1$桁の時，繰り上がりが起こるのは$5$から$9$のみであるので， 実際に計算すると$5 \times 2 = 10, 6 \times 2 = 12, 7 \times 2 = 14, 8 \times 2 = 16, 9 \times 2 = 18$より成立．

$n$桁の時に成立すると仮定する． $x$を${(n+1)}$桁の正整数とする． また，$d$を$x$の最高位の数字とする． $d$を用いると，$x=d \times 10^{n} + (x - d \times 10^{n})$と表すことができる．
よって$2\times x = 2d \times 10^{n} + 2\times (x - d \times 10^{n})$である．
$x$と$d$の定義の仕方により$x-d \times 10^{n}$は$n$桁の整数であるので， $2\times (x - d \times 10^{n}) < 2 \times 10^{n}$が成立． また，$1$桁の時の結果より，$2d \leq 18$であるので， $2d \times 10^{n} \leq 18\times 10^{n}$が成立．
これらの不等式を辺々足すと $2d\times 10^n + 2\times (x - d \times 10^n) = 2x < 20 \times 10^{n}=2 \times 10^{n+1}$を得る． よって成立．

この命題を用いると，「$a_0$から$a_X$のうち最高位が$1$であるものの個数」は 「$a_X$の桁数」と一致することが言えます．

よって，$a_X$の桁数を求めてそれを出力すればよいです． 桁数は$[ \log_{10}{2^X} ]+1 = [X \times \log_{10}{2}]+1$によって求めることができます($[a]$で$a$以下の最大の整数を表す)．