217
$\begingroup$

My son Horatio (nine years old, fourth grade) came home with some fun math homework exercises today. One of his problems was the following little question:

I am thinking of a number...

  • It is prime.
  • The digits add up to 10.
  • It has a 3 in the tens place.

What is my number?

Let us assume that the problem refers to digits in decimal notation. Horatio came up with 37, of course, and asked me whether there might be larger solutions with more digits. We observed together that 433 is another solution, and also 631 and 1531. But also notice that 10333 solves the problem, based on the list of the first 10000 primes, and also $100333$, and presumably many others.

My question is: How many solutions does the problem have? In particular, are there infinitely many solutions?

How could one prove or refute such a thing? I could imagine that there are very large prime numbers of the decimal form $10000000000000\cdots00000333$, but don't know how to prove or refute this.

Can you provide a satisfactory answer this fourth-grade homework question?

  • 9
    The number of $n$-digit numbers that satisfy your condition (2.) and (3.) is quite small: $\binom{(n-1)+7-1}{7} = \binom{n+5}{7} \approx n^7$. Remember that $n$ is logarithmic in the number itself. It would be surprising (to me) if these contained infinitely many prime numbers. :)2011-09-20
  • 13
    Given that it's not known whether there are infinitely many Fermat primes, I would expect this to be difficult.2011-09-20
  • 10
    Did you really name your son Horatio? :)2011-09-20
  • 78
    Well, my wife and I had considered Zarrax, and also Zarax, Xarraz, Xerox and Xzarx, but plain Horatio seemed preferable... :-)2011-09-20
  • 0
    @SrivatsanNarayanan i would like to see the proof of your statement, can u share the link?2011-09-20
  • 0
    Srivatsan and Jacob, thank you very much! Please post your observations as answers, even if they are only partial answers.2011-09-20
  • 5
    @168335 Well, clearly I was just handwaving vigorously in the second sentence. For the first sentence, just count the number of solutions to $x_0 + x_1 + x_2 + \ldots + x_{n-1} = 10$, s.t. $x_i$ are all integers and $x_1 =3$. So you can simplify the equation as $x_0 + x_2 + x_3 + \ldots + x_{n-1} = 7$. That binomial is the number of nonnegative solutions for this. (One can do cut down that number even more by observing that $x_{n-1} \geq 1$, $x_{0} \geq 1$ and so on. I didn't do all that.)2011-09-20
  • 8
    @JDH I seriously wish my parents had named me something like those!2011-09-20
  • 45
    I would love to see the look on your son's teacher's face when he presents his 400+ digit solution :)2011-09-20
  • 1
    @Qiaochu Yuan - they are only a handful (5) known Fermat Primes. The questioner posted 6 in his post. I can't see why his question is necessarily as hard!2011-09-20
  • 8
    @Swlabr: I don't understand this objection. The existence of more examples says nothing about the difficulty of classifying all examples.2011-09-20
  • 2
    Whoa, in one day this made it in to the top ten highest voted questions. While in principle I agree with Qiaochu that the question can potentially be very hard, somehow the statement of the question and Jacob's answer reminds me rather of [Dirichlet's theorm](http://en.wikipedia.org/wiki/Dirichlet's_theorem_on_arithmetic_progressions), but with the "arithmetic" $a\cdot n + b$ replaced by the "geometric" $a^n + b$.2011-09-20
  • 2
    @WillieWong: Isn't that Fermat primes too? Primes in the sequence $a^n + b$ for $a=2$ and $b=1$? (With $b=1$ it so happens that $a^n + 1$ can be a prime only when $n$ is a power of $2$, but the problem statement is the same.)2011-09-21
  • 0
    @Qiaochu Yuan: True, but just because a problem is similar does not mean it is just as hard. Fermant's last theorem being an excellent example! My point was this, and backing it up with the fact that more examples are known (much more if you read the answers) hinting that it isn't necessarily as hard. I mean, if no others were found other than the 6 given, then perhaps, but that isn't the case...2011-09-21
  • 1
    @Swlabr: I still don't understand this objection. Why do you think knowing more examples would necessarily make classifying all examples easier?2011-09-21
  • 0
    I don't. I just don't think you can expect a problem to be difficult because a similar one is hard, but was merely giving the fact that there are more examples as, perhaps, evidence towards this.2011-09-21
  • 0
    The question is missing the text 'find the smallest number which satisfies...' or words to that effect.2013-09-15
  • 2
    I sat in on a lecture by James Maynard - the guy who drastically reduced the prime gap number to less than 600 last year - who claimed that you can find infinitely many primes with a certain decimal digit in the tens place and that this result followed very quickly from his work. Maybe this answers the question..?2014-03-23
  • 0
    @CameronWilliams, that would be great if it is right!2014-03-23
  • 0
    @Cameron: but what about digit sum 10?2015-02-06

6 Answers 6