Problem 685: Inverse Digit Sum II
View on Project EulerProject Euler Problem 685 Solution
EulerSolve provides an optimized solution for Project Euler Problem 685, Inverse Digit Sum II, with C++, Python, Java, and a step-by-step mathematical explanation.
Problem Summary For each pair \((s,m)\), let \(f(s,m)\) be the \(m\)-th positive integer whose decimal digits sum to \(s\), with numbers ordered in the usual increasing order. The target quantity is $$S(k)=\sum_{n=1}^{k} f(n^3,n^4)\pmod{10^9+7}.$$ For the full input range, both the digit sums and the occurrence ranks are far too large for brute force. The solution therefore counts how many admissible numbers lie in each length block, identifies the block containing the required rank, and then reconstructs the number digit by digit. Mathematical Approach The key simplification is to replace each digit by its deficit from \(9\). That turns the digit-sum constraint into a bounded composition problem, which can be counted exactly with inclusion-exclusion. Step 1: Turn the digit-sum condition into a bounded composition Suppose an \(\ell\)-digit number has decimal digits \(a_1,\dots,a_\ell\). Define deficits $$b_i=9-a_i.$$ Then every \(b_i\) lies in \(\{0,\dots,9\}\), and $$a_1+\cdots+a_\ell=s \iff b_1+\cdots+b_\ell=9\ell-s=: \Delta.$$ The first digit cannot be zero, so \(a_1\ge 1\), which means $$b_1\in\{0,\dots,8\}.$$ All remaining deficits may still range from \(0\) to \(9\). Therefore an \(\ell\)-digit number with digit sum \(s\) is equivalent to choosing \(b_1,\dots,b_\ell\) with one slightly tighter bound on the first coordinate....
Detailed mathematical approach
Problem Summary
For each pair \((s,m)\), let \(f(s,m)\) be the \(m\)-th positive integer whose decimal digits sum to \(s\), with numbers ordered in the usual increasing order. The target quantity is
$$S(k)=\sum_{n=1}^{k} f(n^3,n^4)\pmod{10^9+7}.$$
For the full input range, both the digit sums and the occurrence ranks are far too large for brute force. The solution therefore counts how many admissible numbers lie in each length block, identifies the block containing the required rank, and then reconstructs the number digit by digit.
Mathematical Approach
The key simplification is to replace each digit by its deficit from \(9\). That turns the digit-sum constraint into a bounded composition problem, which can be counted exactly with inclusion-exclusion.
Step 1: Turn the digit-sum condition into a bounded composition
Suppose an \(\ell\)-digit number has decimal digits \(a_1,\dots,a_\ell\). Define deficits
$$b_i=9-a_i.$$
Then every \(b_i\) lies in \(\{0,\dots,9\}\), and
$$a_1+\cdots+a_\ell=s \iff b_1+\cdots+b_\ell=9\ell-s=: \Delta.$$
The first digit cannot be zero, so \(a_1\ge 1\), which means
$$b_1\in\{0,\dots,8\}.$$
All remaining deficits may still range from \(0\) to \(9\). Therefore an \(\ell\)-digit number with digit sum \(s\) is equivalent to choosing \(b_1,\dots,b_\ell\) with one slightly tighter bound on the first coordinate.
The smallest feasible length is
$$\ell_{\min}=\left\lceil \frac{s}{9}\right\rceil,$$
because even the largest possible \(\ell\)-digit number contributes only \(9\ell\) to the digit sum.
Step 2: Count bounded suffixes by inclusion-exclusion
Let \(A(d,t)\) denote the number of length-\(d\) strings over \(\{0,\dots,9\}\) whose digits sum to \(t\). Without the upper bound \(9\), stars and bars gives \(\binom{d+t-1}{t}\). To enforce the upper bound, subtract cases where one or more coordinates are at least \(10\). The resulting exact formula is
$$A(d,t)=\sum_{j=0}^{\lfloor t/10\rfloor} (-1)^j \binom{d}{j}\binom{d+t-10j-1}{t-10j}.$$
This is the counting engine used throughout the algorithm. The values can be enormous, so the implementation evaluates them with arbitrary-precision integers instead of reducing them modulo \(10^9+7\).
Step 3: Count numbers of a fixed length
Let \(C_\ell(s)\) be the number of positive \(\ell\)-digit integers whose digit sum is \(s\). Once the first deficit \(b_1\) is chosen, the remaining \(\ell-1\) positions form an unrestricted bounded composition. Hence
$$C_\ell(s)=\sum_{b_1=0}^{\min(8,\Delta)} A(\ell-1,\Delta-b_1), \qquad \Delta=9\ell-s.$$
Numbers with fewer digits are always smaller than numbers with more digits, so the desired occurrence rank \(m\) lies in the first length \(\ell\) satisfying
$$\sum_{t=\ell_{\min}}^{\ell} C_t(s)\ge m.$$
After that, the rank inside the chosen block is simply \(m\) minus the total contribution of all shorter lengths.
Step 4: Unrank inside the chosen length
Now suppose \(r\) positions remain to be filled and the remaining deficit to distribute is \(D\). If the next digit has deficit \(b\), then the number of valid completions is
$$A(r-1,D-b).$$
To preserve increasing numeric order, candidate digits are tested from smallest to largest. In terms of deficits, that means testing from largest to smallest. Whenever the target rank exceeds the size of a whole block, that block is skipped and its size is subtracted from the rank. The first block not skipped determines the next digit.
If \(D=0\), all remaining digits must be \(9\). More generally, the lexicographically last block is the block beginning with a run of \(9\)s. If \(q\) leading \(9\)s are fixed while \(r\) positions remain, then the surviving suffix count is
$$A(r-q,D),$$
so the number of admissible suffixes that come before that block is
$$A(r,D)-A(r-q,D).$$
This monotone quantity is why the implementation can binary-search the length of a leading run of \(9\)s and append that run in one jump.
Worked Example: \(f(10,10)=109\)
The smallest feasible length is \(\lceil 10/9\rceil=2\). The two-digit numbers with digit sum \(10\) are
$$19,28,37,46,55,64,73,82,91,$$
so \(C_2(10)=9\). Therefore the 10th occurrence does not lie in the two-digit block; it is the first element of the three-digit block.
For \(\ell=3\), the deficit is
$$\Delta=27-10=17.$$
Trying first digit \(1\) means first deficit \(8\), leaving deficit \(9\) across the last two digits. The number of completions is
$$A(2,9)=10,$$
so rank \(1\) already lies in that first block. Thus the leading digit is \(1\). Among the remaining two-digit suffixes with digit sum \(9\), the smallest is \(09\), so the first three-digit number with total digit sum \(10\) is \(109\). Hence
$$f(10,10)=109.$$
How the Code Works
The C++, Python, and Java implementations all follow the same mathematical pipeline. First, they evaluate exact combinatorial counts for bounded digit sums using arbitrary-precision integers, because the intermediate ranks are much larger than machine integers. Second, they accumulate length counts until the target occurrence rank enters one specific length block. Third, they reconstruct the required number digit by digit by repeatedly asking how many completions each candidate next digit allows.
The number itself is never materialized as a gigantic decimal integer. Instead, the implementation keeps the constructed value modulo \(10^9+7\) and updates it through the recurrence \(x\mapsto 10x+d\). When an entire run of \(9\)s is known at once, it appends that run with
$$x \mapsto x\cdot 10^q + (10^q-1)\pmod{10^9+7}.$$
Finally, the outer summation evaluates the procedure for each \(n\) with \(s=n^3\) and occurrence rank \(n^4\). The C++ implementation optionally partitions that outer loop across threads, while the Python and Java implementations use the same logic serially.
Complexity Analysis
For one query \(f(s,m)\), suppose the selected number has length \(\ell\). The length-location phase evaluates \(C_t(s)\) for consecutive lengths \(t\) from \(\lceil s/9\rceil\) up to \(\ell\). The unranking phase performs \(O(\ell)\) digit decisions, with a constant number of bounded-composition counts at each step and an occasional \(O(\log \ell)\) binary search when jumping across a run of \(9\)s.
The dominant arithmetic cost comes from the inclusion-exclusion formula for \(A(d,t)\), which contains \(O(\lfloor t/10\rfloor+1)\) terms and uses big-integer binomial coefficients. Memory usage is modest: apart from the big integers storing counts and ranks, only a small amount of state is maintained. In practice this is fast enough for the full sum up to \(k=10^4\), especially when the outer loop is parallelized.
Footnotes and References
- Problem page: https://projecteuler.net/problem=685
- Digit sum: Wikipedia - Digit sum
- Inclusion-exclusion principle: Wikipedia - Inclusion-exclusion principle
- Stars and bars: Wikipedia - Stars and bars
- Lexicographic order: Wikipedia - Lexicographic order
Problem 685 source code
C++
#include <algorithm>
#include <cstdint>
#include <cstdlib>
#include <iostream>
#include <limits>
#include <stdexcept>
#include <string>
#include <thread>
#include <vector>
#include <boost/multiprecision/cpp_int.hpp>
namespace {
using boost::multiprecision::cpp_int;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using u128 = unsigned __int128;
constexpr i64 kMod = 1'000'000'007LL;
constexpr u64 kDefaultK = 10'000ULL;
struct Options {
u64 k = kDefaultK;
bool run_checkpoints = true;
bool allow_multithreading = true;
unsigned requested_threads = 0U;
};
u64 cube_u64(const u64 n) {
const u128 x = static_cast<u128>(n);
return static_cast<u64>(x * x * x);
}
u64 fourth_u64(const u64 n) {
const u128 x = static_cast<u128>(n);
return static_cast<u64>(x * x * x * x);
}
cpp_int binom_small_k(u64 n, u64 k) {
if (k > n) {
return 0;
}
if (k > n - k) {
k = n - k;
}
cpp_int out = 1;
for (u64 i = 1; i <= k; ++i) {
out *= (n - k + i);
out /= i;
}
return out;
}
cpp_int count_0_to_9(const u64 digits, const u64 sum) {
if (sum > 9ULL * digits) {
return 0;
}
if (digits == 0ULL) {
return (sum == 0ULL) ? cpp_int(1) : cpp_int(0);
}
cpp_int total = 0;
const u64 max_j = sum / 10ULL;
for (u64 j = 0; j <= max_j; ++j) {
const u64 remain = sum - 10ULL * j;
cpp_int term = binom_small_k(digits, j);
term *= binom_small_k(digits + remain - 1ULL, remain);
if ((j & 1ULL) == 0ULL) {
total += term;
} else {
total -= term;
}
}
return total;
}
cpp_int count_len_with_sum(const u64 len, const u64 sum) {
if (len == 0ULL || sum == 0ULL) {
return 0;
}
if (sum > 9ULL * len) {
return 0;
}
const u64 deficit = 9ULL * len - sum;
const u64 max_first_deficit = std::min<u64>(8ULL, deficit);
cpp_int out = 0;
for (u64 b0 = 0ULL; b0 <= max_first_deficit; ++b0) {
out += count_0_to_9(len - 1ULL, deficit - b0);
}
return out;
}
i64 mod_pow10(u64 exp) {
i64 base = 10LL;
i64 out = 1LL;
while (exp > 0ULL) {
if ((exp & 1ULL) != 0ULL) {
out = static_cast<i64>((static_cast<__int128>(out) * base) % kMod);
}
base = static_cast<i64>((static_cast<__int128>(base) * base) % kMod);
exp >>= 1ULL;
}
return out;
}
void append_digit_mod(i64& value_mod, const int digit) {
value_mod = static_cast<i64>((static_cast<__int128>(value_mod) * 10LL + digit) % kMod);
}
void append_nines_mod(i64& value_mod, const u64 count) {
if (count == 0ULL) {
return;
}
const i64 p10 = mod_pow10(count);
// 9 repeated count times = 10^count - 1.
value_mod = static_cast<i64>(
(static_cast<__int128>(value_mod) * p10 + p10 - 1LL + kMod) % kMod);
}
struct RankedNumber {
u64 len = 0ULL;
cpp_int rank_inside_len = 0;
};
RankedNumber locate_length_and_rank(const u64 digit_sum, const u64 occurrence_rank) {
const cpp_int target = occurrence_rank;
u64 len = (digit_sum + 8ULL) / 9ULL;
cpp_int prefix_count = 0;
while (true) {
const cpp_int cnt_here = count_len_with_sum(len, digit_sum);
if (prefix_count + cnt_here >= target) {
return RankedNumber{len, target - prefix_count};
}
prefix_count += cnt_here;
++len;
}
}
i64 unrank_mod(const u64 len, const u64 digit_sum, cpp_int rank_inside_len) {
const u64 initial_deficit = 9ULL * len - digit_sum;
i64 value_mod = 0LL;
u64 remaining_digits = len;
u64 remaining_deficit = initial_deficit;
{
const u64 max_deficit_here = std::min<u64>(8ULL, remaining_deficit);
bool chosen = false;
for (int deficit_digit = static_cast<int>(max_deficit_here); deficit_digit >= 0;
--deficit_digit) {
const cpp_int cnt =
count_0_to_9(remaining_digits - 1ULL, remaining_deficit - deficit_digit);
if (rank_inside_len > cnt) {
rank_inside_len -= cnt;
continue;
}
append_digit_mod(value_mod, 9 - deficit_digit);
remaining_deficit -= static_cast<u64>(deficit_digit);
--remaining_digits;
chosen = true;
break;
}
if (!chosen) {
throw std::runtime_error("Failed to choose the first digit during unranking.");
}
}
while (remaining_digits > 0ULL) {
if (remaining_deficit == 0ULL) {
append_nines_mod(value_mod, remaining_digits);
break;
}
const cpp_int total_here = count_0_to_9(remaining_digits, remaining_deficit);
const cpp_int zero_branch = count_0_to_9(remaining_digits - 1ULL, remaining_deficit);
const cpp_int nonzero_prefix = total_here - zero_branch;
if (rank_inside_len > nonzero_prefix) {
u64 low = 1ULL;
u64 high = remaining_digits;
u64 best = 1ULL;
while (low <= high) {
const u64 mid = low + ((high - low) >> 1ULL);
const cpp_int suffix = count_0_to_9(remaining_digits - mid, remaining_deficit);
const cpp_int removed = total_here - suffix;
if (rank_inside_len > removed) {
best = mid;
low = mid + 1ULL;
} else {
if (mid == 0ULL) {
break;
}
high = mid - 1ULL;
}
}
const cpp_int suffix = count_0_to_9(remaining_digits - best, remaining_deficit);
const cpp_int removed = total_here - suffix;
rank_inside_len -= removed;
append_nines_mod(value_mod, best);
remaining_digits -= best;
continue;
}
bool chosen = false;
const u64 max_deficit_here = std::min<u64>(9ULL, remaining_deficit);
for (int deficit_digit = static_cast<int>(max_deficit_here); deficit_digit >= 0;
--deficit_digit) {
const cpp_int cnt =
count_0_to_9(remaining_digits - 1ULL, remaining_deficit - deficit_digit);
if (rank_inside_len > cnt) {
rank_inside_len -= cnt;
continue;
}
append_digit_mod(value_mod, 9 - deficit_digit);
remaining_deficit -= static_cast<u64>(deficit_digit);
--remaining_digits;
chosen = true;
break;
}
if (!chosen) {
throw std::runtime_error("Failed to choose a digit during unranking.");
}
}
return value_mod;
}
i64 f_mod(const u64 digit_sum, const u64 occurrence_rank) {
const RankedNumber located = locate_length_and_rank(digit_sum, occurrence_rank);
return unrank_mod(located.len, digit_sum, located.rank_inside_len);
}
int digit_sum_small(u64 x) {
int out = 0;
while (x > 0ULL) {
out += static_cast<int>(x % 10ULL);
x /= 10ULL;
}
return out;
}
u64 brute_f_small(const int target_sum, const int target_occurrence) {
int seen = 0;
for (u64 x = 1ULL;; ++x) {
if (digit_sum_small(x) != target_sum) {
continue;
}
++seen;
if (seen == target_occurrence) {
return x;
}
}
}
unsigned choose_thread_count(const bool allow_multithreading,
const unsigned requested_threads,
const u64 k) {
if (!allow_multithreading || k <= 1ULL) {
return 1U;
}
unsigned threads = requested_threads;
if (threads == 0U) {
threads = std::thread::hardware_concurrency();
if (threads == 0U) {
threads = 1U;
}
}
return std::max(1U, std::min<unsigned>(threads, static_cast<unsigned>(k)));
}
i64 solve_S_mod(const u64 k, const unsigned threads) {
if (k == 0ULL) {
return 0LL;
}
if (threads <= 1U) {
i64 total = 0LL;
for (u64 n = 1ULL; n <= k; ++n) {
const u64 s = cube_u64(n);
const u64 m = fourth_u64(n);
total += f_mod(s, m);
if (total >= kMod) {
total -= kMod;
}
}
return total;
}
std::vector<i64> partial(threads, 0LL);
std::vector<std::thread> pool;
pool.reserve(threads);
for (unsigned tid = 0U; tid < threads; ++tid) {
const u64 begin = 1ULL + (k * tid) / threads;
const u64 end = (k * (tid + 1U)) / threads;
pool.emplace_back([&, tid, begin, end]() {
i64 local = 0LL;
for (u64 n = begin; n <= end; ++n) {
const u64 s = cube_u64(n);
const u64 m = fourth_u64(n);
local += f_mod(s, m);
if (local >= kMod) {
local -= kMod;
}
}
partial[tid] = local;
});
}
for (std::thread& th : pool) {
th.join();
}
i64 total = 0LL;
for (const i64 part : partial) {
total += part;
total %= kMod;
}
return total;
}
bool parse_u64(const std::string& s, u64& out) {
if (s.empty()) {
return false;
}
u64 value = 0ULL;
for (const char c : s) {
if (c < '0' || c > '9') {
return false;
}
const u64 digit = static_cast<u64>(c - '0');
if (value > (std::numeric_limits<u64>::max() - digit) / 10ULL) {
return false;
}
value = value * 10ULL + digit;
}
out = value;
return true;
}
bool parse_unsigned(const std::string& s, unsigned& out) {
u64 parsed = 0ULL;
if (!parse_u64(s, parsed)) {
return false;
}
if (parsed > static_cast<u64>(std::numeric_limits<unsigned>::max())) {
return false;
}
out = static_cast<unsigned>(parsed);
return true;
}
bool parse_u64_after_prefix(const std::string& arg, const char* prefix, u64& out) {
const std::string p(prefix);
if (arg.rfind(p, 0U) != 0U) {
return false;
}
return parse_u64(arg.substr(p.size()), out);
}
bool parse_unsigned_after_prefix(const std::string& arg,
const char* prefix,
unsigned& out) {
const std::string p(prefix);
if (arg.rfind(p, 0U) != 0U) {
return false;
}
return parse_unsigned(arg.substr(p.size()), out);
}
bool parse_arguments(const int argc, char** argv, Options& options) {
for (int i = 1; i < argc; ++i) {
const std::string arg(argv[i]);
if (arg == "--skip-checkpoints") {
options.run_checkpoints = false;
continue;
}
if (arg == "--single-thread") {
options.allow_multithreading = false;
continue;
}
u64 parsed_k = 0ULL;
if (parse_u64_after_prefix(arg, "--k=", parsed_k)) {
options.k = parsed_k;
continue;
}
unsigned parsed_threads = 0U;
if (parse_unsigned_after_prefix(arg, "--threads=", parsed_threads)) {
options.requested_threads = parsed_threads;
continue;
}
std::cerr << "Unknown argument: " << arg << '\n';
return false;
}
return true;
}
bool run_checkpoints(const unsigned threads) {
struct FCheckpoint {
u64 sum;
u64 occ;
u64 expected;
};
const std::vector<FCheckpoint> f_checks = {
{10ULL, 1ULL, 19ULL},
{10ULL, 10ULL, 109ULL},
{10ULL, 100ULL, 1423ULL},
};
for (const FCheckpoint cp : f_checks) {
const u64 brute = brute_f_small(static_cast<int>(cp.sum), static_cast<int>(cp.occ));
if (brute != cp.expected) {
std::cerr << "Internal brute checkpoint mismatch for f(" << cp.sum << ',' << cp.occ
<< "): expected " << cp.expected << ", brute got " << brute << "\n";
return false;
}
const i64 got_mod = f_mod(cp.sum, cp.occ);
if (got_mod != static_cast<i64>(cp.expected % kMod)) {
std::cerr << "f checkpoint failed for f(" << cp.sum << ',' << cp.occ << "): expected "
<< cp.expected << ", got mod value " << got_mod << "\n";
return false;
}
}
const i64 s3 = solve_S_mod(3ULL, 1U);
if (s3 != 7128LL) {
std::cerr << "S(3) checkpoint failed: expected 7128, got " << s3 << "\n";
return false;
}
const i64 s10 = solve_S_mod(10ULL, 1U);
if (s10 != 32'287'064LL) {
std::cerr << "S(10) checkpoint failed: expected 32287064, got " << s10 << "\n";
return false;
}
if (threads > 1U) {
const i64 single = solve_S_mod(120ULL, 1U);
const i64 multi = solve_S_mod(120ULL, threads);
if (single != multi) {
std::cerr << "Thread consistency checkpoint failed: single=" << single
<< ", multi=" << multi << "\n";
return false;
}
}
std::cout << "All checkpoints passed.\n";
return true;
}
} // namespace
int main(int argc, char** argv) {
Options options;
if (!parse_arguments(argc, argv, options)) {
return 1;
}
const unsigned threads =
choose_thread_count(options.allow_multithreading, options.requested_threads, options.k);
if (options.run_checkpoints && !run_checkpoints(threads)) {
return 1;
}
const i64 answer = solve_S_mod(options.k, threads);
std::cout << answer << '\n';
return 0;
}
Python
def binom_small(n, k):
if k < 0 or k > n: return 0
if k > n - k: k = n - k
out = 1
for i in range(1, k + 1):
out = out * (n - k + i) // i
return out
def count_0_to_9(digits, sum_val):
if sum_val > 9 * digits: return 0
if digits == 0: return 1 if sum_val == 0 else 0
total = 0
max_j = sum_val // 10
for j in range(max_j + 1):
remain = sum_val - 10 * j
term = binom_small(digits, j) * binom_small(digits + remain - 1, remain)
if j % 2 == 0:
total += term
else:
total -= term
return total
def count_len_with_sum(length, sum_val):
if length == 0 or sum_val == 0: return 0
if sum_val > 9 * length: return 0
deficit = 9 * length - sum_val
max_first_deficit = min(8, deficit)
out = 0
for b0 in range(max_first_deficit + 1):
out += count_0_to_9(length - 1, deficit - b0)
return out
MOD = 1000000007
def mod_pow10(exp):
return pow(10, exp, MOD)
def append_digit_mod(value_mod, digit):
return (value_mod * 10 + digit) % MOD
def append_nines_mod(value_mod, count):
if count == 0: return value_mod
p10 = mod_pow10(count)
return (value_mod * p10 + p10 - 1) % MOD
def locate_length_and_rank(digit_sum, occurrence_rank):
target = occurrence_rank
length = (digit_sum + 8) // 9
prefix_count = 0
while True:
cnt_here = count_len_with_sum(length, digit_sum)
if prefix_count + cnt_here >= target:
return length, target - prefix_count
prefix_count += cnt_here
length += 1
def unrank_mod(length, digit_sum, rank_inside_len):
initial_deficit = 9 * length - digit_sum
value_mod = 0
remaining_digits = length
remaining_deficit = initial_deficit
max_deficit_here = min(8, remaining_deficit)
for deficit_digit in range(max_deficit_here, -1, -1):
cnt = count_0_to_9(remaining_digits - 1, remaining_deficit - deficit_digit)
if rank_inside_len > cnt:
rank_inside_len -= cnt
continue
value_mod = append_digit_mod(value_mod, 9 - deficit_digit)
remaining_deficit -= deficit_digit
remaining_digits -= 1
break
while remaining_digits > 0:
if remaining_deficit == 0:
value_mod = append_nines_mod(value_mod, remaining_digits)
break
total_here = count_0_to_9(remaining_digits, remaining_deficit)
zero_branch = count_0_to_9(remaining_digits - 1, remaining_deficit)
nonzero_prefix = total_here - zero_branch
if rank_inside_len > nonzero_prefix:
low = 1
high = remaining_digits
best = 1
while low <= high:
mid = low + ((high - low) >> 1)
suffix = count_0_to_9(remaining_digits - mid, remaining_deficit)
removed = total_here - suffix
if rank_inside_len > removed:
best = mid
low = mid + 1
else:
if mid == 0: break
high = mid - 1
suffix = count_0_to_9(remaining_digits - best, remaining_deficit)
removed = total_here - suffix
rank_inside_len -= removed
value_mod = append_nines_mod(value_mod, best)
remaining_digits -= best
continue
max_deficit_here = min(9, remaining_deficit)
for deficit_digit in range(max_deficit_here, -1, -1):
cnt = count_0_to_9(remaining_digits - 1, remaining_deficit - deficit_digit)
if rank_inside_len > cnt:
rank_inside_len -= cnt
continue
value_mod = append_digit_mod(value_mod, 9 - deficit_digit)
remaining_deficit -= deficit_digit
remaining_digits -= 1
break
return value_mod
def f_mod(digit_sum, occurrence_rank):
length, rank_inside_len = locate_length_and_rank(digit_sum, occurrence_rank)
return unrank_mod(length, digit_sum, rank_inside_len)
def solve():
k = 10000
ans = 0
for n in range(1, k + 1):
s = n * n * n
m = s * n
ans = (ans + f_mod(s, m)) % MOD
return str(ans)
if __name__ == '__main__':
print(solve())
Java
import java.math.BigInteger;
public class Euler685 {
static final long MOD = 1000000007L;
static BigInteger binomSmallK(long n, long k) {
if (k < 0 || k > n)
return BigInteger.ZERO;
if (k > n - k)
k = n - k;
BigInteger out = BigInteger.ONE;
for (long i = 1; i <= k; ++i) {
out = out.multiply(BigInteger.valueOf(n - k + i)).divide(BigInteger.valueOf(i));
}
return out;
}
static BigInteger count0To9(long digits, long sum) {
if (sum > 9 * digits)
return BigInteger.ZERO;
if (digits == 0)
return sum == 0 ? BigInteger.ONE : BigInteger.ZERO;
BigInteger total = BigInteger.ZERO;
long maxJ = sum / 10;
for (long j = 0; j <= maxJ; ++j) {
long remain = sum - 10 * j;
BigInteger term = binomSmallK(digits, j).multiply(binomSmallK(digits + remain - 1, remain));
if ((j & 1) == 0) {
total = total.add(term);
} else {
total = total.subtract(term);
}
}
return total;
}
static BigInteger countLenWithSum(long len, long sum) {
if (len == 0 || sum == 0)
return BigInteger.ZERO;
if (sum > 9 * len)
return BigInteger.ZERO;
long deficit = 9 * len - sum;
long maxFirstDeficit = Math.min(8L, deficit);
BigInteger out = BigInteger.ZERO;
for (long b0 = 0; b0 <= maxFirstDeficit; ++b0) {
out = out.add(count0To9(len - 1, deficit - b0));
}
return out;
}
static long modPow10(long exp) {
long base = 10;
long out = 1;
while (exp > 0) {
if ((exp & 1) != 0)
out = (out * base) % MOD;
base = (base * base) % MOD;
exp >>= 1;
}
return out;
}
static long appendDigitMod(long valueMod, int digit) {
return (valueMod * 10 + digit) % MOD;
}
static long appendNinesMod(long valueMod, long count) {
if (count == 0)
return valueMod;
long p10 = modPow10(count);
return (valueMod * p10 + p10 - 1 + MOD) % MOD;
}
static class RankedNumber {
long len;
BigInteger rankInside;
}
static RankedNumber locateLengthAndRank(long digitSum, long occurrenceRank) {
BigInteger target = BigInteger.valueOf(occurrenceRank);
long len = (digitSum + 8) / 9;
BigInteger prefixCount = BigInteger.ZERO;
while (true) {
BigInteger cntHere = countLenWithSum(len, digitSum);
if (prefixCount.add(cntHere).compareTo(target) >= 0) {
RankedNumber rn = new RankedNumber();
rn.len = len;
rn.rankInside = target.subtract(prefixCount);
return rn;
}
prefixCount = prefixCount.add(cntHere);
len++;
}
}
static long unrankMod(long len, long digitSum, BigInteger rankInsideLen) {
long initialDeficit = 9 * len - digitSum;
long valueMod = 0;
long remainingDigits = len;
long remainingDeficit = initialDeficit;
long maxDeficitHere = Math.min(8L, remainingDeficit);
for (int deficitDigit = (int) maxDeficitHere; deficitDigit >= 0; --deficitDigit) {
BigInteger cnt = count0To9(remainingDigits - 1, remainingDeficit - deficitDigit);
if (rankInsideLen.compareTo(cnt) > 0) {
rankInsideLen = rankInsideLen.subtract(cnt);
continue;
}
valueMod = appendDigitMod(valueMod, 9 - deficitDigit);
remainingDeficit -= deficitDigit;
remainingDigits--;
break;
}
while (remainingDigits > 0) {
if (remainingDeficit == 0) {
valueMod = appendNinesMod(valueMod, remainingDigits);
break;
}
BigInteger totalHere = count0To9(remainingDigits, remainingDeficit);
BigInteger zeroBranch = count0To9(remainingDigits - 1, remainingDeficit);
BigInteger nonzeroPrefix = totalHere.subtract(zeroBranch);
if (rankInsideLen.compareTo(nonzeroPrefix) > 0) {
long low = 1;
long high = remainingDigits;
long best = 1;
while (low <= high) {
long mid = low + ((high - low) >> 1);
BigInteger suffix = count0To9(remainingDigits - mid, remainingDeficit);
BigInteger removed = totalHere.subtract(suffix);
if (rankInsideLen.compareTo(removed) > 0) {
best = mid;
low = mid + 1;
} else {
if (mid == 0)
break;
high = mid - 1;
}
}
BigInteger suffix = count0To9(remainingDigits - best, remainingDeficit);
BigInteger removed = totalHere.subtract(suffix);
rankInsideLen = rankInsideLen.subtract(removed);
valueMod = appendNinesMod(valueMod, best);
remainingDigits -= best;
continue;
}
long maxDefHere = Math.min(9L, remainingDeficit);
for (int deficitDigit = (int) maxDefHere; deficitDigit >= 0; --deficitDigit) {
BigInteger cnt = count0To9(remainingDigits - 1, remainingDeficit - deficitDigit);
if (rankInsideLen.compareTo(cnt) > 0) {
rankInsideLen = rankInsideLen.subtract(cnt);
continue;
}
valueMod = appendDigitMod(valueMod, 9 - deficitDigit);
remainingDeficit -= deficitDigit;
remainingDigits--;
break;
}
}
return valueMod;
}
static long fMod(long digitSum, long occurrenceRank) {
RankedNumber req = locateLengthAndRank(digitSum, occurrenceRank);
return unrankMod(req.len, digitSum, req.rankInside);
}
public static String solve() {
long k = 10000;
long mod = 1000000007;
long ans = 0;
for (long n = 1; n <= k; ++n) {
long s = n * n * n;
long m = n * s;
ans = (ans + fMod(s, m)) % mod;
}
return Long.toString(ans);
}
public static void main(String[] args) {
System.out.println(solve());
}
}