Given that $n$ is a natural number such that the leftmost digits in the decimal representations of $2^n$ and $3^n$ are the same, find all possible values of the leftmost digit.
Problem
Source: India IMO Training Camp 2016, Practice Test 1 Problem 2
Tags: number theory
23.07.2016 09:23
23.07.2016 09:37
Actually this was a misprint and was meant to be the powers of 2 & 5. Anyways we found after the test using computations with logarithms that every digit can be possible. The main idea behind this was Kronecker's theorem and it provided the motivation for the log computations.
23.07.2016 10:16
Any non bash approach to the problem? Nobody at the camp could provide a non computational solution as far as i know
03.12.2016 08:50
Did u mean a non-bash solution for 2^n, 5^n problem? [ I don't think so, because that's very easy one.. ]
03.12.2016 18:45
Since no solutions have been posted yet, here is the brute force solution just for the sake of completeness of this thread. The answer is that, as I mentioned before, $n$ can be anything in the set $\{1,2,3,\cdots ,9\}$. One of the ways to prove this is to give an example for every possible leftmost digit, which is not easy to do manually. So we take resort to Python. for i in range(1,10): n=1 while True: if str(2**n)[0]==str(3**n)[0]==str(i): print('The leftmost digit is ',i,' for n =',n,', in which case 2^n =',2**n,' and 3^n =',3**n,'.') break n=n+1for i in range(1,10): n=1 while True: if str(2**n)[0]==str(3**n)[0]==str(i): print('The leftmost digit is ',i,' for n =',n,', in which case 2^n =',2**n,' and 3^n =',3**n,'.') break n=n+1RunResetPop Out / Upon hitting the Run button, it faithfully returns the following output: Output wrote: The leftmost digit is 1 for n = 17 , in which case 2^n = 131072 and 3^n = 129140163 . The leftmost digit is 2 for n = 28 , in which case 2^n = 268435456 and 3^n = 22876792454961 . The leftmost digit is 3 for n = 85 , in which case 2^n = 38685626227668133590597632 and 3^n = 35917545547686059365808220080151141317043 . The leftmost digit is 4 for n = 125 , in which case 2^n = 42535295865117307932921825928971026432 and 3^n = 436673502879206784130402698570834024654748577491697818855443 . The leftmost digit is 5 for n = 142 , in which case 2^n = 5575186299632655785383929568162090376495104 and 3^n = 56392087339601733413306017749077372989860250021295987473736382457209 . The leftmost digit is 6 for n = 182 , in which case 2^n = 6129982163463555433433388108601236734474956488734408704 and 3^n = 685596132412797531053607549485540055753823212621556770516014091704614236087297342176409 . The leftmost digit is 7 for n = 159 , in which case 2^n = 730750818665451459101842416358141509827966271488 and 3^n = 7282483350946404208076885500996745047522350034970917293604274649554310785067 . The leftmost digit is 8 for n = 199 , in which case 2^n = 803469022129495137770981046170581301261101496891396417650688 and 3^n = 88537996291958256446260440678593208943077817551131498658191653913030830300434060998128233014667 . The leftmost digit is 9 for n = 176 , in which case 2^n = 95780971304118053647396689196894323976171195136475136 and 3^n = 940461086986004843694934910131056317906479029659199959555574885740211572136210345921 . So we are done. $\blacksquare$
05.12.2016 12:28
Ankoganit wrote: Since no solutions have been posted yet, here is the brute force solution just for the sake of completeness of this thread. The answer is that, as I mentioned before, $n$ can be anything in the set $\{1,2,3,\cdots ,9\}$. One of the ways to prove this is to give an example for every possible leftmost digit, which is not easy to do manually. So we take resort to Python. for i in range(1,10): n=1 while True: if str(2**n)[0]==str(3**n)[0]==str(i): print('The leftmost digit is ',i,' for n =',n,', in which case 2^n =',2**n,' and 3^n =',3**n,'.') break n=n+1for i in range(1,10): n=1 while True: if str(2**n)[0]==str(3**n)[0]==str(i): print('The leftmost digit is ',i,' for n =',n,', in which case 2^n =',2**n,' and 3^n =',3**n,'.') break n=n+1RunResetPop Out / Upon hitting the Run button, it faithfully returns the following output: Output wrote: The leftmost digit is 1 for n = 17 , in which case 2^n = 131072 and 3^n = 129140163 . The leftmost digit is 2 for n = 28 , in which case 2^n = 268435456 and 3^n = 22876792454961 . The leftmost digit is 3 for n = 85 , in which case 2^n = 38685626227668133590597632 and 3^n = 35917545547686059365808220080151141317043 . The leftmost digit is 4 for n = 125 , in which case 2^n = 42535295865117307932921825928971026432 and 3^n = 436673502879206784130402698570834024654748577491697818855443 . The leftmost digit is 5 for n = 142 , in which case 2^n = 5575186299632655785383929568162090376495104 and 3^n = 56392087339601733413306017749077372989860250021295987473736382457209 . The leftmost digit is 6 for n = 182 , in which case 2^n = 6129982163463555433433388108601236734474956488734408704 and 3^n = 685596132412797531053607549485540055753823212621556770516014091704614236087297342176409 . The leftmost digit is 7 for n = 159 , in which case 2^n = 730750818665451459101842416358141509827966271488 and 3^n = 7282483350946404208076885500996745047522350034970917293604274649554310785067 . The leftmost digit is 8 for n = 199 , in which case 2^n = 803469022129495137770981046170581301261101496891396417650688 and 3^n = 88537996291958256446260440678593208943077817551131498658191653913030830300434060998128233014667 . The leftmost digit is 9 for n = 176 , in which case 2^n = 95780971304118053647396689196894323976171195136475136 and 3^n = 940461086986004843694934910131056317906479029659199959555574885740211572136210345921 . So we are done. $\blacksquare$ Nice, but we did not have Python to our advantage in the actual TST lol.
05.12.2016 13:40
Ankoganit wrote: Given that $n$ is a natural number such that the leftmost digits in the decimal representations of $2^n$ and $3^n$ are the same, find all possible values of the leftmost digit. One can do this by considering jump powers in 10 bases , in $2^n$ and $3^n$.
05.12.2016 17:34
WizardMath wrote: Nice, but ... I hope that 'Nice' is meant to be sarcastic, since I'm in no way satisfied with the above solution (if it can be called so). kk108 wrote: One can do this by considering jump powers in 10 bases , in $2^n$ and $3^n$. We look forward to seeing your proof.
05.12.2016 18:28
Well I am not an IMOTcer but anyway I think I will post my proof , if I have one tommorow or so ....
05.12.2016 20:42
So here is a solution to a slightly different problem with 2 and 5 and the 2 leftmost digits. Suppose $ 2^n $ and $ 5^n $ start with the same 2 digits.Denote that 2-digit number by $ a $. This implies the existence of natural numbers $ k $ and $ h $ such that we have: $$ 10^ka < 2^n < 10^k(a+1) $$ $$ 10^ha < 5^n < 10^h(a+1) $$ Now multiplying these we get: $$ 10^{k+h}a^2 < 10^n < 10^{k+h}(a+1)^2 $$ or equivalently $ a^2 < 10^{n-k-h} < (a+1)^2 $ but we know $ 10 \leq a \leq 99 = 10^2 $ and using these two relations we get $ n = k + h + 3$ and plugging this back in the above double inequality we get $ a^2 < 1000 < (a+1)^2 $ or $ a < 31.62... < a+1 $ hence a = 31 and we are done
05.12.2016 22:30
I was in a hurry and couldnt type it then.. but notice that this method works for the problem at hand with 2 and 5 and we get the first digit 3!
06.12.2016 05:18
Ankoganit wrote: WizardMath wrote: Nice, but ... I hope that 'Nice' is meant to be sarcastic, since I'm in no way satisfied with the above solution (if it can be called so). kk108 wrote: One can do this by considering jump powers in 10 bases , in $2^n$ and $3^n$. We look forward to seeing your proof. Ofc it was sarcastic. As a motivation for the solution as I already said earlier, we can use Kronecker's theorem, as $\log 2 $ and $\log 3$ are linearly independent over $\mathbb{R}$. kk108 wrote: Well I am not an IMOTcer but anyway I think I will post my proof , if I have one tommorow or so .... Someone at IMOTC also solved this using your idea, but it was quite unrigorous and had quite a few gaps. Hope your solution doesn't have them. Best of luck.
10.03.2017 13:13
Any ideas?
14.09.2017 21:31
@nbasri, what do you mean by 10<= a<=99=10^2? . . <= is less than equal to
14.09.2017 21:56
This was (rumoured to be) a German exercise, it also appeared now in KöMaL (hungarian journal), but instead of $2^n$, they wrote $4^n$. Here is the proof: https://www.komal.hu/verseny/feladat.cgi?a=feladat&f=B4859&l=en
15.09.2017 05:07
The fact that $\log_{10} 2$ and $\log_{10} 5$ are linearly dependent holds the key to the problem. But the same doesn't hold for 5 replaced by 3 so the problem becomes bad then.
12.01.2019 07:48
Where can I study all of these theorems like Kronecker's theorem and all?