Finding the least exponent in writing a power of 2015 in binary

Question

Written in binary, 2015 looks like

$11111011111_2$

Find the smallest exponent $n > 0$ (if it exists) such that $2015^n$ ends in . . . $1111111111_2$ (ten ones) when written in binary.

Answer 1

the smallest number ending in 10 1's in binary is $2^{10} - 1$ find $k$ such that: $2015^k \equiv -1 \pmod{2^{10}}\\ 2015\equiv -33 \pmod{2^{10}}\\ (-32-1)^{32} = 1 + 32\cdot 32\cdots \equiv 1 \pmod{1024}\\ 2015^{32}\equiv 1 \pmod{1024}$

Check $k=16$,

$(-33)^{16}$ either equals $1, -1$ or something else. If it equals $1$, then we check $k=8$. If it equals $-1$, we are done. If it equals something else, then there will be no $k$ such that $2015^k\equiv -1 \pmod{ 1024}$.

$(-33)^{16} = 1 + 16\cdot 32 \equiv 513 \pmod{1024}$

There is no $k$ such that $2015^k$ ends in 10 1's

Answer 2

First of all, I would like to start off with saying that this is a very interesting question, and I would like to know what possibly caused you to think about this. This is a "brute-force" method, but it sometimes helps identify patterns.

I wrote a simple Java program to find the value of $2015^k$ Where k $\in \mathbb Z, k >0$, convert it to binary, and finally check if it ends in 10 1's...

Here is a pastebin link of the output in the format: $2015^k = ...1111111111_2$, computed up to 10000 terms. http://pastebin.com/nhd9k0ax

---

It simply just verifies what Doug M and angryavian posted above, and what is interesting, is that the last 6 binary terms alternate between: $$000001_2$$ and $$011111_2$$

---

If you would like to test this for numbers other than 2015, here is the Java code i used: http://pastebin.com/D0QA18xt

Answer 3

$2015 = (2^{11}-2^5-1)$. You want $n$ such that $2015^n = k2^{10}-1$ for some integer $k$. Working modulo $2^{10}$, this reduces to finding $n$ such that $(-2^5-1)^n \equiv -1 \mod 2^{10}$.

$$(-2^5-1)^n = (-1)^n \sum_{k=0}^n \binom{n}{k} 2^{5k} \equiv (-1)^n (n 2^5 + 1) \mod 2^{10}$$

When $n$ is odd we need $n2^5 + 1 \equiv 1 \mod 2^{10}$ which is impossible since odd $n$ implies $n2^5+1$ is even.

If $n$ is even, we want $n2^5+1 \equiv -1 \mod 2^{10}$. This reduces to $n2^4 \equiv -1 \mod 2^{10}$ which is impossible if $n$ is even.

Edit (since this was not clear): so, no such $n$ exists.

Answer 4

Generalizing this a bit.

Assume that the binary representation of an integer $n$ ends with $\ldots011\ldots1$, in other words there are $k$ ones at the end preceded by a $0$.

I claim that the $k+1$ last bits in the binary representation of $n^\ell$ behave as follows:

• if $\ell$ is even we have $\ldots000\ldots01$ - a single one preceded by $k$ zeros, and
• if $\ell$ is odd, then the pattern in $n^\ell$ is the same as it is with $n$ - $k$ ones preceded by a single zero.

Proof. The assumption says that $n\equiv 2^k-1\pmod{2^{k+1}}$. Let's calculate the powers modulo $2^{k+1}$. We see that $$ (2^k-1)^2=2^{2k}-2\cdot2^k+1=2^{2k}-2^{k+1}+1\equiv1\pmod{2^{k+1}}. $$ Therefore the residue class of $n$ is of order two modulo $2^{k+1}$. The claim follows from this.

Answer 5

I am adding another answer and not adding on to my previous one, as they are different... As an "extension" to the question... what numbers will end with 10 1's in a row written in binary?

$a^k$ Where k $\in \mathbb Z, k >0$ and $a \in \mathbb Z, a >0$

The following general equation will return 10 1's in a row written in binary:

$((1024 *q)-1)^{2p-1}$ Where $q \in \mathbb Z, q >0$ and $p \in \mathbb Z, p >0$