# Base-b representation

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}})$

• 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) – user228113 Aug 25 '17 at 5:55
• @ G. Sassatelli. That is the exact problem statement. I think it can be in the middle. – carat Aug 25 '17 at 6:31

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$.
• 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. – carat Aug 25 '17 at 9:15
• 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. – Robert Israel Aug 25 '17 at 17:56
• $F_n$ is very close to $\phi^n/\sqrt{5}$ where $\phi$ is the Golden Ratio. Since $\log_b \phi$ is irrational, ... – Robert Israel Aug 27 '17 at 8:21