Some Sage code about Fibonacci-like sequences and primality tests

[mmcirvin]

For a little while I've been poking around in some basic number theory using the Sage computer mathematics system (and a tiny bit of PARI/GP, which is another package that comes bundled inside of Sage).

I was initially inspired by a blog post of John Cook's about the Perrin numbers, a sequence sort of like the Fibonacci numbers that can be used

Comments

[mmcirvin]

OK, guess I should have been using Python docstrings for my function descriptions. I'm learning this stuff as I go along.

[mmcirvin]

Here's an arbitrary-order version of the search:

def search(order, coeff_limit, print_min, max):
"""Search coefficient space to the specified order for sufficiently large first pseudoprimes."""
def search_coeffs(coeffs, print_min, max):
M = recur(coeffs)
p = first_pseudoprime(M, max)
if p == None :
print coeffs,": OUT OF RANGE"
elif p >= print_min :
print coeffs,": ",p, factor(p)

def loop_coeffs(coeffs, order, coeff_limit, print_min, max):
if (order <= 0) :
search_coeffs(coeffs, print_min, max)
else :
for c in xrange(-coeff_limit, coeff_limit+1):
coeffs.append(c)
loop_coeffs(coeffs, order-1, coeff_limit, print_min, max)
coeffs.pop()

coeffs = []
loop_coeffs(coeffs, order, coeff_limit, print_min, max)

[mmcirvin]

Using this, I found a really splendid one at order 5 where the recurrence is just simple addition and subtraction, the ratios of successive values asymptotically approach a constant like the Fibonacci and Perrin numbers, and the first two pseudoprimes are 4 and 14,791,044 (the above code actually missed the 4 case because it doesn't check the initial seed numbers, a good thing because it would have rejected this recurrence entirely otherwise); and a sort of parody of the Lucas numbers at order 6 that raises the first pseudoprime from 705 to 3,787,601.

[acw]

I think that for any linear recurrence, the ratio of successive values converges.

[mmcirvin]

Not if the recurrence matrix only has complex eigenvalues. Sometimes not even if it has a mixture of complex and real ones.

I was just making funky-looking graphs of some of the cases where it doesn't:

https://plus.google.com/u/0/100452847199780289157/posts/LD5EbVE814H
https://plus.google.com/u/0/100452847199780289157/posts/b99dxTV4j1o

N.B.

[mmcirvin]

The "signature" format used by this code has the coefficients in the reverse order from that used by OEIS, e.g. here.

Lem

[anonymous]

Is your "Lemography" still on the web?

Thanks much!

Re: Lem

[mmcirvin]

Not at the moment. I may revive it someday.