# The Binary Representation in Number Theory?

I was reading "Concrete Mathematics" and confronted the Joseph Problem. I'm astonished that the recurrence equation in binary representation is so simple. i.e. for J(n) say J(345), $\text{J(345) = J(}101011001_2\text{)=}10110011_2$

the recurrence function is to shift the binary representation left by one bit. While the representation in base 10 is more complicated:

$\text{f(2n) = 2 f(n)-1}$

$\text{f(2n+1) = 2 f(n)+1}$

So I'm wondering if representation in other bases(binary, etc.) may aid to the analyzation of number patterns, hence has some application in number theory.

-
en.wikipedia.org/wiki/Josephus_problem didn't help? –  draks ... Jan 13 '12 at 12:48
No one can answer this question? –  Strin Jan 14 '12 at 2:31
Strin, I'm not sure what you're after. Does decimal representation have applications to number theory? –  Yuval Filmus Jan 15 '12 at 3:50
The key point that makes the Josephus problem look good is that multiplying by two (and powers of two) is very simple in binary. But multiplying by any other number is still complicated, so binary doesn't help much for more general problems. –  Rahul Jan 15 '12 at 4:00
I have answered your question by giving some possible generalizations of Josephus problem. I think there are some other representations that are more useful, like Galois representations which play a central part in number theory. To add something, there is a small TYPO in your question, its " Josephus " , not " Joseph " , you mis-spelt the person's name, please rectify it, I can't fix it as I don't have edit rights. –  Iyengar Jan 15 '12 at 5:40

## 2 Answers

Here's an application of binary representation to a problem in Number Theory.

Problem: split the numbers $0,1,2,\dots,2^k-1$ into two sets $A$ and $B$ such that $$\sum_{x{\rm\ in\ }A}x^r=\sum_{x{\rm\ in\ }B}x^r$$ for $r=0,1,\dots,k-1$. Here we take $0^0$ to be $1$. So we want the two sets to have the same number of elements, the same sum, the same sum of squares, etc., up to (and including) the same sum of $k-1$ powers.

Solution: let $A$ have the numbers with an even number of $1$s in binary, $B$, the numbers with an odd number of $1$s.

Example: $k=3$; the numbers (in binary) are $0,1,10,11,100,101,110,111$, so $$A=\lbrace\,0.3,5,6\,\rbrace,\quad B=\lbrace\,1,2,4,7\,\rbrace$$ both with 4 elements, and we have $$0+3+5+6=1+2+4+7=14,\quad 0^2+3^2+5^2+6^2=1^2+2^2+4^2+7^2=70$$

Proof: left to the reader.

-
Very nice application @Gerry Myerson –  Iyengar Jan 15 '12 at 5:38
Nice, I appreciate it. –  Strin Jan 16 '12 at 11:46

Before answering your question, the first thing you have to learn is to wait for the answer, as volunteers, professors etc.. who are present in Math.SE will be personally busy with their own works, its very great thing that they spend time for us in sharing beautiful knowledge free of cost. So the thing we need to do is to wait patiently. Take this just as a request or advice.

Josephus problem, you have mentioned have many generalizations extending it to $n$ , I think you must go through this papers thoroughly , they contain precise information you are looking for.

1. This one is an extended formulation of Josephus problem, which you are looking for, its a paper by Mr.Armin Shams-Baragh .
2. Another one is representing the same in case of $\mathbb{Q}$ , its here . This article is by a group of authors.

Thanks a lot.

-
–  Arturo Magidin Jan 15 '12 at 5:49
Thanks so much. –  Strin Jan 16 '12 at 11:39