3
$\begingroup$

Given a finite sequence of decimal digits $a_1,a_2,...,a_n$ prove that there exists a natural number $m$ such that decimal representation of $2^m$ starts with that sequence of digits.

Thanks for your help :)

$\endgroup$
  • 1
    $\begingroup$ .. with $a_1\ne 0$? $\endgroup$ – Hagen von Eitzen May 10 '14 at 13:36
  • 1
    $\begingroup$ Do you know any relevant property of the rotations of the circle $S^1$? $\endgroup$ – Did May 10 '14 at 13:39
  • $\begingroup$ @Did Thanks! Actually I prefer to solve this question using rotations of $S^1$, Could you give me a little more explanation ? Oh ! Do you mean rotations of the circle $[0,1]/0\~1$ by the map $R_{log2}$ which sends $x \in S^1$ to $x+log2 (mod 1)$ has dense orbits in the circle... $\endgroup$ – the8thone May 10 '14 at 14:33
  • $\begingroup$ there is another answer here $\endgroup$ – user354674 Sep 8 '16 at 14:24
6
$\begingroup$

Hint: $\log 2$ is irrational. What can you say about $ \{ n log 2 \}$, the fractional parts?

$\endgroup$
  • $\begingroup$ the fractional parts of the sequence $\{m \log 2\}^{\infty}_{m=1}$ is $\{ \log 2,\log 4,\log 8,\log 1.6, \log 3.2 , \ldots \}$ which is a sequence of irrational numbers in $[0,1]$. If we know that this sequence is dense in $[0,1]$ we are done , but do we know that ?! $\endgroup$ – the8thone May 10 '14 at 14:26
  • $\begingroup$ @the8thone Great. Your guess is true, now show it. Use the pigeonhole principle. $\endgroup$ – Calvin Lin May 10 '14 at 15:01
  • $\begingroup$ I don't understand why are we done if the sequence $\{m \log 2\}$ is dense. Can you explain me, please? Thank you very much! $\endgroup$ – g.pomegranate Nov 19 '17 at 18:49
  • $\begingroup$ @g.pomegranate More generally, for irrational $r$, $\{ m r \} $ is dense. For example, by the pigeonhole principle applied to the first 101 values (pigeons) and 100 intervals $[\frac{n}{100}, \frac{n+1}{100} ]$ (hole), we can find 2 values of $mr$ which lie in the same interval. Their positive difference is a value of the form $m'r$, and lies within $[0, 0.01]$. So, we have a value in every 0.01 interval. Extend to $ 100 \rightarrow \infty$. $\endgroup$ – Calvin Lin Nov 27 '17 at 16:09
  • $\begingroup$ @CalvinLin Thank you very much! $\endgroup$ – g.pomegranate Nov 28 '17 at 18:44
1
$\begingroup$

It is not a proof, just a try to find by approximations the first solutions, without the guarantee that they exist.

I tried a small script to select candidates which were submited next to a large digital computer for example manually.

The principle is the decimal approximation. The algorithm keeps only the 11 digits of a number hoping that the truncature will not affect a lot the most left digits. To extend the search , it selects also a few approximative matches, always under the target, since the truncature makes the result smaller.

There is an example of implementation for the target 999 , easy to adapt to other ones:

function main()
{
    var i, k = 68719476736,res="",res2="" ; /// begin with 2^36
    for( i=37 ; i < 50000 ; i++ )
    {
        k = 2* ((""+k).substr(0,7)) ;

        var kk = (""+k).substr(0,3) ;
        if( kk=="999" ) // if( kk=="998" || kk=="999" )
        {
            res +=( k+" ("+i+"), " ) ;
            res2 +=( "2^"+i+"," ) ;
        }
    }

    return res+"\n"+res2+"\n" ;
}


// scratchpad formalism to output the result as the last seen variable
// type CTRL L to run
var tto , ttt = main() ;
tto = ttt ;

Truncated numbers selected with the power in parenthesis :

$99912223808 (2621), 99928497088 (4757), 99944773024 (6893), $ $99961051568 (9029), 99977332768 (11165), 99993616640 (13301), $ $99905846016 (15922), $ $99922118264 (18058), 99938393032 (20194), 99954670632 (22330), $ $99970950824 (24466), 99987233664 (26602), $ $99915739784 (31359), 99932013584 (33495), 99948290144 (35631), $ $99964569264 (37767), 99980851144 (39903), $ $99997135584 (42039), 99909361920 (44660), 99925634840 (46796), $ $99941910296 (48932); ...$

After external tests, $2^{2621}$, $2^{4757}$, $2^{6893}$ , $2^{9029}$ , $2^{11165}$ seem to work well with the target of the test $999$.

edit : keeping 11 significative digits and testing only the target, I get directly the same begining of the sequence solution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.