prime_range should allow a step

[kedlaya]

Is there any reason not to implement the following?

sage: prime_range(11, 100, 10)
[11, 31, 61, 71]

For this ticket, I have in mind the easy fix of running the same internal algorithm and retaining only the answers in the desired congruence class; that is, prime_range(x, y, z) would be equivalent to

[p for p in prime_range(x, y) if (p-x)%z == 0]

A more advanced (and more efficient) version would be to change the underlying algorithm.

Depends on #31548

CC: @DaveWitteMorris

Component: number theory

Author: David Roe

Branch/Commit: u/roed/prime_range @ 7f0a385

Issue created by migration from https://trac.sagemath.org/ticket/29760

[kedlaya]

comment:1

Upon further reflection, maybe I should also be asking for this in the primes iterator.

[mkoeppe]

comment:2

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[roed314]

Branch: u/roed/prime_range

[roed314]

comment:4

Dependence on #31548 is in order to have FLINT's ulong_extras.

---

Last 10 new commits:

1a7bb38	Fixing some bugs
6f41da9	Fixing doctest problems from switching default implementation to flint for small matrices
cd1b853	Merge branch 'u/roed/nmod_mat' of trac.sagemath.org:sage into t/31548/nmod_mat
d0507c4	Working on fixing reduction matrix bug
9748ffc	Add deprecation warning to _reduction_matrix
6e2b75a	Merge branch 'u/roed/nmod_mat' of trac.sagemath.org:sage into t/31548/nmod_mat
ee10b06	Working on documentation and fixing tests
465f51d	Working on documentation
760e0c9	Small fixes
726b135	Add step to prime_range and primes

[roed314]

Author: David Roe

[roed314]

Commit: 726b135

[roed314]

Dependencies: #31548

[roed314]

comment:5

The changes in this ticket are all in sage/rings/fast_arith.p* and sage/arith/misc.py.

[sagetrac-git]

Changed commit from 726b135 to 7f0a385

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

7f0a385

Fix fast_arith.pxd

[kedlaya]

comment:7

Looks fine modulo the dependence on #31548.

[mkoeppe]

comment:8

Setting a new milestone for this ticket based on a cursory review.

[mezzarobba]

comment:9

needs rebase, dependency too