tag:blogger.com,1999:blog-3722233.post4792566710287614960..comments2019-07-18T09:22:37.096-04:00Comments on Computational Complexity: When does n divide a_n? The answer, though you already know it. The Point, though its not as strong as I wanted. Oh well.Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-30383007876170026962016-06-25T09:22:18.410-04:002016-06-25T09:22:18.410-04:00I've added a pointer to a proof in the post.I've added a pointer to a proof in the post.<br />GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11179462901553783632016-06-24T17:55:23.600-04:002016-06-24T17:55:23.600-04:00The point of the series of articles is to take the...The point of the series of articles is to take the interested reader through the process of doing the obvious and naive through to the more complex and less obvious ideas. As you say, matrices can be used quickly and efficiently, working modulo the number we're interested in, to compute the result for a single number extremely quickly. We can trivially test numbers in the millions.<br /><br />But the point is to go beyond millions. Each case is trivial to test, but testing all of them becomes impractical, hence needing the sieving techniques, and some way to avoid testing Every. Single. Number. All. The. Time.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27139510846322616762016-06-22T07:39:29.681-04:002016-06-22T07:39:29.681-04:00I believe it is known (honestly I am not sure) tha...I believe it is known (honestly I am not sure) that most diophantine problems are of the kind "such and such is true for finitely many positive integers". The questions is, is it known how many Perrin psp's there are? I for one, for example, believe that there are finitely many perfect numbers (hence Mersenne primes). My reason for believing this is beyond the scope of this discussion, but, more likely than not, there are tons of examples of ordinary easy to state problems (relatively) for which this is the case...hard to prove these....they might look true for a while, and then...the sequence stops.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30444050503357384722016-06-21T19:12:13.538-04:002016-06-21T19:12:13.538-04:00For more information about Perrin pseudoprimes, se...For more information about Perrin pseudoprimes, see the Shanks article here:<br />http://www.ams.org/journals/mcom/1982-39-159/S0025-5718-1982-0658231-9/home.html .<br /><br />It is very easy to make similar recurrences for which n divides b(n) if n is prime, and counterexamples are rare. Basically, take any monic polynomial p(x) = x^k + ... such that the coefficient of x^{k-1} is 0, and let the roots be a_1, a_2, ..., a_k.<br />Then the sums of the n'th powers of the zeroes of this polynomial will have the desired property, and these satisfy a linear recurrence obtainable from the coefficients of p. For many choices of the coefficients, you'll get sequences for which the smallest composite n dividing a(n) will be fairly large.Jeffrey Shallithttps://www.blogger.com/profile/12763971505497961430noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11727708300104572132016-06-21T19:06:12.855-04:002016-06-21T19:06:12.855-04:00You seem to be claiming that you need to compute a...You seem to be claiming that you need to compute a(n) first and then check divisibility. This is, of course, not so. Any linear recurrence can be computed efficiently mod k through a standard trick involving matrices discussed in my book, Algorithmic Number Theory, and so it is trivial to look for counterexamples up to millions, with no need for extended precision integer arithmetic.Jeffrey Shallithttps://www.blogger.com/profile/12763971505497961430noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19595243882414693352016-06-21T15:30:24.653-04:002016-06-21T15:30:24.653-04:00Could you link to a proof that if n is prime then ...Could you link to a proof that if n is prime then n divides a(n)?Anonymousnoreply@blogger.com