Ask Your Question

Generate a conditional list of integers

asked 2014-12-03 12:59:48 +0100

math1429 gravatar image

updated 2014-12-03 14:21:09 +0100

vdelecroix gravatar image

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


edit retag flag offensive close merge delete

2 Answers

Sort by » oldest newest most voted

answered 2014-12-03 13:36:58 +0100

vdelecroix gravatar image


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


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()]


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


edit flag offensive delete link more


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

vdelecroix gravatar imagevdelecroix ( 2014-12-04 09:01:48 +0100 )edit

answered 2014-12-03 19:08:39 +0100

Rolandb gravatar image


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
edit flag offensive delete link 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')

vdelecroix gravatar imagevdelecroix ( 2014-12-04 08:59:38 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2014-12-03 12:59:48 +0100

Seen: 1,169 times

Last updated: Dec 03 '14