Ask Your Question
2

How do I create subsets of sets?

asked 2011-02-26 14:17:51 +0100

Mike gravatar image

updated 2011-02-26 15:05:38 +0100

DSM gravatar image

How do I create, for example, the set of all primes less than 100 which are congruent to 1 mod 6? In Magma, I would do something like this:

{p : p in [0..100] | IsPrime(p) and (p mod 6) eq 1};

After 25 minutes of searching the Sage documentation, googling, and trying things at random, I can't figure out how to make such a construction in Sage.

(I'm not so interested in this particular set, but rather how to do constructions like this in general [e.g., the subset of all matricies whose given minor has a certain rank, etc.).

edit retag flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted
2

answered 2011-02-26 14:32:28 +0100

Jason Bandlow gravatar image

Here is one solution:

sage: [p for p in [0..100] if is_prime(p) and (p%6)==1]
[7, 13, 19, 31, 37, 43, 61, 67, 73, 79, 97]

For more documentation on this, look for list comprehensions in your favorite Python documentation.

edit flag offensive delete link more
4

answered 2011-02-26 14:57:28 +0100

DSM gravatar image

updated 2011-02-26 14:59:20 +0100

You can also use a generator expression instead of a list comprehension; it's a very similar syntax, but whereas a list comprehension constructs an object of type list immediately, the generator expression is a lazy object:

sage: [p for p in (0..100) if is_prime(p) and (p%6)==1]
[7, 13, 19, 31, 37, 43, 61, 67, 73, 79, 97]
sage: 
sage: # generator expression
sage: (p for p in (0..100) if is_prime(p) and (p%6)==1)
<generator object <genexpr> at 0x10e0be3c0>

which you can turn into a list or a set or anything else:

sage: list(p for p in (0..100) if is_prime(p) and (p%6)==1)
[7, 13, 19, 31, 37, 43, 61, 67, 73, 79, 97]
sage: tuple(p for p in (0..100) if is_prime(p) and (p%6)==1)
(7, 13, 19, 31, 37, 43, 61, 67, 73, 79, 97)
sage: set(p for p in (0..100) if is_prime(p) and (p%6)==1)
set([97, 67, 37, 7, 73, 43, 13, 79, 19, 61, 31])

[Except for a technicality about the variables, list(p for p in (0..100)) is the same as [p for p in (0..100)].]

Why is this useful? Well, since you don't have to construct the list in memory, you can use it in ways that list comprehensions can't be used. E.g.

sage: time min([k for k in IntegerRange(10**5) if is_prime(1000*k+1)])
CPU times: user 2.69 s, sys: 0.12 s, total: 2.81 s
Wall time: 2.99 s
3
sage: time next(k for k in IntegerRange(10**5) if is_prime(1000*k+1))
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00 s
3

The listcomp is really slow because it has to construct the whole list first, taking time and memory, before anything can happen with it, even though we're only going to care about a few terms. The genexp builds as you iterate.

FWIW, I'd have written your original function -- assuming you really wanted a list, and not a set -- as

sage: list(p for p in primes(100) if p % 6 == 1)
[7, 13, 19, 31, 37, 43, 61, 67, 73, 79, 97]
edit flag offensive delete link more

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

Stats

Asked: 2011-02-26 14:17:51 +0100

Seen: 912 times

Last updated: Feb 26 '11