1
$\begingroup$

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.

  • 0
    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.2012-01-15

2 Answers 2

3

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.

  • 0
    Nice, I appreciate it.2012-01-16
5

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.

  • 0
    See [the FAQ on signing your name](http://math.stackexchange.com/faq#signatures).2012-01-15