Problem 845: Prime Digit Sum
View on Project EulerProject Euler Problem 845 Solution
EulerSolve provides an optimized solution for Project Euler Problem 845, Prime Digit Sum, with C++, Python, Java, and a step-by-step mathematical explanation.
Problem Summary We seek the \(n\)-th positive integer whose decimal digit sum is prime. A direct scan would be far too slow for the real target, so the solution counts how many valid numbers lie in \([1,x]\), then finds the first \(x\) whose count reaches \(n\). Let \(s(x)\) be the base-10 digit sum of \(x\), and let \(\mathcal{P}\) denote the set of prime numbers. The central counting function is $$C(x)=\#\{1\le m\le x : s(m)\in\mathcal{P}\}.$$ Once \(C(x)\) can be evaluated quickly, the answer is simply the smallest \(x\) with \(C(x)\ge n\). Mathematical Approach The method is a digit dynamic program. Instead of enumerating every number up to \(x\), it counts possible suffixes by their digit sums and reuses those counts while scanning the decimal representation of \(x\). The implementations reserve tables for at most \(D=20\) decimal positions, so the largest relevant digit sum is \(S=9D=180\). Step 1: Count digit strings by length and sum For \(\ell\ge 0\) and \(0\le t\le S\), define $$W(\ell,t)=\#\{(d_1,\dots,d_\ell)\in\{0,\dots,9\}^{\ell}: d_1+\cdots+d_\ell=t\}.$$ Leading zeros are allowed. This matters because a string such as \(04\) represents the ordinary number \(4\), so the same table automatically covers shorter numbers when we later compare against a fixed-length bound....
Detailed mathematical approach
Problem Summary
We seek the \(n\)-th positive integer whose decimal digit sum is prime. A direct scan would be far too slow for the real target, so the solution counts how many valid numbers lie in \([1,x]\), then finds the first \(x\) whose count reaches \(n\).
Let \(s(x)\) be the base-10 digit sum of \(x\), and let \(\mathcal{P}\) denote the set of prime numbers. The central counting function is
$$C(x)=\#\{1\le m\le x : s(m)\in\mathcal{P}\}.$$
Once \(C(x)\) can be evaluated quickly, the answer is simply the smallest \(x\) with \(C(x)\ge n\).
Mathematical Approach
The method is a digit dynamic program. Instead of enumerating every number up to \(x\), it counts possible suffixes by their digit sums and reuses those counts while scanning the decimal representation of \(x\).
The implementations reserve tables for at most \(D=20\) decimal positions, so the largest relevant digit sum is \(S=9D=180\).
Step 1: Count digit strings by length and sum
For \(\ell\ge 0\) and \(0\le t\le S\), define
$$W(\ell,t)=\#\{(d_1,\dots,d_\ell)\in\{0,\dots,9\}^{\ell}: d_1+\cdots+d_\ell=t\}.$$
Leading zeros are allowed. This matters because a string such as \(04\) represents the ordinary number \(4\), so the same table automatically covers shorter numbers when we later compare against a fixed-length bound.
The initial conditions are
$$W(0,0)=1,\qquad W(0,t)=0\text{ for }t>0,$$
and the recurrence is
$$W(\ell,t)=\sum_{d=0}^{9} W(\ell-1,t-d),$$
with the convention that \(W(\ell,u)=0\) whenever \(u \lt 0\). After this table is built, we know how many tails of any remaining length realize any required digit sum.
Step 2: Convert those counts into prime-completing suffix counts
Suppose a prefix already contributes digit sum \(p\), and there are \(r\) digits still to choose. We need the number of tails that make the final total prime. Define
$$G(r,p)=\sum_{\substack{u\ge 0\\ p+u\in\mathcal{P}}} W(r,u).$$
Thus \(G(r,p)\) counts all length-\(r\) suffixes whose digit sum \(u\) turns the current prefix sum \(p\) into a prime total \(p+u\). This second table becomes the counting oracle used for every query.
Because the largest possible total is only \(180\), primality can be precomputed once by a small sieve and then reused for every state \((r,p)\).
Step 3: Evaluate \(C(x)\) digit by digit
Write the decimal expansion of \(x\) as \(x_0x_1\dots x_{k-1}\), and let
$$\sigma_i=x_0+x_1+\cdots+x_{i-1}$$
be the sum of the digits strictly before position \(i\), with \(\sigma_0=0\).
While scanning from left to right, position \(i\) offers two possibilities: follow the actual digit \(x_i\), or choose any smaller digit \(d \lt x_i\). If we choose a smaller digit, then the remaining \(k-1-i\) positions are completely free, so their contribution is exactly
$$G(k-1-i,\sigma_i+d).$$
Summing this over every position and every smaller digit yields all valid numbers strictly below \(x\). After the scan, we add one more if the digit sum of \(x\) itself is prime. In compact form,
$$C(x)=\sum_{i=0}^{k-1}\sum_{d=0}^{x_i-1} G(k-1-i,\sigma_i+d)+\varepsilon(x),$$
where \(\varepsilon(x)=1\) when \(s(x)\in\mathcal{P}\), and \(\varepsilon(x)=0\) otherwise.
Step 4: Why leading zeros handle shorter numbers automatically
If \(x\) has \(k\) digits, then every positive integer with fewer than \(k\) digits is still represented as a length-\(k\) string by padding it with leading zeros. For example, \(37\) is treated as \(037\) when compared against a 3-digit bound.
This removes the need for separate cases for 1-digit, 2-digit, and longer numbers. The number \(0\) causes no trouble, because its digit sum is \(0\), and \(0\notin\mathcal{P}\).
Step 5: Recover the \(n\)-th valid number by monotone search
The function \(C(x)\) is nondecreasing, because enlarging \([1,x]\) can only add more valid integers. Therefore the target value is
$$\min\{x\ge 1 : C(x)\ge n\}.$$
The implementations first grow an upper bound by repeated doubling until the count reaches \(n\). Once such a bound is found, ordinary binary search isolates the first \(x\) with \(C(x)\ge n\).
Worked Example: Why the 61st term is \(157\)
A useful checkpoint is that the 61st positive integer with prime digit sum is \(157\). The digit-DP explains this neatly.
First consider all numbers from \(0\) to \(99\). Using 2-digit strings with leading zeros, the prime digit sums are \(2,3,5,7,11,13,17\). The table \(W(2,t)\) gives
$$W(2,2)=3,\quad W(2,3)=4,\quad W(2,5)=6,\quad W(2,7)=8,\quad W(2,11)=8,\quad W(2,13)=6,\quad W(2,17)=2,$$
so
$$G(2,0)=3+4+6+8+8+6+2=37.$$
Thus exactly \(37\) numbers in \([1,99]\) have prime digit sum.
Now move to numbers below \(157\). Fix the hundreds digit as \(1\). For a tens digit smaller than \(5\), the current prefix sums are \(1,2,3,4,5\). The 1-digit suffix table gives
$$G(1,1)=4,\quad G(1,2)=5,\quad G(1,3)=4,\quad G(1,4)=4,\quad G(1,5)=4,$$
hence the block \(100\) to \(149\) contributes
$$4+5+4+4+4=21.$$
Finally, within \(150\) to \(156\), only \(151\) and \(155\) have prime digit sum, so this last partial block contributes \(2\). Therefore
$$C(156)=37+21+2=60.$$
Since \(1+5+7=13\) is prime, \(157\) itself is valid, giving
$$C(157)=61.$$
So the 61st term is indeed \(157\), exactly matching the checkpoint used by the implementations.
How the Code Works
The C++, Python, and Java implementations follow the same pipeline. They first precompute primality for every possible digit sum from \(0\) to \(180\). Next they build the table \(W(\ell,t)\) for all lengths up to \(20\), then build the suffix-completion table \(G(r,p)\).
For a query \(C(x)\), the implementation converts \(x\) to decimal, scans left to right, and whenever a smaller digit than the bound is possible at the current position, it adds the precomputed number of prime-completing tails. After the full scan, it checks whether the bound itself has prime digit sum and includes it if appropriate.
To obtain the \(n\)-th valid integer, the implementation repeatedly doubles an upper bound until enough valid numbers are covered, and then performs a standard binary search on that interval. No brute-force pass over all intermediate integers is needed.
Complexity Analysis
Let \(D\) be the maximum number of digits and \(S=9D\) the maximum digit sum. Building the prime table costs \(O(S\log\log S)\). Building \(W\) costs \(O(10DS)\). Building the suffix table \(G\) in the straightforward form used here costs \(O(DS^2)\), because each state \((r,p)\) scans all feasible tail sums.
One evaluation of \(C(x)\) costs \(O(10D)\): there are \(D\) positions and at most 10 candidate digits per position. The final search uses \(O(\log X)\) such evaluations, where \(X\) is the answer. Memory usage is \(O(DS)\). In these implementations, \(D=20\) and \(S=180\), so the constants are very small.
Footnotes and References
- Problem page: https://projecteuler.net/problem=845
- Digit sum: Wikipedia — Digit sum
- Dynamic programming: Wikipedia — Dynamic programming
- Prime number: Wikipedia — Prime number
- Binary search algorithm: Wikipedia — Binary search algorithm
Problem 845 source code
C++
#include <array>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <string>
using u64 = std::uint64_t;
using u128 = unsigned __int128;
static constexpr int kMaxLen = 20;
static constexpr int kMaxSum = 9 * kMaxLen;
struct DigitPrimeDP {
std::array<bool, kMaxSum + 1> is_prime{};
std::array<std::array<u128, kMaxSum + 1>, kMaxLen + 1> ways{};
std::array<std::array<u128, kMaxSum + 1>, kMaxLen + 1> good{};
DigitPrimeDP() {
sieve_primes();
build_ways();
build_good();
}
void sieve_primes() {
is_prime.fill(true);
is_prime[0] = false;
is_prime[1] = false;
for (int p = 2; p * p <= kMaxSum; ++p) {
if (!is_prime[p]) continue;
for (int x = p * p; x <= kMaxSum; x += p) is_prime[x] = false;
}
}
void build_ways() {
for (auto& row : ways) row.fill(0);
ways[0][0] = 1;
for (int len = 1; len <= kMaxLen; ++len) {
for (int s = 0; s <= 9 * (len - 1); ++s) {
u128 cur = ways[len - 1][s];
if (cur == 0) continue;
for (int d = 0; d <= 9; ++d) ways[len][s + d] += cur;
}
}
}
void build_good() {
for (auto& row : good) row.fill(0);
for (int rem = 0; rem <= kMaxLen; ++rem) {
for (int pref = 0; pref <= kMaxSum; ++pref) {
u128 cnt = 0;
for (int tail = 0; tail <= 9 * rem; ++tail) {
if (pref + tail <= kMaxSum && is_prime[pref + tail]) cnt += ways[rem][tail];
}
good[rem][pref] = cnt;
}
}
}
u128 count_upto(u64 x) const {
std::string s = std::to_string(x);
int sum = 0;
u128 ans = 0;
for (int i = 0; i < static_cast<int>(s.size()); ++i) {
int d = s[i] - '0';
int rem = static_cast<int>(s.size()) - i - 1;
for (int dig = 0; dig < d; ++dig) ans += good[rem][sum + dig];
sum += d;
}
if (is_prime[sum]) ++ans;
return ans;
}
};
static u64 nth_value(u64 n, const DigitPrimeDP& dp) {
u128 target = n;
u64 lo = 1;
u64 hi = 1;
while (dp.count_upto(hi) < target) hi <<= 1;
while (lo < hi) {
u64 mid = lo + (hi - lo) / 2;
if (dp.count_upto(mid) >= target) hi = mid;
else lo = mid + 1;
}
return lo;
}
int main() {
DigitPrimeDP dp;
assert(nth_value(61, dp) == 157ULL);
assert(nth_value(100'000'000ULL, dp) == 403'539'364ULL);
std::cout << nth_value(10'000'000'000'000'000ULL, dp) << '\n';
return 0;
}
Python
class DigitPrimeDP:
def __init__(self):
self.kMaxLen = 20
self.kMaxSum = 9 * self.kMaxLen
self.is_prime = [True] * (self.kMaxSum + 1)
self.ways = [[0] * (self.kMaxSum + 1) for _ in range(self.kMaxLen + 1)]
self.good = [[0] * (self.kMaxSum + 1) for _ in range(self.kMaxLen + 1)]
self.sieve_primes()
self.build_ways()
self.build_good()
def sieve_primes(self):
self.is_prime[0] = False
self.is_prime[1] = False
for p in range(2, int(self.kMaxSum**0.5) + 1):
if self.is_prime[p]:
for x in range(p * p, self.kMaxSum + 1, p):
self.is_prime[x] = False
def build_ways(self):
self.ways[0][0] = 1
for length in range(1, self.kMaxLen + 1):
for s in range(9 * (length - 1) + 1):
cur = self.ways[length - 1][s]
if cur == 0: continue
for d in range(10):
self.ways[length][s + d] += cur
def build_good(self):
for rem in range(self.kMaxLen + 1):
for pref in range(self.kMaxSum + 1):
cnt = 0
for tail in range(9 * rem + 1):
if pref + tail <= self.kMaxSum and self.is_prime[pref + tail]:
cnt += self.ways[rem][tail]
self.good[rem][pref] = cnt
def count_upto(self, x):
s = str(x)
ans = 0
total_sum = 0
for i, char in enumerate(s):
d = int(char)
rem = len(s) - i - 1
for dig in range(d):
ans += self.good[rem][total_sum + dig]
total_sum += d
if self.is_prime[total_sum]:
ans += 1
return ans
def nth_value(n, dp):
lo = 1
hi = 1
while dp.count_upto(hi) < n:
hi <<= 1
while lo < hi:
mid = lo + (hi - lo) // 2
if dp.count_upto(mid) >= n:
hi = mid
else:
lo = mid + 1
return lo
def solve():
dp = DigitPrimeDP()
ans = nth_value(10000000000000000, dp)
return str(ans)
if __name__ == "__main__":
print(solve())
Java
public class Euler845 {
static final int kMaxLen = 20;
static final int kMaxSum = 9 * kMaxLen;
static class DigitPrimeDP {
boolean[] isPrime;
long[][] ways;
long[][] good;
DigitPrimeDP() {
isPrime = new boolean[kMaxSum + 1];
ways = new long[kMaxLen + 1][kMaxSum + 1];
good = new long[kMaxLen + 1][kMaxSum + 1];
sievePrimes();
buildWays();
buildGood();
}
void sievePrimes() {
java.util.Arrays.fill(isPrime, true);
isPrime[0] = false;
isPrime[1] = false;
for (int p = 2; p * p <= kMaxSum; ++p) {
if (!isPrime[p])
continue;
for (int x = p * p; x <= kMaxSum; x += p)
isPrime[x] = false;
}
}
void buildWays() {
ways[0][0] = 1;
for (int len = 1; len <= kMaxLen; ++len) {
for (int s = 0; s <= 9 * (len - 1); ++s) {
long cur = ways[len - 1][s];
if (cur == 0)
continue;
for (int d = 0; d <= 9; ++d)
ways[len][s + d] += cur;
}
}
}
void buildGood() {
for (int rem = 0; rem <= kMaxLen; ++rem) {
for (int pref = 0; pref <= kMaxSum; ++pref) {
long cnt = 0;
for (int tail = 0; tail <= 9 * rem; ++tail) {
if (pref + tail <= kMaxSum && isPrime[pref + tail]) {
cnt += ways[rem][tail];
}
}
good[rem][pref] = cnt;
}
}
}
long countUpto(long x) {
String s = Long.toString(x);
int sum = 0;
long ans = 0;
for (int i = 0; i < s.length(); ++i) {
int d = s.charAt(i) - '0';
int rem = s.length() - i - 1;
for (int dig = 0; dig < d; ++dig) {
ans += good[rem][sum + dig];
}
sum += d;
}
if (isPrime[sum])
++ans;
return ans;
}
}
static long nthValue(long n, DigitPrimeDP dp) {
long lo = 1;
long hi = 1;
while (dp.countUpto(hi) < n)
hi <<= 1;
while (lo < hi) {
long mid = lo + (hi - lo) / 2;
if (dp.countUpto(mid) >= n)
hi = mid;
else
lo = mid + 1;
}
return lo;
}
public static String solve() {
DigitPrimeDP dp = new DigitPrimeDP();
return Long.toString(nthValue(10000000000000000L, dp));
}
public static void main(String[] args) {
System.out.println(solve());
}
}