Detailed mathematical approach

Problem Summary

A very odd number, as encoded by the implementations, is a positive integer divisible by \(105\) whose decimal expansion uses each of the five odd digits \(1,3,5,7,9\) a positive odd number of times. The problem asks for the \(10^{16}\)-th such number in increasing numerical order.

Direct enumeration is hopeless. Even after the divisibility filters, the search space contains huge blocks of repeated-digit permutations, and the target index is far beyond what brute force could reach. The successful approach is to work with digit-count vectors, separate the divisibility conditions, count multiset permutations by their remainder modulo \(7\), and then reconstruct the answer digit by digit in lexicographic order.

Mathematical Approach

The key point is that the value of a candidate number depends on two different kinds of data: how many times each odd digit appears, and in which order those digits are arranged. The code treats those two layers separately.

Odd multiplicities become a count-vector problem

For a fixed length \(L\), write

$c=(c_1,c_3,c_5,c_7,c_9),$

where \(c_d\) is the number of occurrences of digit \(d\). Every component must be a positive odd integer, so we may write \(c_d=2a_d+1\) with \(a_d\ge 0\). Therefore

$L=c_1+c_3+c_5+c_7+c_9=5+2(a_1+a_3+a_5+a_7+a_9).$

Immediately, every valid length is odd and at least \(5\). For a chosen length, the problem first reduces to listing all possible count vectors \(c\). Since all digits are nonzero, there is no leading-zero complication: within a fixed length, numerical order is exactly lexicographic order on the digit strings.

The divisibility conditions separate cleanly

Once a count vector \(c\) is fixed, divisibility by \(3\) depends only on the digit sum:

$1c_1+3c_3+5c_5+7c_7+9c_9\equiv 0 \pmod 3.$

No permutation can change that sum, so this is an early filter on the vector itself.

Divisibility by \(5\) is even more rigid. Because only odd digits are allowed, the last digit must be \(5\). Hence \(c_5\ge 1\), and after reserving the final digit we are left with the shorter multiset

$c'=(c_1,c_3,c_5-1,c_7,c_9).$

If the whole number is written as \(10P+5\), then divisibility by \(7\) becomes

$10P+5\equiv 0 \pmod 7.$

Since \(10\equiv 3 \pmod 7\) and \(3^{-1}\equiv 5 \pmod 7\), this is equivalent to

$P\equiv 3 \pmod 7.$

So for each admissible count vector, the counting problem is exact and finite: how many distinct permutations of the multiset \(c'\) have remainder \(3\) modulo \(7\)?

Remainder DP on multiset states

For any nonnegative state

$u=(u_1,u_3,u_5,u_7,u_9),$

define \(R_u[r]\) to be the number of distinct digit strings using exactly those counts and having value congruent to \(r\pmod 7\). The empty state is the base case:

$R_{(0,0,0,0,0)}[0]=1,\qquad R_{(0,0,0,0,0)}[r]=0 \text{ for } r\ne 0.$

If \(|u|=u_1+u_3+u_5+u_7+u_9=m\) and we place digit \(d\) as the most significant digit of the remaining block, then the rest of the block has length \(m-1\), so its contribution is shifted by a factor \(10^{m-1}\). This gives the transition

$R_u\bigl((d\cdot 10^{m-1}+r)\bmod 7\bigr)\;{+}{=}\;R_{u-e_d}[r],$

where \(e_d\) subtracts one copy of digit \(d\). Memoization makes this effective because the same count state appears repeatedly while scanning many candidate vectors and many suffixes during reconstruction.

Worked example: why the first valid length is \(7\)

Length \(5\) would force one copy of each digit \(1,3,5,7,9\). Their sum is \(25\), which is not divisible by \(3\), so no length-\(5\) number can work.

The smallest possible length is therefore \(7\). To keep the number as small as possible, the first count vector to test is

$c=(3,1,1,1,1),$

meaning three \(1\)'s and one copy of each of \(3,5,7,9\). Its digit sum is

$3\cdot 1+3+5+7+9=27,$

so the divisibility-by-\(3\) condition is satisfied. Reserving the last digit \(5\) leaves the multiset \(\{1,1,1,3,7,9\}\). We need the prefix \(P\) to satisfy \(P\equiv 3\pmod 7\). Among the lexicographically ordered distinct permutations of that multiset, the first one with remainder \(3\) is

$P=111793.$

Hence the smallest very odd number is

$1117935,$

which indeed is divisible by \(105\). This is exactly the first validation example used by the implementations.

Rank selection is done left to right

After counting how many valid numbers exist for each odd length, we locate the unique length block containing the target index. Inside that block, the answer is built digit by digit.

Suppose a prefix has already been fixed, and let \(\rho\) be its contribution modulo \(7\) in the full length-\(L\) decimal number. If the remaining middle block is the integer \(S\), then the unfinished number has the form

$\rho + 10S + 5 \pmod 7.$

Therefore the suffix must satisfy

$10S\equiv -(\rho+5)\pmod 7,$

or equivalently

$S\equiv -(\rho+5)\cdot 5 \pmod 7.$

For each tentative next digit, the code subtracts the already used digits from every admissible total count vector, asks the DP table how many suffix permutations hit that required remainder, and sums those completion counts. The first digit whose completion count contains the target rank is chosen. Because digits are tested in increasing order, this is exactly lexicographic rank selection within the correct length.

How the Code Works

Counting one length block at a time

The implementations iterate through odd lengths \(L=5,7,9,\dots\). For each \(L\), they generate every count vector with positive odd entries summing to \(L\). Vectors failing the digit-sum test modulo \(3\) are discarded immediately, and vectors with no \(5\) are impossible because the last digit is forced to be \(5\).

Every surviving vector contributes the number of permutations of \(c'\) whose remainder modulo \(7\) is \(3\). Adding these contributions gives the size of the entire length-\(L\) block. The C++ and Java implementations split this counting stage across several worker tasks; the Python implementation performs the same arithmetic serially.

Memoized remainder tables

The central cache stores, for each multiset state \(u\), a table of seven counts, one for each remainder class modulo \(7\). The only arithmetic precomputation needed is \(10^k \bmod 7\) for relevant powers \(k\), because the DP transition depends on the decimal place of the digit being inserted.

This cache is reused in two places: first when counting how many valid numbers a whole count vector contributes, and later when asking how many suffixes can complete a partially fixed prefix.

Digit-by-digit reconstruction

Once the target length is known, the code keeps a running record of how many copies of each digit have already been used and what the current prefix contributes modulo \(7\). At each position before the final digit, it tries the candidate digits \(1,3,5,7,9\) in increasing order.

For each candidate, it scans all admissible total count vectors of that length, checks which ones are still compatible with the chosen prefix and the reserved final \(5\), converts the leftover counts into a suffix state, and reads from the DP table how many suffixes satisfy the needed remainder. If that total is smaller than the remaining rank, the code skips the whole block at once. Otherwise it fixes the candidate digit and moves to the next position. After all earlier positions are decided, the last digit \(5\) is appended.

Complexity Analysis

Let \(M\) be the length of the final answer. Because the digit alphabet has fixed size \(5\) and the modulus is fixed at \(7\), the dynamic-programming state space is controlled entirely by the count vectors. The number of nonnegative count states with total size at most \(M-1\) is

$\sum_{m=0}^{M-1}\binom{m+4}{4}=\binom{M+4}{5},$

so the memoized remainder tables require \(O(M^5)\) states and the same polynomial order of work, up to constant factors coming from the five digit choices and seven remainders.

For a fixed length \(L\), the raw number of positive odd count vectors is

$\binom{\frac{L-5}{2}+4}{4},$

before the divisibility filters remove many of them. Reconstruction tries at most five candidate digits at each of the first \(L-1\) positions and scans the admissible vectors for that length, so its extra cost is linear in \(L\) times the number of surviving vectors. In practice, this is tiny compared with brute-force enumeration of the actual integers, because the algorithm works with aggregated multiset states rather than individual numbers.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=974
2. Modular arithmetic: Wikipedia - Modular arithmetic
3. Permutations of multisets: Wikipedia - Permutations of multisets
4. Dynamic programming: Wikipedia - Dynamic programming
5. Lexicographical order: Wikipedia - Lexicographical order