# Can you answer my son's fourth-grade homework question: Which numbers are prime, have digits adding to ten and have a three in the tens place?

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.

-
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. :) –  Srivatsan Sep 20 '11 at 3:09
Given that it's not known whether there are infinitely many Fermat primes, I would expect this to be difficult. –  Qiaochu Yuan Sep 20 '11 at 3:20
Well, my wife and I had considered Zarrax, and also Zarax, Xarraz, Xerox and Xzarx, but plain Horatio seemed preferable... :-) –  JDH Sep 20 '11 at 3:40
I would love to see the look on your son's teacher's face when he presents his 400+ digit solution :) –  user641 Sep 20 '11 at 12:14
@Swlabr: I don't understand this objection. The existence of more examples says nothing about the difficulty of classifying all examples. –  Qiaochu Yuan Sep 20 '11 at 16:49

I wrote some Perl code for this. There are 125 such primes other than 37 up to 100000000. There are 99 that end with 31. And 26 that end in 33 :). I believe this is exhaustive list. Getting numbers for higher limit is just matter of compute time.

433 631 1531 3331 4231 10333 10531 13033 15031 20233 20431 23131 30133
31033 31231 40231 41131 50131 51031 100333 103231 105031 110233 110431
113131 114031 120331 122131 123031 202231 211231 212131 231031 300331 310231
312031 321031 400033 411031 501031 510031 1000333 1001431 1010431 1011331
1030033 1050031 1110133 1110331 1112131 1130131 1311031 1320031 1400131
1401031 2001331 2011033 2020231 2110033 2130031 2300131 2301031 2400031
3000133 3000331 3011131 3030031 3100231 4010131 4020031 10002133 10002331
10010431 10012033 10014031 10020133 10020331 10023031 10112131 10121131
10201231 10203031 10210033 10220131 10500031 11040031 11101033 11101231
11102131 11111131 11201131 12000133 12020131 15000031 20003131 20004031
20013031 20110231 20112031 20202031 20210131 20211031 20400031 21001033
21100033 21100231 21201031 22002031 22100131 22110031 23100031 30000133
30000331 30010033 30030031 30102031 31110031 32100031 33000031 40000033
40000231 40011031 40101031 50000131 50010031


Code:

#!/usr/local/bin/perl

use strict;
use POSIX qw(ceil);

my $limit =$ARGV[0];
my $cnt=0; my$cnt31=0;
my $cnt33=0; my @sieve = set_sieve($limit);
chk_special($limit*$limit, $limit); print "Special primes:$cnt, Ending with 31: $cnt31, Ending with 33:$cnt33\n";

