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

Prompt:

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

Proof:

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|improve this question
1  
If I was grading it, I would give you full credit. –  Daniel Montealegre Aug 29 '13 at 23:17
1  
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
1  
not a mathematician, but that was a pleasure to read. just thanks for posting it. –  andrew cooke Aug 29 '13 at 23:22
2  
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. :) –  anorton Aug 29 '13 at 23:51

2 Answers 2

up vote 3 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|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

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|improve this answer

Your Answer

 
discard

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.