0

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.

Wilfred Montoya
  • 113
  • 2
  • 1
    There are two obvious approaches: (1) Factor each positive integer and check the prime factors, as you noted in your post, or (2) Generate non-Gaussian primes, and take the products of various sub-multisets. The only problem with the second approach is if you want to put the products in increasing order. I suppose you could maintain a set of exponents multisets, and at each stage, either increase the exponent of one of the primes in one of the multisets, or move to the next higher non-Gaussian prime. This only works if you're generating the primes starting at the lowest. – Tom Karzes Aug 19 '22 at 04:19
  • The second approach also gets more and more costly as the number of factors increases. I don't know how it compare to the first approach asymptotically. – Tom Karzes Aug 19 '22 at 04:23
  • 1
    Another approach would be to use a prime sieve. You could then filter out the multiples of Gaussian primes up front. – Tom Karzes Aug 19 '22 at 04:27
  • The sizes of the numbers you are examining/generating may inform the choice of algorithm to use. Note that if n = 3 mod 4 then *at least* one of its prime factors is 3 mod 4 and you may discard that n. However if n = 1 mod 4 then you do not know whether or not any of its prime factors are 3 mod 4. – President James K. Polk Aug 19 '22 at 18:33
  • Why is 25 not in the list? (And actually 1 should be the first element.) – Kelly Bundy Aug 20 '22 at 07:09

2 Answers2

0

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.

SargeATM
  • 2,483
  • 14
  • 24
0

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.

rossum
  • 15,344
  • 1
  • 24
  • 38