Previous page Next page Navigation bar

Puzzles

2001/2002 Puzzles

30 April 2001 (Prime 500)

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 6n-1 or 6n+1, since all the other possible divisors are multiples of 2 or 3. The approach outlined — trying all odd numbers — tests 6n+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 1010. 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 ]

Previous page Top of page Next page Navigation bar

Copyright © 2001 Brian Hetrick
Page last updated 2 August 2001.

Brian’s Casio Calculator Corner

Home

Programs

Tutorial

Puzzles

Index

2001/2002

Index

15 April 2002

11 February 2002

1 October 2001

24 September 2001

13 August 2001

30 July 2001

18 June 2001

4 June 2001

21 May 2001

7 May 2001

30 April 2001

23 April 2001

9 April 2001

18 February 2001

4 February 2001

29 January 2001

Previous years

In memoriam: Dijkstra

Site Information

Your Privacy

Site Map

E-mail

Site Technical Data