Detailed mathematical approach

Problem Summary

Let \(f(n)\) be the smallest positive integer such that

$\gcd(f(n),m)\gt 1$

for every positive integer \(m\le n\) whose last decimal digit is \(3\). The goal is to compute

$L(n)=\ln f(n)$

for \(n=10^6\), rounded to 6 decimal places. The C++, Python, and Java implementations work with logarithms because minimizing a product of primes is equivalent to minimizing the sum of their logarithms.

Mathematical Approach

Define the target set

$\mathcal{S}_n=\left\{m\in\mathbb{Z}_{\ge 1}: m\le n,\ m\equiv 3 \pmod{10}\right\}.$

We want the cheapest set of primes whose union of divisibility covers every element of \(\mathcal{S}_n\).

Step 1: Reduce the problem to selecting primes

If a prime \(p\) already divides the candidate integer, replacing \(p^k\) by \(p\) for any \(k\ge 2\) keeps the condition \(\gcd(f(n),m)\gt 1\) unchanged and only makes the number smaller. Therefore the optimal \(f(n)\) is squarefree.

So we only need to choose a set of primes \(\mathcal{T}\) and minimize

$L(n)=\min_{\mathcal{T}} \sum_{p\in\mathcal{T}} \ln p,$

subject to the requirement that every \(m\in\mathcal{S}_n\) is divisible by at least one prime in \(\mathcal{T}\).

Step 2: Eliminate residue classes that never create new constraints

Numbers ending in \(3\) are never divisible by \(2\) or \(5\), so those primes are irrelevant. Now split the remaining primes by their residue modulo \(10\):

$\mathcal{P}_3=\left\{p\le n: p \text{ prime and } p\equiv 3 \pmod{10}\right\},$

$\mathcal{P}_7=\left\{p\le n: p \text{ prime and } p\equiv 7 \pmod{10}\right\},\qquad \mathcal{P}_9=\left\{p\le n: p \text{ prime and } p\equiv 9 \pmod{10}\right\}.$

Primes congruent to \(1 \pmod{10}\) are never needed in an optimal answer. If \(q\equiv 1 \pmod{10}\) divides some \(m\in\mathcal{S}_n\), then \(m/q\) is still a positive integer ending in \(3\), and \(m/q\lt m\). Any selected prime that hits \(m/q\) also hits \(m\), so such numbers do not introduce a new obligation.

Every prime in \(\mathcal{P}_3\) is itself an element of \(\mathcal{S}_n\). Hence every feasible solution must contain all of them, contributing the unavoidable term

$L_3=\sum_{p\in\mathcal{P}_3}\ln p.$

Step 3: Identify the forced primes congruent to \(7 \pmod{10}\)

After removing numbers that already contain a \(1 \pmod{10}\) prime factor or a mandatory \(3 \pmod{10}\) prime factor, any remaining target number is built only from primes in \(\mathcal{P}_7\cup\mathcal{P}_9\).

A product of such primes can end in \(3\) only if it contains at least one \(7 \pmod{10}\) prime. More precisely, if we count multiplicities, the number of \(7 \pmod{10}\) prime factors must be odd. That means every unresolved number contains either

$\text{at least three primes from }\mathcal{P}_7,$

or

$\text{one prime from }\mathcal{P}_7 \text{ and at least one prime from }\mathcal{P}_9.$

If \(a\in\mathcal{P}_7\) and \(a^3\le n\), then \(a^3\in\mathcal{S}_n\). Since \(a^3\) has no prime divisor other than \(a\), that prime is forced. Define

$\mathcal{F}=\left\{a\in\mathcal{P}_7: a^3\le n\right\},\qquad L_F=\sum_{a\in\mathcal{F}}\ln a.$

This also automatically covers every target containing at least three \(7 \pmod{10}\) prime factors: if \(a\le b\le c\) are three such factors of \(m\), then \(a^3\le abc\le m\le n\), so \(a\in\mathcal{F}\).

Step 4: Reduce the remaining constraints to prime pairs

Once the forced set \(\mathcal{F}\) is included, the only unresolved cases are numbers containing a nonforced \(7 \pmod{10}\) prime and at least one \(9 \pmod{10}\) prime. Put

$\mathcal{A}=\mathcal{P}_7\setminus\mathcal{F},\qquad \mathcal{B}=\mathcal{P}_9.$

If \(a\in\mathcal{A}\), \(b\in\mathcal{B}\), and \(ab\le n\), then \(ab\equiv 3 \pmod{10}\), so \(ab\in\mathcal{S}_n\). Therefore any valid prime set must include at least one of \(a\) or \(b\).

