Perrin Sequence(cut-the-knot.org)
cut-the-knot.org
Perrin Sequence
http://www.cut-the-knot.org/arithmetic/combinatorics/PerrinSequence.shtml
1 comments
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.
I 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...
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...
Actually, there is a polynomial algorithm for testing primality, the 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.
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]
The list is here:
http://oeis.org/A013998
The first is P_(271441) with 33,150 digits
The first is P_(271441) with 33,150 digits
From that page:
EXTENSIONS
... Further terms beyond those shown here have been
computed by cdw10(AT)cix.compulink.co.uk (C Wright)
This was in the days before languages like Python, with arbitrary precision integers. I used C to find the first place it failed, and indeed, all counter-examples less than 2^32.
There aren't many, and they have interesting things in common. It's a fascinating mathematical and programmatic playground.