0
$\begingroup$

Let $p$ be a prime and $b \geq 2$ be an integer.

(a) Is there a power of $p$ that contains $\underbrace{00\ldots0}_{\text{$2017$}}$ in its base-$b$ representation ?

(b) Is there a power of $p$ that contains $\underbrace{11\ldots1}_{\text{$2017$}}$ in its base-$b$ representation ?

(c) Is there Fibonacci number that contains $\underbrace{11\ldots1}_{\text{$2017$}}$ in its base-$b$ representation ?


Thank you, Robert Israel.

Edited work for (a) and (b):

Consider two following cases.

Case 1 : $b=p^t, \;\;\exists t \in \mathbb{N}$

(a) Choose $t > 2017$, then (a) is true.

(b) Suppose $\underbrace{11\ldots1}_{\text{$2017$}}$ are $n$-th digits of number $x$, where $n=k, k+1, \ldots, k+2016$.

then $v_p(x) \leq v_p(b^k) = v_p(p^{tk})=tk \rightarrow x \leq p^{tk}$ ---[1]

but the $(k+2016)$-th digit of $x$ is $1$ so $x>b^{k+2016}>p^{t(k+2016)}$ contradict [1], so (b) is false.

Case 2 : $b\not=p^t, \;\;\forall t \in \mathbb{N}$

(a) Since $\log_b p$ is irrational, there exist $m, n \in \mathbb{N}$ and $\alpha, \beta \in \mathbb{R}$ such that

$m+\alpha < n\log_b p < m+\beta$, so $b^{m+\alpha} < p^n<b^{m+\beta}$

Let $m>2018$, $\alpha = 0$, $\beta = \log_b (1+b^{-2018})$ then every numbers between $b^{m+\alpha}$ and $b^{m+\beta}$

contains $2017\;\; 0$'s, so $p^n$ contains $2017\;\; 0$'s, hence (a) is true.

(b) As $b^{m+\alpha} < p^n<b^{m+\beta}$, choose $\alpha = \left(\frac{1}{b-1}-b^{-2018}\right)$, $\beta=\left(\frac{1}{b-1}\right)$

then $b^m\left(\frac{1}{b-1}\right)-b^{-2018}<p^n<b^m\left(\frac{1}{b-1}\right)$

choose $m>2020$ then $b^m\left(\frac{1}{b-1}\right)-b^{-2018}$ will contains $2017\;\; 1$'s and $\frac{b^m}{b-1}$ contains more than $2017 \;\; 1$'s so $p^n$ contains $2017\;\; 1$'s, hence (b) is true.


My attempted work for (c) :

Consider order pair of Fibonacci sequence $(F_i,F_{i+1})$, $\;\forall i \in \mathbb{N}$ and remainder of the division of $F_i$ by $b^{2017}$.

Since there are infinitely many order pairs of Fibonacci sequence $(F_i,F_{i+1})$ but finitely many different remainders so there exists $k \in \mathbb{N}$ such that

$F_i \equiv F_{i+k} (\bmod {b^{2017}})$, $F_{i+1} \equiv F_{i+k+1} (\bmod {b^{2017}})$

then $F_i+F_{i+1} \equiv F_{i+k}+F_{i+k+1}(\bmod {b^{2017}}) \rightarrow F_{i+2} \equiv F_{i+k+2} (\bmod {b^{2017}})$

then $F_{i+l} \equiv F_{i+k+l} (\bmod {b^{2017}})$, $\forall l \in \mathbb{N}$

so $F_n (\bmod {b^{2017}})$ is periodic sequence.

I don't know how to find $x$ such that $F_x = b^{2016}+b^{2015}+\ldots+b+1(\bmod {b^{2017}})$

$\endgroup$
  • $\begingroup$ Are those $2017$ digits supposed to be the tail of the number, or can they be in the middle? (the latter would make the problem considerably harder) $\endgroup$ – user228113 Aug 25 '17 at 5:55
  • $\begingroup$ @ G. Sassatelli. That is the exact problem statement. I think it can be in the middle. $\endgroup$ – carat Aug 25 '17 at 6:31
3
$\begingroup$

If $b$ is a power of $p$, then the base-$b$ representation of any power of $p$ has all but its first digit $0$. So (a) is true and (b) false in this case.

If $b$ is not a power of $p$, $\log_b p$ is an irrational number. The integer multiples of $\log_b p$ are then evenly distributed mod $1$. Thus for any $\alpha < \beta $ there are positive integers $m, n$ such that $m + \alpha < n \log_b p < m + \beta$, so that $b^{m+\alpha} < p^n < b^{m+\beta}$. Taking $\alpha = 0$ and $\beta = \log_b(1 + b^{-2018})$, the base $b$ representation of $p^n$ starts with $1\underbrace{00\ldots0}_{\text{$2017$}}$, so (a) is true. Similarly, taking $\alpha = \log_b(1/(b-1) - b^{-2018})$ and $\beta = \log_b(1/(b-1))$, the base $b$ representation of $p^n$ starts with $\underbrace{1\ldots1}_{\text{$2017$}}$, so (b) is true.

EDIT: The Binet formula for the Fibonacci numbers is $$F_n = \frac{\phi^n}{\sqrt{5}} - \frac{(-1/\phi)^n}{\sqrt{5}}$$ where $\phi = (\sqrt{5}-1)/2$ is the Golden Ratio. Thus for large $n$, $F_n$ is very close to $\phi^n/\sqrt{5}$. Now $\log_b(\phi)$ is irrational (since no integer power of $\phi$ is an integer), so the integer multiples of $\log_b(\phi)$ are evenly distributed mod $1$. Thus the base $b$ representation of $\phi^n$, and therefore also of $F_n$, will start with $\underbrace{1\ldots1}_{\text{$2017$}}$ for infinitely many $n$.

$\endgroup$
  • $\begingroup$ Thank you. I don't understand here, please explain why or suggest me where to read : Taking $\alpha = 0$ and $\beta = \log_b(1 + b^{-2017})$, the base $b$ representation of $p^n$ starts with $1\underbrace{00\ldots0}_{\text{$2017$}}$, so (a) is true. $\endgroup$ – carat Aug 25 '17 at 9:15
  • $\begingroup$ Sorry, that should have been $b^{-2018}$. The base $b$ representation of $b^m$ is $1$ followed by all $0$'s. The base $b$ representation of $b^m(1+b^{-2018})$ starts with $1$ followed by $2017$ $0$'s and then $1$. Anything between starts with $1$ followed by at least $2017$ $0$'s. $\endgroup$ – Robert Israel Aug 25 '17 at 17:56
  • $\begingroup$ Thank you very much, this topic is new for me. Please kindly check my understanding in edited work and give me some suggestions for (c). $\endgroup$ – carat Aug 26 '17 at 5:21
  • $\begingroup$ $F_n$ is very close to $\phi^n/\sqrt{5}$ where $\phi$ is the Golden Ratio. Since $\log_b \phi$ is irrational, ... $\endgroup$ – Robert Israel Aug 27 '17 at 8:21
  • $\begingroup$ Sorry, I don't get it. Will you please explain in more details on (c) ? $\endgroup$ – carat Aug 27 '17 at 23:38

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.