Conversely, every unresolved target \(m\) contains some pair \(a\in\mathcal{A}\), \(b\in\mathcal{B}\) with \(ab\mid m\), hence \(ab\le m\le n\). Covering all such pairs is therefore equivalent to covering all remaining target numbers.

The optimization becomes

$\min_{X\subseteq\mathcal{A},\,Y\subseteq\mathcal{B}} \left(\sum_{a\in X}\ln a+\sum_{b\in Y}\ln b\right),$

subject to the rule that for every pair \((a,b)\) with \(ab\le n\), at least one endpoint is chosen.

Step 5: Interpret the pair problem as a weighted vertex cover

Build a bipartite graph

$G=(\mathcal{A},\mathcal{B},E),\qquad E=\left\{(a,b)\in\mathcal{A}\times\mathcal{B}: ab\le n\right\}.$

Choosing primes from \(X\subseteq\mathcal{A}\) and \(Y\subseteq\mathcal{B}\) that hit every admissible pair is exactly a weighted vertex-cover problem on this graph, with weights \(\ln a\) and \(\ln b\).

The standard flow reduction applies:

$s\to a \text{ has capacity } \ln a,\qquad b\to t \text{ has capacity } \ln b,$

and every graph edge \(a\to b\) receives a very large capacity. Then the minimum \(s\)-\(t\) cut equals the minimum weighted vertex cover. Hence

$L(n)=L_3+L_F+\operatorname{mincut}(G).$

Worked Example: \(n=800\)

For \(n=800\), the forced \(7 \pmod{10}\) prime is only \(7\), because

$7^3=343\le 800,\qquad 17^3=4913\gt 800.$

Among nonforced \(7 \pmod{10}\) primes, the only ones that still form admissible products with a \(9 \pmod{10}\) prime are \(17\) and \(37\). On the \(9 \pmod{10}\) side, the relevant primes are \(19\) and \(29\). The valid edges are

$17\cdot 19=323,\qquad 17\cdot 29=493,\qquad 37\cdot 19=703,$

all of which are at most \(800\) and end in \(3\).

So the graph has edges

$ (17,19),\qquad (17,29),\qquad (37,19). $

The cheapest cover is \(\{17,19\}\): prime \(17\) covers two edges, prime \(19\) covers the third, and any cover using \(29\) or \(37\) has larger total logarithmic weight. Therefore the optimization stage contributes the factors \(7\), \(17\), and \(19\), and

$f(800)=\left(\prod_{\substack{p\le 800\\ p\equiv 3 \pmod{10}}} p\right)\cdot 7\cdot 17\cdot 19.$

How the Code Works

The C++, Python, and Java implementations begin with a prime sieve up to \(n\). They partition the primes into the residue classes \(3\), \(7\), and \(9 \pmod{10}\), immediately add the logarithms of all mandatory \(3 \pmod{10}\) primes, and then add the logarithms of all forced \(7 \pmod{10}\) primes satisfying \(p^3\le n\).

Next, they construct only the useful part of the bipartite graph. For each nonforced \(7 \pmod{10}\) prime \(a\), every \(9 \pmod{10}\) prime \(b\le n/a\) creates one edge. Vertices that never appear in any edge are ignored, because they cannot affect the minimum cover.

A standard max-flow/min-cut routine is then run on the source-left-right-sink network. The cut value is added to the two mandatory logarithmic contributions, and the final result is rounded to six decimal places. The implementations also use the checkpoints

$L(40)=6.799056,\qquad L(2800)=715.019337$

as sanity checks for the construction.

Complexity Analysis

The prime sieve costs \(O(n\log\log n)\) time and \(O(n)\) memory. Let

$|E|=\#\left\{(a,b)\in\mathcal{A}\times\mathcal{B}: ab\le n\right\}.$

Building the graph takes \(O(|\mathcal{A}|\log|\mathcal{B}|+|E|)\) time: each left-side prime first finds the cutoff point among the sorted right-side primes, then emits exactly its incident edges. The max-flow stage runs on a network with \(O(|\mathcal{A}|+|\mathcal{B}|)\) vertices and \(O(|E|)\) finite edges, so it dominates the remaining runtime. Overall memory usage after the sieve is \(O(|\mathcal{A}|+|\mathcal{B}|+|E|)\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=838
2. Greatest common divisor: Wikipedia — Greatest common divisor
3. Vertex cover: Wikipedia — Vertex cover
4. Bipartite graph: Wikipedia — Bipartite graph
5. Max-flow min-cut theorem: Wikipedia — Max-flow min-cut theorem