3
$\begingroup$

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.

$\endgroup$
4
  • 3
    $\begingroup$ You would need to phrase this question better. What do you mean by "are not the same"? In base 2 or base 10? $\endgroup$
    – Calvin Lin
    Feb 4, 2013 at 0:43
  • 1
    $\begingroup$ It'd be great if you could create a more informative title, too. $\endgroup$ Feb 4, 2013 at 4:32
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 4, 2013 at 5:21
  • $\begingroup$ that's a rather strange question... $\endgroup$
    – Albert
    Feb 4, 2013 at 14:30

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Did you mean $a_j \equiv N (\mod 2+n-j)$ instead of $a_j \equiv n (\mod 2+n-j)$ ? $\endgroup$ Feb 6, 2013 at 9:56
2
$\begingroup$

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.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .