Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


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?

share|cite|improve this question
If I was grading it, I would give you full credit. – Daniel Montealegre Aug 29 '13 at 23:17
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. – Daniel Fischer Aug 29 '13 at 23:19
not a mathematician, but that was a pleasure to read. just thanks for posting it. – andrew cooke Aug 29 '13 at 23:22
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$. – alex.jordan Aug 29 '13 at 23:45
@alex.jordan Thanks--I can't believe I overlooked that. :) – apnorton Aug 29 '13 at 23:51
up vote 6 down vote accepted

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$.

share|cite|improve this answer
(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!) – Steven Stadnicki Aug 29 '13 at 23:29
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? – Airdish Jul 19 at 14:01
@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$. – Steven Stadnicki Jul 19 at 15:24
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. – Airdish Jul 20 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$.

share|cite|improve this answer

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.