Perrin Sequence
cut-the-knot.org
cut-the-knot.org
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.
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...
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.
The first is P_(271441) with 33,150 digits
EXTENSIONS
... Further terms beyond those shown here have been
computed by cdw10(AT)cix.compulink.co.uk (C Wright)