Numbers which only have non-gaussian primes as prime factors

Question

I am a mathematician who is interested in the product of non-gaussian primes. A prime p is called non-gaussian, if p mod 4 = 1.

It is easy to generate an ongoing list of natural numbers in Python:

natural_numbers = [1,2,3,4,5]
natural_numbers.append(natural_numbers[-1]+1)

I can just extend this list whenever I need it to be longer. But what if I am interested in numbers that only have non-gaussian primes as prime factors?

product_of_non_gaussian_primes = [5,13,17,29,37,41,53,61,65]
product_of_non_gaussian_primes.append(???)

Checking the prime factorization of the following numbers until one happens to only have non-gaussian primes seems quite inefficient. I was wondering if there is a better way.

Answer 1

One approach that is a finite-dimensional approximation is to create a "vector space" (please excuse a possibly informal use of the term) with non-gaussian primes as the basis.

An example in 3 dimensions would be to use 5, 13, and 17 as the basis. The elements of the space would be given by: { pow(5,a) * pow(13,b) * pow(17,c) | a, b, c are numbers 0, 1, 2, 3, ... }

The elements of this space can be enumerated by enumerating a, b, and c over non-negative integers.

Answer 2

As @Tom Karzes says, you could use a variant of the Sieve of Eratosthenes. Start with an array of bits, all set to 1, with the nth bit representing the number n. Then use the sieving technique to switch every array entry with a non-non-Gaussian prime as a factor to 0. Thus, you are marking every multiple of 2, 3, 7, 11, etc. Any entry not set to 0 represents a multiple of non-Gaussian primes.

If your bit array is too large for memory, you can halve its size by having bit[n] represent the odd number 2n+1, since all even numbers have a factor 2. If that is not enough, then there are methods to process the sieve, i.e. the bit array, in chunks: 0..100000, 100001..200000 etc.

My python is non-existent, though I am sure there are many python examples of the Sieve of Eratosthenes that you can adapt for your purpose.