tag:blogger.com,1999:blog-3722233.post6704204702231101478..comments2023-12-07T03:00:23.146-06:00Comments on Computational Complexity: When does n divide a_n in this sequence?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger15125tag:blogger.com,1999:blog-3722233.post-82834967413287934912018-05-09T09:54:49.372-05:002018-05-09T09:54:49.372-05:00can you prove the following sentence plz?
"I...can you prove the following sentence plz?<br /><br />"If n is a prime, n divides A(n)"Anonymoushttps://www.blogger.com/profile/14349278773719278750noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63812051325446743982016-06-19T08:50:11.876-05:002016-06-19T08:50:11.876-05:00Aren't Perrin's pseudoprimes defined by th...Aren't Perrin's pseudoprimes defined by this exact problem?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2109130357437647112016-06-17T13:02:58.312-05:002016-06-17T13:02:58.312-05:00One observation I managed to make is this: a(n) i...One 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.Sindhuhttps://www.blogger.com/profile/01392032223218688689noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29981877445102328502016-06-17T00:52:47.178-05:002016-06-17T00:52:47.178-05:00Proof by OEIS: http://oeis.org/A013998Proof by OEIS: http://oeis.org/A013998Pseudonymhttps://www.blogger.com/profile/04272326070593532463noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61580222478225361512016-06-16T05:08:40.561-05:002016-06-16T05:08:40.561-05:00The second counterexample is 904631.The second counterexample is 904631.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56233053542003324872016-06-15T13:46:49.866-05:002016-06-15T13:46:49.866-05:00I had a simpler "proof" that the conject...I 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).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44514817644142406832016-06-15T06:38:24.577-05:002016-06-15T06:38:24.577-05:00So, like the run of nine 8s in Pi, pointing out th...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61960442734449229902016-06-14T13:25:50.706-05:002016-06-14T13:25:50.706-05:00Something not quite exact here.
2314934680497152...Something not quite exact here. <br /><br />23149346804971526 / 134 does yield a quotient of 172756319440086, but with a remainder of 2.Brian Hayeshttp://bit-player.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68756370389802549872016-06-14T12:32:25.049-05:002016-06-14T12:32:25.049-05:00Interesting that the first counterexample is a per...Interesting 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?<br /> <br />Alas no. The second counterexample is 904631 = 7 x 13 x 9941.Brian Hayeshttp://bit-player.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56909748233263328172016-06-14T09:00:43.887-05:002016-06-14T09:00:43.887-05:00Used a python script to conclude that 271441 is in...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.Teja yyyhttps://www.blogger.com/profile/04347059367465831890noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76469038715873331192016-06-14T07:42:32.897-05:002016-06-14T07:42:32.897-05:00I wrote a program to test it out on the first half...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?Enoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81328491637318963582016-06-13T14:54:42.346-05:002016-06-13T14:54:42.346-05:00counter example: 134 divides a(134)
a(134)/134 = 2...counter example: 134 divides a(134)<br />a(134)/134 = 23149346804971524/134 = 172756319440086Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88201084570929116772016-06-13T14:16:56.314-05:002016-06-13T14:16:56.314-05:00You are correct- 561^2 is the first counterexample...You are correct- 561^2 is the first counterexample.<br />I am surprised you found it so fast!GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50355953880900020372016-06-13T13:16:25.818-05:002016-06-13T13:16:25.818-05:00For one direction of your proof, I hope you make u...For one direction of your proof, I hope you make use of the fact that these numbers count maximal independent sets in cycles.Unknownhttps://www.blogger.com/profile/04996449012882520366noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60257238333676764302016-06-13T13:08:48.855-05:002016-06-13T13:08:48.855-05:00I spent some time trying to prove this, but it tur...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.Joshhttps://www.blogger.com/profile/11676036929432628204noreply@blogger.com