sub set_sieve {
my $limit =$_[0];
my $i=5; my$incr = 2;
my @sieve = [];
$sieve[0] = 2;$sieve[1] = 3;
while ($i <$limit) {
my $j = 0; my$found = 1;
while (($sieve[$j]*$sieve[$j]) <= $i) {$j++;
if (($i %$sieve[$j]) == 0) {$found = 0;
last;
}
}
if ($found == 1) { push(@sieve,$i);
sp_prime($i); }$i = $i +$incr;
if ($incr == 2) {$incr = 4;
} else {
$incr = 2; } } my$total = $#sieve+1; return @sieve; } sub chk_special { my$limit = $_[0]; my$start = $_[1]; my$i=$start-($start%6)+7;
my $cutoff = power10(length($i)-1)*6;
my $incr = 4; while ($i < $limit) { my$j = 0;
my $found = 1; if (sp_num($i)==1) {
while (($sieve[$j]*$sieve[$j]) <= $i) {$j++;
if (($i %$sieve[$j]) == 0) {$found = 0;
last;
}
}
if ($found == 1) { print "$i\n";
my $mod =$i%100;
if ($mod == 31) {$cnt31++;
}
if ($mod == 33) {$cnt33++;
}
$cnt++; } }$i = $i +$incr;
if ($incr == 2) {$incr = 4;
} else {
$incr = 2; } if ($i > $cutoff) { my$new_start = power10(length($cutoff)-1)*10;$i = $new_start - ($new_start%6) + 7;
$incr = 4;$cutoff = power10(length($i)-1)*6; #print "New_start:$new_start Cutoff:$cutoff\n"; } } } sub sp_prime { my$prime = $_[0]; my$mod_100 = $prime%100; if (($mod_100 == 33) || ($mod_100 == 31)) { my$sum;
$sum += eval join '+', split(//,$prime);
#print "$prime:$mod_100:$sum\n"; if ($sum == 10) {
print "$prime\n"; my$mod = $prime%100; if ($mod == 31) {
$cnt31++; } if ($mod == 33) {
$cnt33++; }$cnt++;
}
}
}

sub power10 {
my $exp =$_[0];
my $power = 1; foreach my$n (1..$exp) {$power *= 10;
}
return $power; } sub sp_num { my$num = $_[0]; my$mod_100 = $num%100; if (($mod_100 == 33) || ($mod_100 == 31)) { my$sum;
$sum += eval join '+', split(//,$num);
if ($sum == 10) { return 1; } else { return 0; } } else { return 0; } }  EDIT: Another curious fact is as sum of digits is 10, all numbers are of the form 1 (mod 3) or 6n+1 type.... - Thanks very much! Could I ask kindly that you post your code? – JDH Oct 7 '13 at 23:50 Not an answer as such but primes that satisfy criteria 2 & 3 have the form: $$\begin{cases} 37\\ 31+6\times10^a\\ 31+5\times10^a+10^b\\ 31+4\times10^a+2\times10^b\\ 31+4\times10^a+10^b+10^c\\ 31+3\times10^a+2\times10^b+10^c\\ 31+3\times10^a+10^b+10^c+10^d\\ 31+2\times10^a+10^b+10^c+10^d+10^e\\ 31+10^a+10^b+10^c+10^d+10^e+10^f\\ 33+4\times10^a\\ 33+3\times10^a+10^b\\ 33+2\times10^a+2\times10^b\\ 33+2\times10^a+10^b+10^c\\ 33+10^a+10^b+10^c+10^e\\ \end{cases}$$ where$a,b,c,d,e,f\in\mathbb N$, are distinct and$\gt1$. Taking any one of these forms, can anyone prove that there are infinitely many primes in the sequence? I would guess that$33+4\times10^a$would be the easiest to try. I will also say that given that many other sequences that are not as restrictive as this (e.g. Goldbach's conjecture, twin prime, Proth, Mersine) cannot be proved to have infinitely many primes this could well be a hiding to nothing. - 37 433 631 1531 3331 4231 10333 10531 13033 15031 20233 20431 23131 30133 31033 31231 40231 41131 50131 51031 100333 103231 105031 110233 110431 113131 114031 120331 122131 123031 202231 211231 212131 231031 300331 310231 312031 321031 400033 411031 501031 510031 1000333 1001431 1010431 1011331 1030033 1050031 1110133 1110331 1112131 1130131 1311031 1320031 1400131 1401031 2001331 2011033 2020231 2110033 2130031 2300131 2301031 2400031 3000133 3000331 3011131 3030031 3100231 4010131 4020031 10002133 10002331 10010431 10012033 10014031 10020133 10020331 10023031 10112131 10121131 10201231 10203031 10210033 10220131 10500031 11040031 11101033 11101231 11102131 11111131 11201131 12000133 12020131 15000031 - Thanks very much! Could you say a few words about your method? – JDH Sep 22 '11 at 20:02 I wrote bunch of line of mathematica code to generate this. This is an exhaustive list of numbers from 1 to 20 million which satisfies given conditions. Nothing fancy. Just wanted see whether any obvious pattern exist. – Yudhi Kandel Sep 23 '11 at 4:37 Thanks very much. If possible, could you post your code? – JDH Sep 23 '11 at 12:44 @JDH: I don't know what code Yudhi used, but this is how I'd have done it in Mathematica: Select[Prime[Range[PrimePi[2*10^7]]], (Total[IntegerDigits[#]] == 10 && IntegerDigits[#][[-2]] == 3) &] – Guess who it is. Sep 24 '11 at 4:53 As requested I'm posting this an answer. I wrote a short sage script to check the primality of numbers of the form$10^n+333$where$n$is in the range$[4,2000]$. I found that the following values of$n$give rise to prime numbers: $$4,5,6,12,53,222,231,416.$$ Edit 3: I stopped my laptop's search between 2000 and 3000, since it hadn't found anything in 20 minutes. I wrote a quick program to check numbers of the form$10^n+3*10^i+33$. Here are a couple • 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000030000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000033 • 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000300033 • 100000000000000000000000000000000000000000000000000000300000000000000000000000000000000000000033 • 100000000000000000000000000000000000000000000000030000000000000000000000000000000000000000000033 • 100000000000000000000000000000000000000000000030000000000000000000000000000000000000000000000033 • 10000000000000000000000000000000003000000033 • 10000000000000000000000000000030000000000033 • 10000000000000000000000030000000000000000033 • 10000000003000000000000000000000000000000033 There seemed to be plenty of numbers of this form and presumably I could find more if I checked some of the other possible forms as outlined by dr jimbob. Note: I revised the post a bit after jimbob pointed out I was actually looking for primes that didn't quite fit the requirements. Edit 4: As requested here are the sage scripts I used. To check if$10^n+333$was prime: for n in range(0,500): k=10^n+333 if(is_prime(k)): print n  And to check for numbers of the form$10^n+3*10^i+33$: for n in range(0,500): k=10^n+33 for i in range(2,n): l=k+3*10^i if(is_prime(l)): print l  - Thanks very much! ...and I am sure that Horatio will be interested to report these additional cases to his teacher! :-) – JDH Sep 20 '11 at 4:06 Aren't all your answers above (in the edit numbers like 100000030000000000000030000000000000000000000003), having the 3 in the "ones" places not the "tens" place as required in the teacher's problem? I agree with the arguments that they appear to be many (and likely infinite per Michael's argument)? Shouldn't you just check for numbers in the forms$10^n + 3*10^m + 33$or$3*10^n + 3*10^m + 31$or$10^n+5*10^m+31$or$6*10^n + 31$,$4*10^n + 33$, etc. – dr jimbob Sep 20 '11 at 5:40 @Dr jimbob You're right somewhere around writing the first program that condition slipped my mind and I was just looking at digits summing to ten. I'll revise my program and take some new data. – JSchlather Sep 20 '11 at 6:36 Would it be possible for you to post your scripts? – JDH Sep 20 '11 at 14:48 @JDH I've added both. – JSchlather Sep 20 '11 at 17:27 From Srivatsan Narayanan's comment: there are on the order of$n^7$numbers satisfying the digit constraint, with$n$digits. The probability that a random$n$-digit number is prime is of order$1/n$. So naively there are on the order of$n^6n$-digit numbers satisfying all the conditions. The sum of sixth powers diverges (quite strongly!) and I suspect the answer is infinitely many and would be quite surprised to learn otherwise. In particular the number of such integers with$n$digits or less "ought to be" on the order of$1^6 + 2^6 + \cdots + n^6$, or on the order of$n^7$; the number of such integers less than or equal to$x$, then, is on the order of$\log_{10} (Cx^7)$for some constant$C$, or about$7 \log_{10} x\$.

-
I think it's a stretch to assume that being prime and satisfying the digit constraint are uncorrelated events. –  user6701 Sep 20 '11 at 7:22
I agree. But my gut feeling (which I admit may be wrong!) is that that non-independence only shows up in the constant factors that I've suppressed. –  Michael Lugo Sep 20 '11 at 15:25