I'm not a math major, but would like to compete in the Putnam. As suggested in other questions here, I'm working some old contest problems. I'd like some input on this attempted proof--general input is gladly welcomed, but I do have some specific questions (see bottom of post.)


How many primes among the positive integers, written as usual in the base 10, are such that their digits are alternating 1's and 0's, beginning and ending with 1?

Source: http://www.math.ksu.edu//events/ksucomp/putnam/examquestions.htm

Answer: There is only one such prime, namely, $101$.


Consider the numbers of the form $101\ldots01$. Let $a_n$ be the number of this form with $n$ ones in its base-10 representation. That is: $$a_n = \sum_{k=0}^{n-1}10^{2k} \tag{1}$$ It follows: $$\begin{align} a_n &= \sum_{k=0}^{n-1}\left(10^2\right)^k \\ &= \frac{\left(10^2\right)^n-1}{10^2-1} \\ &= \frac{(10^n)^2-1}{99} \\ &= \frac{(10^n-1)(10^n+1)}{9\cdot 11} \end{align}$$

We now note that $10^n-1=9\sum_{k=0}^{n-1}10^k$. Thus:

$$a_n = \frac{\left(\sum_{k=0}^{n-1}10^k\right)(10^n+1)}{11} \tag{2}$$

Let $b_n$ be the numerator in $(2)$; that is: $$b_n = \left(\sum_{k=0}^{n-1}10^k\right)(10^n+1)$$

From formula $(1)$, we can see that $a_n$ is the sum of integers, thus, $a_n$ is clearly an integer. For $a_n$ to be a prime, $b_n$ must satisfy the following: $$b_n = 11\cdot p\text{, where $p$ is prime.}$$

Therefore, one of either $\left(\sum_{k=0}^{n-1}10^k\right)$ or $(10^n+1)$ must be $11$, and the other is prime. For $n=1$, we see: $$\left(\sum_{k=0}^{n-1}10^k\right) = 1;\qquad(10^n+1)=11$$ For $n=2$, we see: $$\left(\sum_{k=0}^{n-1}10^k\right) = 11;\qquad(10^n+1)=101$$ As both terms are monotonically increasing, these two are the only ways to have either one equal to $11$. Of these two, only one pair contains a prime (namely, $101$).

My questions:

First and foremost, I want to know if my proof is valid/on the right track. :) After that, I'd like to know if I'm covering the proof in enough detail. Specifically:

  1. I assert that $10^n-1=9\sum_{k=0}^{n-1}10^k$. Do I need to prove this, or is it obvious enough? (Subtracting $1$ from a power of $10$ leaves a number with as many $9$s as there are $0$'s in the power of $10$.)
  2. Do I need to show further why $b_n$ must be $11$ times a prime? Or is it clear that all other cases yield composite $a_n$?
  3. Is my reasoning that there are only these two solutions (i.e. monotonically increasing terms) legitimate?

And, finally, is there some well-known theorem that I have totally overlooked that would make solving this problem easy?

  • 1
    $\begingroup$ If I was grading it, I would give you full credit. $\endgroup$ Aug 29, 2013 at 23:17
  • 1
    $\begingroup$ It's valid. After using the formula for a geometric sum, you need not worry about dividing $10^n-1$ by $10-1$. Very good job. $\endgroup$ Aug 29, 2013 at 23:19
  • 3
    $\begingroup$ not a mathematician, but that was a pleasure to read. just thanks for posting it. $\endgroup$ Aug 29, 2013 at 23:22
  • 2
    $\begingroup$ Just to nitpick for Putnam-level grading: "Therefore, one of either ... or $10n+1$ must be $11$, and the other is prime." This is not strictly true. People often neglect that a factorization could involve $1$, so that one of these factors could be $1$ and the other could be $11p$. This is an easy situation to address, since it would force $n$ to be $1$. $\endgroup$
    – 2'5 9'2
    Aug 29, 2013 at 23:45
  • $\begingroup$ @alex.jordan Thanks--I can't believe I overlooked that. :) $\endgroup$
    – apnorton
    Aug 29, 2013 at 23:51

2 Answers 2


You can actually cut your proof short a fair bit earlier — once you have $a_n=(10^n+1)(10^n-1)/99$, you can note that for $n\gt 2$, both of these factors are larger than $2\times 99$ and so there must be a factorization of $a_n$ into two numbers each larger than $2$.

More formally, you can split into the case of even $n$ and odd $n$; for even $n$ then $99|10^n-1$ so you have $a_n=(10^n+1)\times \left((10^n-1)/99\right)$ with each factor $\gt 1$, while for odd $n$ $11| 10^n+1$ and $9|10^n-1$ so $a_n=\left((10^n+1)/11\right)\times\left((10^n-1)/9\right)$ with each factor $\gt 1$. (These divisibility properties are immediate from $10\equiv 1\pmod 9$ and $10\equiv -1\pmod{11}$). This also explains why the proof breaks down at $n=2$; there, you still have $a_n=(10^n+1)\times\left((10^n-1)/99\right)$, but it's no longer the case that the right factor is $\gt 1$.

  • $\begingroup$ (Also, thank you for the flashback - this was one of the Putnams I took back in college, the one I did particularly well on, and it's a joy to see this question again!) $\endgroup$ Aug 29, 2013 at 23:29
  • $\begingroup$ Just wanted to see if I got the idea right -- if $n > 2$ then theres a factorized quotient remaining after dividing the numerator by $99$ and that's why for $n>2$ it's composite? $\endgroup$
    – Airdish
    Jul 19, 2016 at 14:01
  • $\begingroup$ @Airdish Sort of, though you don't explicitly know the factors without doing the odd/even analysis - what you can say is that $a=mn / 99$ with $m$ and $n$ both greater than 99, and so you know there's some factorization $a=ij$ with $i,j\gt 1$. $\endgroup$ Jul 19, 2016 at 15:24
  • $\begingroup$ Alright, thanks :) This problem came in my textbook and I had no idea how to solve it, so I'm really glad I came across this post. $\endgroup$
    – Airdish
    Jul 20, 2016 at 9:45

Your proof looks good to me. Here's an alternative proof, which is not necessarily better but was the first thing that came to my mind:

Let $a_n$ be as in your proof. It is easy to see that if $m\mid n$ then $a_m\mid a_n$ (just consider the process of long division). By inspection, I found that if $n$ is odd then $$a_n=\left(\sum\limits_{k=0}^n 10^k\right)\left(1+\sum\limits_{k=0}^{(n-1)/2}9\cdot 10^{2k}\right).$$ Thus $a_n$ can only be prime when $n$ is an even prime, i.e. $n=2$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .