I'm not sure if the recreational-mathematics tag is appropriate, but this problem came up during a practice Putnam seminar so maybe?

The problem:

Say that a positive integer is alternating if when expressed in base 2, any two consecutive digits are different. Is the number of alternating primes finite or infinite?

I chose to attempt this problem for the seminar one week, but I didn't get very far. The best I have is:

The alternating numbers are of the form $0, 1, 10, 101, 1010, 10101,... (\text{base}~2)$. Of these, we need only concern ourselves with the odd alternating numbers, which are all alternating numbers ending with $0$. Thus we may write them as a sum: $$\sum_{k=0}^n 2^{2k} = \sum_{j=0}^n 4^j.$$

Thus the odd alternating numbers are precisely the numbers whose representations in base $4$ consist entirely of $1$'s: $1, 11, 111,... (\text{base}~4)$. The question is now: are there infinitely many primes that are of this form in base $4$?

That's as far as I got. The professor organizing the seminar didn't know what the solution was. Actually he suspected that it was an open problem and he just put it on the weekly problem list for the heck of it.

Do you have any ideas on where we can try to go from here?

  • 2
    $\begingroup$ The number with $n$ ones base $4$ is $(4^n-1)/3$. You ought to be able to work out primality conditions for such a number. $\endgroup$ – Gerry Myerson Jan 16 '13 at 23:25
  • 2
    $\begingroup$ If you are still struggling, another hint: "difference of two squares". $\endgroup$ – Old John Jan 16 '13 at 23:49
  • $\begingroup$ Update: Still working on it. I get why Gerry's comment is valid (is that what you were referring to John?) and I'm thinking about the primality conditions. Not knowing any number theory other than basic definitions (mod, prime, etc.) is making this tough. $\endgroup$ – Gyu Eun Lee Jan 17 '13 at 0:32
  • 1
    $\begingroup$ @proximal, as Old John said, $a^2-b^2 = (a-b)(a+b)$ is all you need - not even modular arithmetic. $\endgroup$ – user27126 Jan 17 '13 at 0:42
  • 1
    $\begingroup$ @proximal And now remember that $4=2^2$... $\endgroup$ – Calvin Lin Jan 17 '13 at 2:54

Following Gerry's remark, we may write any odd alternating number in the following form: $$\frac{4^n-1}{3}.$$ Applying the difference of squares formula, we write $$\frac{4^n-1}{3} = \frac{(2^n+1)(2^n-1)}{3}.$$

For any number $\alpha$ that is not divisible by $3$, either $3 \mid (\alpha-1)$ or $3 \mid (\alpha+1)$. Since $3 \not\mid 2^n$, we conclude that $3 \mid (2^n+1)$ or $3 \mid (2^n-1)$. This shows that for $n > 2$, $\frac{4^n-1}{3}$ is composite. Thus the number of alternating primes is finite.

  • $\begingroup$ Thanks to Gerry, Old John, Sanchez, and Calvin for leading me to this answer. $\endgroup$ – Gyu Eun Lee Jan 17 '13 at 3:09
  • $\begingroup$ The same happens in other bases, $\frac{b^{2n}-1}{b-1}$ is composite for all (not very small) $n$. $\endgroup$ – Jeppe Stig Nielsen Aug 29 '14 at 11:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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