Find the least positive integer that cannot be represented as $\frac{2^a-2^b}{2^c-2^d}$ for some positive integers $a, b, c, d$.
Problem
Source:
Tags: number theory proposed, number theory
23.07.2012 20:40
An equivalent form of that representation is $2^k(1 + 2^{\ell} + 2^{2\ell} + \cdots + 2^{m\ell})$, based on the fact that $2^p-1 \mid 2^q-1$ if and only if $p\mid q$. The first not representable is $11 = 1+2+2^3$ (since $1=1$, $3=1+2^1$, $5=1+2^2$, $7=1+2^1+2^2$, $9=1+2^3$).
23.07.2012 20:46
Appeared in All-Russian 2005, 10.1
01.01.2018 15:44
Basically, a number is representable in this form iff the positions of the $1$s in its binary representation are in arithmetic progression.
12.08.2020 04:50
The number $n$ cannot be represented in this form if it's binary sum i.e $n=\sum2^{a_i}$, where all $a_i$ are distinct,has exponents $a_i$ and $a_i$ are not in arithmetic progression. We see the first such no. is $11=2^3+2^2+2^0$, where $3,2,0$ are not in A.P.