|
|
Too many people think Math is Dull.
Astounding Math Stories exists to show you
the kinds of weird things that happen when you do math.
These Astounding Stories also illustrate some important ideas in math,
so this blog also has a Secret Educational Agenda.
The unreliability of numerical evidence
3 April 2008
The Perrin function on the natural numbers is defined inductively this way:
The table below shows the first 30 values. You can check that for these values, if n divides P(n), then n is prime. In fact this checks out through the first couple of hundred thousand integers: always if n divides P(n), then n is prime. Precisely:
For all integers n < 271,441, if n divides P(n), then n is prime.
In other words, the numerical evidence up to 271,441 suggests that if n divides P(n), then n is prime, Now suppose you were a biology Ph. D. and you discovered a new species of frog. Suppose you dissected several specimens and discovered that each one had two livers. Then you could write a paper saying that you had discovered a new species of frog that had two livers. I am not a biologist, but I think such a paper could get published in The Journal of Frogs (or something) and your reputation would be enhanced. Maybe you would even get a tenure-track job. In no case would anyone expect you to dissect over 200,000 specimens before you published! Or even 100.
Mathematics does not work like that. Mathematics is full of sly surprises. You need to be paranoid when you do math research:
271,441 divides P(271,441), but 271,441 is not prime (it is 5212).
MORAL: In math, checking a few hundred thousand cases never tells you everything.
P(271,441) has 33,150 digits. It is an example of a composite number for which n divides P(n).
Remark
It has been proved that for any natural number n, if n is prime, then n divides P(n), so the converse is in fact true for all n.
References
William Adams and Daniel Shanks, “Strong primality tests that are not sufficient”, Mathematics of Computation, Vol. 39, No. 159 (July1982), pp. 255-300.
First 30 values of the Perrin Function
|
n |
P(n) |
|
1 |
0 |
|
2 |
2 |
|
3 |
3 |
|
4 |
2 |
|
5 |
5 |
|
6 |
5 |
|
7 |
7 |
|
8 |
10 |
|
9 |
12 |
|
10 |
17 |
|
11 |
22 |
|
12 |
29 |
|
13 |
39 |
|
14 |
51 |
|
15 |
68 |
|
16 |
90 |
|
17 |
119 |
|
18 |
158 |
|
19 |
209 |
|
20 |
277 |
|
21 |
367 |
|
22 |
486 |
|
23 |
644 |
|
24 |
853 |
|
25 |
1130 |
|
26 |
1497 |
|
27 |
1983 |
|
28 |
2627 |
|
29 |
3480 |
|
30 |
4610 |
|
|