Project Euler Problem 838

Solution

Answer: 250591.442792

Let $S_N$ be the set of positive integers $n \le N$ whose last digit is $3$.

We seek the smallest integer $f(N)$ such that every $n \in S_N$ shares a common prime factor with $f(N)$.

A few key observations:

If a prime $p \equiv 3 \pmod{10}$, then $p \in S_N$, so $p$ must divide $f(N)$.
Any remaining $n \in S_N$ with no prime factor ending in $3$ must contain:
at least one prime $\equiv 7 \pmod{10}$,
and at least one prime $\equiv 9 \pmod{10}$,

because only $7 \cdot 9 \equiv 3 \pmod{10}$.

Thus the remaining problem becomes a minimum-weight vertex cover on the bipartite graph:
left vertices: primes $\equiv 7 \pmod{10}$,
right vertices: primes $\equiv 9 \pmod{10}$,
edge $pq$ whenever $pq \le N$.

Using logarithmic weights $\log p$, the minimum vertex cover gives the minimum possible $\log f(N)$.

Checking against the supplied example:

$$\log f(2800)=715.019337207\ldots$$

which matches the problem statement.

For $N=10^6$, the computation gives:

$$\log f(10^6)=250591.44279227447\ldots$$

Rounded to six decimal places:

Answer: 250591.442792