The problem statement from the Ole Miss Problems of the Week page is:

Determine the units digit of the product of the first 1000 prime numbers.

With our philosophy of computing first, asking questions later, we realize we have a programmable calculator! We can do that!

We first write a program to generate primes, and multiply them together, until we have generated 1000 primes. We assume the existence of a magic program P043001A that will tell us if a number is a prime: we will give it the number to test in A, and it will return 1 in B is the number is prime. Our program P043001 to multiply together the first 1000 primes is therefore available in a text file with .CAT file contents, or here in text form. Lines and parts of lines starting with a semicolon (“;”) are comments and are not actually entered into the calculator.

; Variables: ; A is the number which may be a prime ; B is the indication as to whether A is a prime (0=no, 1=yes) ; C is the number of primes found so far ; D is the product of the primes found so far ; Symbols: ; -> is assignment arrow ; < is less than relational ; = is equality comparision 2->A ; First potential prime is 2 0->C ; No primes found yet 1->D ; Prime product accumulator While C<1000 ; Do until we have 1000 primes Prog "P043001A" ; Figure out whether A is prime If B=1 ; Test primality indicator Then AD->D ; If A is prime, accumulate product C+1->C ; And increment prime count IfEnd ; [End of test primality indicator] A+1->A ; Go on to next potential prime number WhileEnd ; [End of loop until we have 1000 primes] "Product" ; Label the product report D ; Report the product

Now we need a magic primality testing program. A number is a prime if it is divisible only by itself and 1. We could write a really clever primality testing routine. But this is just a puzzle, so we will keep it simple. We will write a routine to simply try 2, then every odd number. If one of these actually divides the number we are testing, then the number is not prime. We can quit trying when we exceed the square root of the number we are checking for primality: if the number is composite — that is, it is not prime — it will have at least two factors, and at least one of them will be less than the square root of the number.

This is not a particularly good way to test primality.
Once 2 and 3 have been shown not to be factors, all possible remaining
factors are of the form 6*n*-1 or 6*n*+1, since all
the other possible divisors are multiples of 2 or 3.
The approach outlined — trying all odd numbers — tests
6*n*+3 as well, even though this is clearly divisible by 3 and
so cannot be the first factor found.
We are doing at least 50% more work than we need to, even using
trial division.
And trial division finds factors, which is much more than we need to
show primality.
But again, this is just a puzzle, and this simple minded approach is
easy to program.

The subroutine practically writes itself. Once again using semicolon to indicate the start of comments that are not to be entered into the calculator, we have the program P043001A:

; Variables: ; A is number to test for primality ; B is candidate factor and result (0=no, 1=yes) ; Symbols: ; -> is assignment arrow ; / is division operator ; <> is inequality relational ; x^2 is x square operator ; > is greater than relational ; = is equality relational 2->B ; First factor to try is 2 If BInt (A/B)<>A ; Test if 2 is a factor Then 3->B ; If not, next factor to try is 3 While BInt (A/B)<>A; Loop while candidate is not a factor If Bx^2>A ; Test whether we have exhausted candidates Then A->B ; If so, first factor is A itself Else B+2->B ; Otherwise, go on to next potential factor IfEnd ; [End of exhausted candidates test] WhileEnd ; [End of loop about candidates] IfEnd ; [End of 2 is a factor test] A=B->B ; A prime if and only if factor found is A itself

This takes an integer in A, and returns in B 0 if the number is not a prime, or 1 if the number is a prime. This is exactly the interface expected by P043001.

All that is left is to run the program (which is available as a text file with .CAT file contents) and look at the units digit.

Unfortunately, running the program gets “Ma ERROR” on the line “AD->D” in P043001. We look at the variable contents: A is 251, B is 1, C is 53, and D is 2.56041159e+98. Checking the meanings assigned to the variables, this means that 251 is the 54th prime found, the product of the first 53 primes is very large, and trying to multiply that product by 251 gives an overflow. Oh, yes. Well, there is that. The product of the first 1000 primes will be a somewhat bigger number than the calculator can hold.

But all problems have an engineering solution, as Wally said to
Dilbert while launching the PC with the catapult.
What to do, what to do?
We could write a multiple precision integer package — one
using lists, perhaps, to store numbers in perhaps radix 10^{10}.
A 500-digit number would turn into a list with 50 elements, each
element holding 10 digits of the number.
We quickly modify our program to add the logarithms of the first
1000 primes and find the logarithm of the product of the first 1000
primes is 3392.831633.
This tells us the product is 3393 digits long, and the first few
digits of the product, but not (alas) the last few digits.
But if we used lists where each element held 10 digits, we would
need 340 list elements — and the CFX-9850A allows only 255
elements in a list.
To handle this problem we would need to do something
perhaps with matrices and odd indexing to pretend the matrix is
a folded list of some type....

Hmm. This simple problem is sounding bigger all the time. We reread the problem description to see if there is some way of avoiding some of this work. Perhaps there is an easier way.

Aha!
Rereading the problem, we notice that we do not need to find the
product of the first 1000 prime numbers.
We need only find the *units digit* of the product of
the first 1000 prime numbers.
Now, if we multiply two numbers, the units digit of the product
is the unit digit of the product of the unit digits of the two
numbers.
(Is that unclear?
Say we need to multiply two numbers, and we only need the units
digit of the result.
Break each number into its units digit and everything else.
So one number will be 10A+B, and the other 10C+D.
Then (10A+B)×(10C+D) is 100AC + 10(AD + BC) + BD.
The A and C parts do not contribute to the units digit; just the
B and C parts do.)
So, editing our product of primes program, right after the line:

Then AD->D ; If A is prime, accumulate product

we add the line:

D-10Int (D/10)->D ; Truncate the product to only the ones digit

This truncates the running product to have only the units digit.
*That* will certainly not overflow!

So now we run the program again. After a little more than half an hour (perhaps we should have used a better primality test), the program says:

Product 0

What?
Primes are odd, and the product of prime numbers is odd, but 0
is even.
This cannot be.
But wait, 2 is a prime, and 2 is even, so *this* product
of primes will be even since we are including 2.
2×3 is 6, 6×5 is 30 ... wait.

Oh dear.

The first and third primes are 2 and 5.
Their product is 10.
So the product of the first *k* primes, where *k*
is at least 3, will be a multiple of 10.
And its units digit will therefore be zero.

Next time, we will think first, compute later. Really, we will.

[ Previous page | Top of page | Next page ]

Copyright © 2001 Brian Hetrick

Page last updated 2 August 2001.