# Conjecture I came up with

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.

• You would need to phrase this question better. What do you mean by "are not the same"? In base 2 or base 10? Feb 4, 2013 at 0:43
• It'd be great if you could create a more informative title, too. Feb 4, 2013 at 4:32
• It's unusual for randomly formulated processes to interact with other processes. Without evidence to suggest an interaction in this case, I don't find this a significant question. Feb 4, 2013 at 5:21
• that's a rather strange question... Feb 4, 2013 at 14:30

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.
• Did you mean $a_j \equiv N (\mod 2+n-j)$ instead of $a_j \equiv n (\mod 2+n-j)$ ? Feb 6, 2013 at 9:56
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$
$b_7=1\ \ \Rightarrow\ \ n\equiv 1(\mod 8)\ \ \Rightarrow\ \ n = \overline{b_1b_2\dots 001}$