a(1)=0
a(2)=2
a(3)=3
for all n ≥ 4 a(n) = a(n-2)+a(n-3)
Here is a table of a(n) for 2 ≤ n ≤ 23
n 2 3 4 5 6 7 8 9 10 11 12
a(n) 2 3 2 5 5 7 10 12 17 22 29
n 13 14 15 16 17 18 19 20 21 22 23
a(n) 39 51 68 90 119 158 209 277 367 486 644
For 2≤ n ≤ 23 the n such that n divides a(n) are
n = 2,3,5,7,11,13,17,19,23.
Notice a pattern? Of course you do!
I propose the following question which I will answer in my next post (in a week or so)
PROVE or DISPROVE the following:
for all n≥ 2 n divides a(n) iff n is prime.
I spent some time trying to prove this, but it turns out to be false! One can check that 271441 divides a(271441), but 271441 = 521^2 is not prime.
ReplyDeleteYou are correct- 561^2 is the first counterexample.
DeleteI am surprised you found it so fast!
I wrote a program to test it out on the first half a million values and also found the counter-example at 271,441 (the program ran out of heap space before hitting 500,000 so I don't know where the next counter-example is yet). So, is there anything interesting or special about that number?
DeleteThe second counterexample is 904631.
DeleteFor one direction of your proof, I hope you make use of the fact that these numbers count maximal independent sets in cycles.
ReplyDeletecounter example: 134 divides a(134)
ReplyDeletea(134)/134 = 23149346804971524/134 = 172756319440086
Something not quite exact here.
Delete23149346804971526 / 134 does yield a quotient of 172756319440086, but with a remainder of 2.
Used a python script to conclude that 271441 is indeed a counter-example.[Did not read the comment above!] But we need to see if primality is sufficient for the divisibility.
ReplyDeleteInteresting that the first counterexample is a perfect square. It suggests possibly weakening the conjecture: Maybe every n that divides a(n) is either a prime or a prime power?
ReplyDeleteAlas no. The second counterexample is 904631 = 7 x 13 x 9941.
So, like the run of nine 8s in Pi, pointing out the difference between noticing a pattern over a finite range and proving that pattern is true on an infinite range.
ReplyDeleteI had a simpler "proof" that the conjecture is false: if it were true, it would give a very past primality testing algorithm and GASARCH would publish this algorithm somewhere other than this blog. This sequence is similar to a Fibonacci sequence and so (see Matrix Form in the wikipedia article on Fibonacci numbers) one can compute a(n) in time log(n)*(time required to multiply two numbers of size a(n)). One can compute a(n) mod n in time log(n)*(time required to do arithmetic mod(n)), so one can compute it in time O(log(n)^3).
ReplyDeleteProof by OEIS: http://oeis.org/A013998
ReplyDeleteOne observation I managed to make is this: a(n) is divisible by n if n is a prime or pseudoprime. Both 271,441 and 904,631 are Perrin's pseudoprimes.
ReplyDeleteAren't Perrin's pseudoprimes defined by this exact problem?
Deletecan you prove the following sentence plz?
ReplyDelete"If n is a prime, n divides A(n)"