Over a million developers have joined DZone.

Almost If and Only If

· Big Data Zone

The Perrin numbers have a definition analogous to Fibonacci numbers. Define P0 = 3, P1 = 0, and P2 = 2. Then for n > 2, define

Pn+3 = Pn+1 + Pn+0.

The Concrete Tetrahedron says

It appears that n is prime “almost if and only if” Pn mod n = 0.

The “only if” condition is true without qualification: if n is prime, Pn mod n = 0. It’s the “if” part that’s almost true. When Pn mod n = 0, n is usually prime. Composite numbers that satisfy the Perrin condition Pn mod n = 0 are called Perrin pseudoprimes. The smallest Perrin pseudoprime is 271,441. The next is 904,631.

There are only 17 Perrin pseudoprimes less than a billion. By comparison, there are 50,847,534 primes less than a billion.

So if you used the Perrin condition to test whether numbers less than a billion are prime, you would correctly identify all 50,847,534 primes as primes. But out of the 949,152,466 composite numbers, you would falsely report 17 of these as prime.  In other words, you would be 100% accurate in identifying primes as primes, but only 99.999998% accurate in identifying composite numbers as composite.


Published at DZone with permission of John Cook , DZone MVB .

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}