# Almost If and Only If

# Almost If and Only If

Join the DZone community and get the full member experience.

Join For FreeHortonworks Sandbox for HDP and HDF is your chance to get started on learning, developing, testing and trying out new features. Each download comes preconfigured with interactive tutorials, sample data and developments from the Apache community.

The Perrin numbers have a definition analogous to Fibonacci numbers. Define *P*_{0} = 3, *P*_{1} = 0, and *P*_{2} = 2. Then for *n* > 2, define

*P*_{n+3} = *P*_{n+1} + *P*_{n+0}.

It appears that

nis prime “almost if and only if”P_{n}modn= 0.

The “only if” condition is true without qualification: if *n* is prime, *P*_{n} mod *n* = 0. It’s the “if” part that’s almost true. When *P*_{n} mod *n* = 0, *n* is **usually** prime. Composite numbers that satisfy the Perrin condition *P*_{n} 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.

Hortonworks Community Connection (HCC) is an online collaboration destination for developers, DevOps, customers and partners to get answers to questions, collaborate on technical articles and share code examples from GitHub. Join the discussion.

Published at DZone with permission of John Cook , DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

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

## {{ parent.tldr }}

## {{ parent.linkDescription }}

{{ parent.urlSource.name }}