Conjecture I came up with

Question

For each number translated into binary $0$, $1$, $10$, $11$, $100$, $101$, $110$, $111$, $1000$, ... find a number where, when you take the length of the binary number, the binary number and the number modulus the first of that many integers greater than $1$ are the same.

Example:

$n=23$. In binary this is $10111$ which has length $=5$.

$23 \equiv 1\pmod{2}$

$23 \equiv 2\pmod{3}$

$23 \equiv 3\pmod{4}$

$23 \equiv 3\pmod{5}$

$23 \equiv 5\pmod{6}$

Taking these as digits, we get the number $12335$. However, $10111\neq 12335$, so $23$ does not fit.

I thought it would be a neat test. I'm not sure if there are any possible matches besides zero and one. How would I go about proving or disproving whether or not there are? There is no solution other than $0$ and $1$ up to $2$ billion.

Answer 1

A non-trivial solution cannot exist. The question is equivalent to asking whether for some n-digit number $N$ written in base 2 (I'll enumerate the digits starting $a_1$ to $a_n$), $$a_j \equiv n (\mod 2+n-j),$$ for $j=1,2,...n$. This seems to be the only interpretation, because if the second number is taken to be in base $10$ the resulting number would have approximately $\lfloor\log_{10}2^{n}\rfloor \approx \lfloor0.3n\rfloor < n$, so there would trivially be no solutions. Now since $N$ has n digits, $a_n=1$ (because we only have two choices and it can't be zero) and so $n \equiv 1 (\mod 2)$, or in other words n is odd. Now by the Chinese Remainder Theorem, a system of congruences has a solution if and only if $$a_i \equiv a_j (\mod \gcd(i,j))$$ for all $i,j$, which implies that all the digits must equal $1$ (to see this, notice that because $n$ is odd, the odd-numbered digits must all be congruent to $a_n$ modulo $2$ and hence must also be $1$; similarly we must have $a_{n-1} \equiv a_{n-4} \equiv 1(\mod 3)$ so all $a_{3k} = 1$ etc. for all $a_{p\alpha}$ for primes $p \leq \sqrt{n}$. In particular, $a_2=1$, which is key) so we have a number of the form $N=111...1$. But this implies that $$a_2 \equiv 1 \equiv n \equiv 0 (\mod n),$$ a contradiction. Not a terribly rigorous proof but I hope this helps.

Answer 2

There are no such numbers exist above 63.

Let $\ n = \overline{b_1b_2\dots b_k},\ \ k>6$
$b_1=1\ \ \Rightarrow\ \ n\equiv 1(\mod 2)\ \ \Rightarrow\ \ \forall m\in\mathbb{N}\ \ \ n\not\equiv 0(\mod 2m)\ \ \Rightarrow\ \ \forall m\in\mathbb{N}\ \ b_{2m-1}=1$
So, there are no two adjacent zero bits in n.
$b_7=1\ \ \Rightarrow\ \ n\equiv 1(\mod 8)\ \ \Rightarrow\ \ n = \overline{b_1b_2\dots 001}$
Contradiction.