An interesting formula for generating a good many (but not all) primes is n2 + n + 41. If we plug in consecutive integers 1, 2, 3, etc., at least up to a certain point, we can generate prime numbers. Give an integer for which the formula fails.
The formula will fail for 40, resulting in 1681, which is the square of 41. This formula will also fail for 41, since 41 can be factored out. But, it will generate primes if integers from 1 to 39 are used in the formula, and many (but not all) integers greater than 41 as well.
1 Paul Hoffman, Archimedes' Revenge, 1995, Ballantine Books, p. 38-39.
Why this works
The riddle highlights a fascinating mathematical formula for generating prime numbers: \(n^2 + n + 41\). While this formula produces prime numbers for many consecutive integers starting at 1, it fails at \(n = 40\) because plugging in 40 gives \(40^2 + 40 + 41 = 1681\), which is \(41^2\), a composite number. Additionally, at \(n = 41\), the formula results in \(41^2 + 41 + 41\), which can also be simplified to show that it is not prime. This interplay of algebra and prime generation is what makes this riddle both intriguing and educational!