13
$\begingroup$

This math problem was posted on The Nineteenth Byte over at Programming Puzzles and Code Golf.

It states this: Prove that for all integers $n > 0, 2^n$ will contain a digit other than $1$ and $0$ in base $5$.

TNB came up with these conditions for a counterexample:

$2^n \text{ mod } 5 = 1$ ; $2^n \text{ mod } 10 = 6$ ; and $n \text{ mod } 4 = 0$

$\endgroup$
18
  • 3
    $\begingroup$ If we express a number in base 5 using only ones and zeros, the resulting value will be a number that must be either divisible by 5 (if the last digit is 0), or is one greater than a number that is divisible by 5 (if the last digit is 1) $\endgroup$ Jul 7, 2017 at 0:57
  • 2
    $\begingroup$ @AndrewGray Not in base $5$. For example, $2^{20}=232023301_5$ which ends in $01$. $\endgroup$
    – lulu
    Jul 7, 2017 at 1:01
  • 1
    $\begingroup$ Also note that the power will be a power of 16; that is, $n\equiv 0\text{ (mod 4)}$ $\endgroup$ Jul 7, 2017 at 1:07
  • 1
    $\begingroup$ Worse: you can always get the power to begin with $10^k$ (or any other pattern of 1s and 0s) because of the irrationality of $\log_5(2)$. So you can't get a proof just by constraining either the starting or the ending digits. $\endgroup$ Jul 7, 2017 at 1:16
  • 3
    $\begingroup$ So far as I know, incidentally, this problem is open for all combinations of bases except for trivial cases. $\endgroup$ Jul 7, 2017 at 1:19

1 Answer 1

2
$\begingroup$

We assume it can be written as $N=5^{a_i} + 5^{a_{i-1}} +・・・+ 5^{a_1} + 1$

Since this equal to $2^n$. Let $n=4m$,

$2^{n}-1$ $=16^{m}-1$ $=(3*5+1)^m-1 $ $=(3*5)^m+・・・+m(m-1)/2*(3*5)^2+5*3m$

It must be $3m=5^{b_1}=1$, or $5^{b_1}+1$. $9m(m-1)/2$ must be $5^{b_2},5^{b_2}+1$. So possible case are two.

$(i)$ $5^{b_1}*3(m-1)/2=5^{b_2}+1$

this leads $-5^{b_2-b_1}=2,b_1=0$. This is false.

$(ii)$ $9m(m-1)/2=5^{b_2}+1$

$⇔(5^{b_1}+1)*(5^{b_1}-2)=2(5^{b_2}+1)$

$-2 \not \equiv2 \mod 5 $ This is a contradiction.

Therefore it was proved there are no $2^n$ of base 5 which is made of only $0$ and $1$.

$\endgroup$
6
  • $\begingroup$ @EpsilonNeighborhoodWatch The question is asking about powers of 2, where the number must be able to be written as $2^n$ $\endgroup$ Jul 8, 2017 at 1:12
  • 2
    $\begingroup$ Why must $3m=5^{b_1}=1$? $\endgroup$
    – Joel
    Jul 8, 2017 at 1:37
  • $\begingroup$ @EpsilonNeighborhoodWatch Yeah I think you're right, my bad! $\endgroup$ Jul 8, 2017 at 2:51
  • $\begingroup$ This argument seems to be making the assumption that an individual term binomial expansion has to match an individual term in the sum of powers of $5$ (with a allowance for the extra $1$). This is fundamentally unsound. $\endgroup$
    – Erick Wong
    Aug 8, 2017 at 17:29
  • $\begingroup$ I think it is most natural assumption, though. By the way, did you read comments in question? $\endgroup$ Aug 8, 2017 at 19:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .