Question Details

No question body available.

Tags

python algorithm combinatorics number-theory

Answers (2)

Accepted Answer Available
Accepted Answer
January 8, 2026 Score: 1 Rep: 67,674 Quality: High Completeness: 50%

  1. Calculate all the primes up to and including half of your range, and their indices.

  2. Make a "Boolean" bit array "primes" of size [range][prime count].

  3. For each integer in your range, calculate if it is divisable by each prime, and if so, mark that boolean/bit as true/1. (Numbers should not be marked as multiples of themselves, or 1)

  4. Now you finally iterate over the combinations. For each combination, look up the primes array for each of the values. If any index in that array is true/1 for all of the values, then all the values in this combination are a multiple of that prime, and thus of another combination, and thus can be skipped.

Values up to ~625 would only have to calculate up to 64 primes, and thus each integers' primes row fits in a 64-bit integer, taking about 5kb total. 128 bits gets you ranges up to ~1417, about 23kb. You can very slightly increase the range by hard coding the "divisible by 2" check, but the range increases by such a small amount that it's not worth the performance penalty.

January 8, 2026 Score: 1 Rep: 21,455 Quality: Medium Completeness: 50%

Are there any algorithms, data structures, or precomputed tables

Euclid's GCD algorithm seems pretty relevant here, on the face of it. Use it to discard candidate 4-tuples.

The sieve of Eratosthenes will often be relevant when separating primes from compound numbers. There's a rich literature surrounding it, suggesting ways to make it take less memory and less time.

Other data structures may be relevant, such as Bloom filters. You have not yet told us how to evaluate competing solutions, so it's categorically not possible to sensibly tune the Bloom parameters at this time.

Your "math for scale" clarification suggests you're interested in a solution space of on the order of a trillion 4-tuples. Presumably you're not going to use all of them in a single batch -- you will explore the space in some order, perhaps starting with smaller integers. To effectively apply any of these well known mathematical tools, you will need to first write down what your true business requirements are. Only then can we explore the solution space in a sensible way which adds value beyond the obvious "enumerate all tuples and naïvely discard the scaled ones".

You have constraints: time, money, RAM. What are they? How do you value them?

Counting to 1e12 takes a long time. The originally stated problem of counting to 1e4 is trivial, even for an Apple ][+.

Prefer to solve "the 2-tuple problem" first. Your experiences there will give insight into what would make sense for the 3-tuple and eventually the 4-tuple problem. It appears there are symmetries you could exploit.