Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
You would need to phrase this question better. What do you mean by "are not the same"? In base 2 or base 10? –  Calvin Lin Feb 4 '13 at 0:43
    
He is going to make a new number out of the number k. The nth digit(not necessary digit because for congruences greater than 1 he can get a 2 digit number) of the number (from left to right) will be the congruence of k mod(n+1) –  Jorge Fernández Feb 4 '13 at 1:12
1  
It'd be great if you could create a more informative title, too. –  Zev Chonoles Feb 4 '13 at 4:32
1  
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. –  Greg Martin Feb 4 '13 at 5:21
    
that's a rather strange question... –  Glougloubarbaki Feb 4 '13 at 14:30

2 Answers 2

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.

share|improve this answer
    
Did you mean $a_j \equiv N (\mod 2+n-j)$ instead of $a_j \equiv n (\mod 2+n-j)$ ? –  Egor Skriptunoff Feb 6 '13 at 9:56

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.

share|improve this answer
    
Very nice...... –  Ross Millikan Feb 9 '13 at 22:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.