# Generate a conditional list of integers

Dear all,

I'm assuming I can use Sage to generate a series of integers numbers under certain conditions. Suppose I have a theorem states that: Let N be a square-free positive integer such that N ≡ −1 (mod 24), then........etc

If I want to generate a long list of squarefree numbers N's satisfied the previous condition, how can I do that?

Thank you very much in advance

Mohd

edit retag close merge delete

Sort by » oldest newest most voted

Hello,

If you just want to iterate through these number then you can do

sage: N_max = 1000
sage: for N in srange(23, N_max, 24):
....:    if not N.is_squarefree():
....:        continue
....:    # here N is square free = -1 (24)
....:    print N


And you get as output

23
47
71
95
119
...
959
983


You can also create the list of such integers with

sage: l = [N for N in srange(23, N_max, 24) if N.is_squarefree()]


Then

sage: print l[0], l[1], l[2]
23 47 71


Vincent

more

On a sided note (and related to Rolandb post), you can replace my 'srange' with 'xsrange' and it will be faster.

( 2014-12-04 02:01:48 -0600 )edit

Hi,

Generating a long list takes time. If speed is an issue too, you could consider defining your own squarefree test.

sage: %cython
sage: cimport cython
sage: @cython.cdivision(True)
sage: #Fast up to 5*10^8
sage: cpdef bint is_csquarefree(long long n, unsigned long long priem=10**6):
...       cdef unsigned long p
...       cdef unsigned int* eerste=[2,3,5]
...       cdef unsigned int i=1,k
...       cdef unsigned int* diff=[6,4,2,4,2,4,6,2]
...       if not n: return 0
...       if n<0: n=-n
...       for k in xrange(3):
...           if not n%eerste[k]:
...               n//=eerste[k]    #In 539 of 900 cases a number not dividable by 4,9,25
...               if not n%eerste[k]: return False
...
...       p=7
...       while p<=priem and p*p<=n:
...           if not n%p:
...               e=1 ; n//=p
...               if not n%p: return False
...
...           p+=diff[i%8]
...           if not p%7: i+=1 ; p+=diff[i%8]                     #Small lost of time
...           i+=1
...       return True


Test it:

sage: for k in xsrange(1,1000):
...       if is_csquarefree(k)!=is_squarefree(k): print k


Enjoy speed:

sage: timeit('for k in xrange(10^8,10^8+10^3): is_squarefree(k)==True')
sage: timeit('for k in xrange(10^8,10^8+10^3): is_csquarefree(k)==True')
25 loops, best of 3: 29.2 ms per loop
125 loops, best of 3: 4.86 ms per loop

more

An optimized is_squarefree is already implemented at the level of Sage integers (that calls pari in the background). And note that the fastest for me is timeit('for k in xsrange(10^8,10^8+10^3): k.is_squarefree()==True')

( 2014-12-04 01:59:38 -0600 )edit