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.

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?

share|improve this question
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. –  Gerry Myerson Jan 16 '13 at 23:25
If you are still struggling, another hint: "difference of two squares". –  Old John Jan 16 '13 at 23:49
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. –  Gyu Eun Lee Jan 17 '13 at 0:32
@proximal, as Old John said, $a^2-b^2 = (a-b)(a+b)$ is all you need - not even modular arithmetic. –  user27126 Jan 17 '13 at 0:42
@proximal And now remember that $4=2^2$... –  Calvin Lin Jan 17 '13 at 2:54

1 Answer 1

up vote 7 down vote accepted

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.

share|improve this answer
Thanks to Gerry, Old John, Sanchez, and Calvin for leading me to this answer. –  Gyu Eun Lee Jan 17 '13 at 3:09
Maybe try $n>2$ since for $n=2$ we have $\frac{5\cdot 3}{3}=5$ is not composite. –  adam W Jan 17 '13 at 3:17
Whoops. Typo :D –  Gyu Eun Lee Jan 17 '13 at 3:24
Just a quick $\LaTeX$ note: I changed all occurence of "|" to "\mid" as it formats much nicer. Notice especially the difference between "\not |" and "\not\mid". –  JavaMan Jan 17 '13 at 4:05
@JavaMan Thanks! I don't usually type up number theory stuff so I didn't know about \mid. –  Gyu Eun Lee Jan 17 '13 at 4:07

Your Answer


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.