[ColinWright]

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.