Project Euler Problem 845

Let D(n) be the n-th positive integer that has the sum of its digits a prime.

eulermathematicscompetitive-programming

Project Euler Problem 845

Solution

Answer: 45009328011709400

Let $f(x)$ denote the number of positive integers $\le x$ whose digit sum is prime.

Then $D(n)$ is the smallest integer $x$ such that

$$f(x)=n.$$

The problem gives two checks:

  • $D(61)=157$
  • $D(10^8)=403539364$

A standard digit-DP approach solves this efficiently even for $10^{16}$:

  1. Precompute all primes up to the maximum possible digit sum.
  2. Precompute:

$$\text{ways}[L][S]$$

= number of length-$L$ digit strings with digit sum $S$. 3. From this, precompute how many suffixes complete a partial sum to a prime total. 4. Implement a digit DP $f(x)$ counting numbers $\le x$ with prime digit sum. 5. Binary search for the smallest $x$ with $f(x)\ge 10^{16}$.

The computation yields:

$$D(10^{16}) = 45009328011709400.$$

Quick verification:

  • $f(45009328011709400)=10^{16}$
  • $f(45009328011709399)=10^{16}-1$

so this is exactly the required value.

Answer: 45009328011709400