3 ms·
It was once presented to me as a fact, and they asked for a proof, that n|k(n) if and only if n is prime. I immediately said that it couldn't possibly be true,
by ColinWright 12y ago
It was once presented to me as a fact, and they asked for a proof, that n|k(n) if and only if n is prime. I immediately said that it couldn't possibly be true, so I was challenged to find a counter-example.
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.
- peterderivaz 12y agoThe list is here: http://oeis.org/A013998 http://oeis.org/A013998 The first is P_(271441) with 33,150 digits
- ColinWright 12y agoFrom that page: EXTENSIONS ... Further terms beyond those shown here have been computed by cdw10(AT)cix.compulink.co.uk (C Wright) I should contact Neil and get him to change that email address.
- Chinjut 12y agoImpressive! 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]