5 ms·
Impressive! Out of curiosity, did you have good reason to immediately suspect it couldn't possibly be true? According to Wikipedia, this question had been consi
by Chinjut 12y ago
Impressive! Out of curiosity, did you have good reason to immediately suspect it couldn't possibly be true? According to Wikipedia, this question had been considered considered by Perrin himself (way back in 1899), but was only first resolved by Adam and Shanks in 1982.
- peterderivaz 12y agoI don't know Colin's logic, but my personal reasoning would be: 1. If this were true then it gives a simple, efficient, deterministic method to test for primes. (You can compute P_n modulo n efficiently using matrix exponentiation.) 2. If there was such a method I am sure I would have heard of it before - and people wouldn't bother using Miller-Rabin or the complicated deterministic primality method 3. Therefore there must be a flaw...
- ColinWright 12y agoActually, there is a polynomial algorithm for testing primality, the AKS primality test. http://en.wikipedia.org/wiki/AKS_primality_test http://en.wikipedia.org/wiki/AKS_primality_test In essence, my reasoning was simply that primes don't behave like this. Any connection with addition-type stuff is spurious and doesn't go on forever. Mind you, when I'd searched up to 10^5 and still hadn't found a counter-example I was starting to doubt my intuition. The first counter-example is when the sequence predicts that 521^2 is prime. In fact, if p is prime then p divides k(p). I find that non-obvious, but do follow and believe the proof. Even so, I don't know it well enough to feel enlightened by it. The work continues.
- deleted 12y ago[deleted]