Search code examples
primessage

Primes in arithmetic progressions in Sagemath

I am in need of finding prime numbers in arithmetic progression

80218110*n+8021749, n=1 to 100,000

I was told that using Sage would be a good option, since my computer is old. I happen to be new to Sage and I haven't found it to solve my problem, I guess it shouldn't be difficult, does anyone have a good reference for printing primes in arithmetic progressions?

Solution

  • SageMath is based on Python, and Python provides a syntax which should be comfortable for mathematicians:

    [80218110*n + 8021749 for n in range(100)]

    range(100) is the ordered set 0, 1, 2, ..., 99, and so the previous line evaluates 80218110*n + 8021749 for these values of n. We can also test whether the entries are prime:

    INPUT: [80218110*n+8021749 for n in range(100) if (80218110*n+8021749).is_prime()]
OUTPUT: 
[8021749,
 489330409,
 569548519,
 970639069,
 1050857179,
 1131075289,
 1772820169,
 2093692609,
 2173910719,
 3136528039,
 3617836699,
 4660672129,
 4740890239,
 5382635119,
 6425470549,
 7067215429,
 7227651649,
 7548524089]

    You can of course make the argument to range larger, but maybe it's not a good idea to print the whole list.

    INPUT: len([80218110*n+8021749 for n in range(100000) if (80218110*n+8021749).is_prime()])
OUTPUT: 15273

    (len returns the length of the list.) Producing this list is pretty quick, at least on my computer:

    INPUT: %time L = [80218110*n+8021749 for n in range(100000) if (80218110*n+8021749).is_prime()]
OUTPUT CPU times: user 94.6 ms, sys: 1.13 ms, total: 95.8 ms
Wall time: 95.5 ms

    (ms is milliseconds.)