Problem Summary

Let

$$P=\prod_{p<190} p.$$

We want the largest divisor \(d\mid P\) such that \(d\le \sqrt P\). This divisor is the pseudo square root of \(P\). The implementation finally prints the value modulo \(10^{16}\), but the search itself is done exactly.

Mathematical Approach

1. Divisors as Subset Products

Because \(P\) is a product of distinct primes, every divisor corresponds to a subset of the prime list. If \(S\) is the chosen subset, then

$$d=\prod_{p\in S} p.$$

The condition \(d\le \sqrt P\) is equivalent to

$$d^2\le P.$$

So the problem is a subset-product maximization problem under an upper bound.

2. Logarithms Turn the Product Constraint into a Sum Constraint

Multiplication is awkward to compare directly, but logarithms convert products into sums:

$$\log d=\sum_{p\in S}\log p,\qquad \log d\le \tfrac12\log P.$$

That means we want a subset whose log-sum is as close as possible to \(\tfrac12\log P\) from below. This is exactly the shape of a knapsack-style search.

3. Meet-in-the-Middle

The prime list below 190 has 42 elements, so a brute-force scan over all \(2^{42}\) subsets is too large. The code splits the primes into two halves, enumerates all subset sums in each half, sorts those lists, and then combines them efficiently.

For a left subset \(a\) and a right subset \(b\), the candidate is valid when

$$\log a+\log b\le \tfrac12\log P.$$

Among all valid pairs, we need the one with the greatest total logarithm.

4. Exact Validation After Log Filtering

Floating-point logs are used only to narrow the search. They do not decide the final answer. Once the algorithm finds a near-optimal pair of masks, it reconstructs the exact product with big integers and checks

$$d^2\le P$$

using exact arithmetic. This avoids rounding errors and guarantees the final divisor is truly maximal.

5. Why the Search Is Efficient

Each half has roughly \(2^{21}\) subsets. Enumerating both halves is still feasible, especially because subset log sums can be built incrementally from bit masks:

if a mask removes its lowest set bit, the new subset sum is the previous sum plus the log of the corresponding prime.

After sorting, the code uses a monotone scan over the two lists, then inspects a small neighborhood of right-hand candidates around the current boundary to catch the best exact solution.

6. Small Toy Example

Suppose the primes were just \(\{2,3,5,7\}\), split as \(\{2,3\}\) and \(\{5,7\}\). The left subsets give log-values for \(1,2,3,6\); the right subsets give log-values for \(1,5,7,35\).

We then look for the best pair whose combined log does not exceed half of \(\log(2\cdot3\cdot5\cdot7)\). The real problem behaves the same way, just on a much larger prime set.

In this toy instance

$$P=2\cdot3\cdot5\cdot7=210,\qquad \sqrt P\approx 14.49.$$

The best valid divisor is therefore

$$14=2\cdot7,$$

whereas the nearby product \(15=3\cdot5\) already fails because \(15^2=225>210\). This makes the optimization target concrete: we are not looking for the most balanced subset, but for the largest subset product that stays just below the square-root barrier.

7. Modular Output

The final pseudo square root is enormous, so the program prints

$$d \bmod 10^{16}.$$

The value itself is computed exactly in the internal big integer representation, and only the displayed form is reduced modulo \(10^{16}\).

How the Code Works

The program only accepts --skip-checkpoints. The function primes_below(190) generates the 42 primes used in the problem. enumerate_subsets computes every subset mask together with its log-sum and sorts the results. The key implementation trick is incremental subset construction: for a nonzero mask, the code removes its lowest set bit, reuses the previous mask sum, and adds one prime log via __builtin_ctz.

solve_for_primes computes the total log target, splits the primes into two halves, and searches the best valid pair by combining the sorted lists. A monotone pointer finds the boundary in the right list, and then only a very small neighborhood around that boundary is rechecked with exact arithmetic. So logarithms guide the search, but exact integer comparison still decides the winner.

Once a promising pair of masks is found, build_from_masks reconstructs the exact product as a BigInt. The helper square_leq checks whether the square stays below the full product. The BigInt type implements fixed-width multiword multiplication and exact division by \(10^{16}\) for the final printout.

The checkpoint routine compares the fast solver with a brute-force search for smaller prime limits such as 30, 40, and 50. These checks confirm that the meet-in-the-middle logic and the exact validation agree with exhaustive search on small instances.

Complexity Analysis

If there are \(n\) primes, each half has about \(2^{n/2}\) subsets. Enumeration, sorting, and the guided neighborhood scan dominate the cost, so the runtime is about

$$O(2^{n/2}\log 2^{n/2})$$

and the memory usage is about

$$O(2^{n/2}).$$

For \(n=42\), this is feasible, while the naive \(2^{42}\) search is not.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=266
2. Meet-in-the-middle technique: Wikipedia - Meet-in-the-middle attack
3. Subset sum problem: Wikipedia - Subset sum problem
4. Logarithms and monotone search: Wikipedia - Logarithm
5. Big integer arithmetic: Wikipedia - Arbitrary-precision arithmetic