Problem 974: Very Odd Numbers

Project Euler Problem 974 Solution

EulerSolve provides an optimized solution for Project Euler Problem 974, Very Odd Numbers, with C++, Python, Java, and a step-by-step mathematical explanation.

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$....

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

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

Problem 974 source code

C++

#include <iostream>
#include <vector>
#include <numeric>
#include <string>
#include <algorithm>
#include <map>
#include <array>
#include <mutex>
#include <future>
#include <iomanip>

using namespace std;

// Represents the counts of digits 1, 3, 5, 7, 9
struct Counts {
    int c[5]; // Indices: 0->1, 1->3, 2->5, 3->7, 4->9

    bool operator<(const Counts& other) const {
        for (int i = 0; i < 5; ++i) {
            if (c[i] != other.c[i]) return c[i] < other.c[i];
        }
        return false;
    }

    bool operator==(const Counts& other) const {
        for (int i = 0; i < 5; ++i) {
            if (c[i] != other.c[i]) return false;
        }
        return true;
    }
};

const int DIGITS[] = {1, 3, 5, 7, 9};

// Global memoization cache
// Map from Counts -> array of 7 longs (count of permutations for each remainder)
map<Counts, array<long long, 7>> memo;
mutex memo_mutex;

// Modular powers of 10 for efficient remainder calculation
long long pow10mod7[50];

void init_pow() {
    pow10mod7[0] = 1;
    for (int i = 1; i < 50; ++i) {
        pow10mod7[i] = (pow10mod7[i - 1] * 10) % 7;
    }
}

// Factorials for multinomial check (optional, but good for debugging total counts)
long long factorial[30];
void init_fact() {
    factorial[0] = 1;
    for (int i = 1; i < 30; ++i) factorial[i] = factorial[i - 1] * i;
}

// DP function to count permutations
// Returns array[7] where index is remainder mod 7
array<long long, 7> get_rem_counts(Counts counts) {
    int total_len = 0;
    for (int x : counts.c) total_len += x;

    if (total_len == 0) {
        array<long long, 7> res = {0};
        res[0] = 1;
        return res;
    }

    {
        lock_guard<mutex> lock(memo_mutex);
        if (memo.count(counts)) {
            return memo[counts];
        }
    }

    array<long long, 7> total_res = {0};

    // Try placing each available digit at the CURRENT position (most significant of the remaining block? No, let's build from right to left or left to right)
    // Actually, order matters for mod 7. 
    // Is it simpler to place the *first* digit (most significant)?
    // Remainder = (d * 10^(L-1) + rest) % 7.
    // Yes.
    
    // We strictly need to be consistent. Let's assume we are placing the most significant digit.
    // Power needed is 10^(total_len - 1).
    int power = pow10mod7[total_len - 1];

    for (int i = 0; i < 5; ++i) {
        if (counts.c[i] > 0) {
            Counts next_counts = counts;
            next_counts.c[i]--;
            
            // Recurse
            // No need to lock for recursion, but cache access needs lock
            // To avoid deadlock or high contention, we might need thread-local caches or better locking strategy.
            // For now, simple lock is safest.
            
            // NOTE: To avoid holding lock during recursion, we release it. 
            // We already released it after checking cache.
            
            array<long long, 7> sub_res = get_rem_counts(next_counts);

            int digit = DIGITS[i];
            int current_rem_contribution = (digit * power) % 7;

            for (int r = 0; r < 7; ++r) {
                if (sub_res[r] > 0) {
                    int new_rem = (current_rem_contribution + r) % 7;
                    total_res[new_rem] += sub_res[r];
                }
            }
        }
    }

    {
        lock_guard<mutex> lock(memo_mutex);
        memo[counts] = total_res;
    }
    return total_res;
}

// Optimized DP without locking for single-threaded reconstruction
array<long long, 7> get_rem_counts_nolock(Counts counts, map<Counts, array<long long, 7>>& local_memo) {
    int total_len = 0;
    for (int x : counts.c) total_len += x;

    if (total_len == 0) {
        array<long long, 7> res = {0};
        res[0] = 1;
        return res;
    }

    if (local_memo.count(counts)) return local_memo[counts];

    array<long long, 7> total_res = {0};
    int power = pow10mod7[total_len - 1];

    for (int i = 0; i < 5; ++i) {
        if (counts.c[i] > 0) {
            Counts next_counts = counts;
            next_counts.c[i]--;
            
            array<long long, 7> sub_res = get_rem_counts_nolock(next_counts, local_memo);
            int digit = DIGITS[i];
            int current_rem_contribution = (digit * power) % 7;

            for (int r = 0; r < 7; ++r) {
                 total_res[(current_rem_contribution + r) % 7] += sub_res[r];
            }
        }
    }
    return local_memo[counts] = total_res;
}


// Worker function for a batch of count tuples
long long process_tuples(const vector<Counts>& tuples, int length) {
    long long count = 0;
    for (const auto& c : tuples) {
        // Condition: Sum of Digits % 3 == 0
        long long sum_digits = 0;
        for (int i = 0; i < 5; ++i) sum_digits += (long long)c.c[i] * DIGITS[i];
        if (sum_digits % 3 != 0) continue;

        // Condition 2: Divisible by 5 (Last digit is 5)
        // We need permutations of (Counts - one 5) ending in 5.
        // So we look at permutations of the remaining set.
        // Remaining set R has counts c.
        // But the full number is P * 10 + 5.
        // We want (P * 10 + 5) % 7 == 0 => 3*P + 5 == 0 mod 7 => 3*P == 2 => P == 3 mod 7.
        // So we need P (permutation of remaining digits) to have remainder 3.
        
        if (c.c[2] < 1) continue; // Must have at least one 5 to be the last digit
        
        Counts remaining = c;
        remaining.c[2]--; // Remove the last 5
        
        array<long long, 7> rems = get_rem_counts(remaining);
        count += rems[3]; // We need remainder 3
    }
    return count;
}

// Generate partitions
void generate_partitions(int index, int remaining_len, Counts current, vector<Counts>& result) {
    if (index == 5) {
        if (remaining_len == 0) {
            result.push_back(current);
        }
        return;
    }
    
    // Each count must be odd
    // Max count is remaining_len.
    // Try 1, 3, 5...
    for (int k = 1; k <= remaining_len; k += 2) {
        current.c[index] = k;
        // Optimization: remaining digits must sum to remaining_len - k
        // Minimum for future digits is 1 each.
        // So k cannot be such that remaining_len - k < (5 - 1 - index) * 1
        if (remaining_len - k >= (4 - index)) {
            generate_partitions(index + 1, remaining_len - k, current, result);
        }
    }
}

// Find logic for N-th number
// Returns string representation
string find_nth(long long N) {
    long long current_count = 0;
    
    // 1. Find Length
    for (int L = 5; ; L += 2) {
        // Generate tuples
        vector<Counts> all_tuples;
        generate_partitions(0, L, {0}, all_tuples);
        
        // Parallel processing to count
        int num_threads = thread::hardware_concurrency();
        vector<future<long long>> futures;
        int chunk_size = (all_tuples.size() + num_threads - 1) / num_threads;
        
        // Reset/Clear memo for new length to save memory? 
        // L=19 states ~3000. Not needed to clear.
        
        for (int i = 0; i < num_threads; ++i) {
            int start = i * chunk_size;
            if (start >= all_tuples.size()) break;
            int end = min((int)all_tuples.size(), start + chunk_size);
            
            // Copy sub-vector
            vector<Counts> chunk(all_tuples.begin() + start, all_tuples.begin() + end);
            futures.push_back(async(launch::async, process_tuples, chunk, L));
        }
        
        long long count_for_L = 0;
        for (auto& f : futures) count_for_L += f.get();
        
        if (current_count + count_for_L >= N) {
            // Target is in this length.
            // Find which Tuple
            
            // We need to iterate tuples in a deterministic order (lexicographical usually implied by problem?)
            // "Define Theta(n) be the nth very odd number".
            // Numbers are ordered by value.
            // Value order: Smallest length comes first.
            // Within same length, numbers are sorted naturally.
            // So we cannot just pick a tuple. We have to mix all tuples.
            // Actually, we construct digit by digit.
            // We know the length is L.
            // We know the set of valid tuples.
            
            map<Counts, array<long long, 7>> local_memo; // For fast reconstruction

            string res = "";
            
            // We have 'current_count' numbers before this Length.
            long long target_in_L = N - current_count;
            
            // We need to construct L digits.
            // Wait, the last digit is FIXED to 5.
            // So we really construct L-1 digits.
            // And we have a constraint that the counts of the FULL number (including the last 5) must match ONE of the valid tuples.
            // AND the digits used so far affect the remaining needed counts.
            
            // Let's refine the reconstruction state.
            // We are building a prefix.
            // At each step, we try placing a digit d (1, 3, 5, 7, 9).
            // Length remaining: rem_len.
            // Counts used so far.
            // We need to count how many ways to complete this prefix to form a VALID number (valid tuple + divisible by 7 + divisible by 3 + ends in 5).
            
            // State for reconstruction:
            // - Current index (0 to L-1).
            // - Current remainder mod 7.
            // - Current counts of digits used.
            // - Remainder condition for Div 3?
            //   Div 3 condition is on the SUM of digits. 
            //   Sum so far + Sum of future = 0 mod 3.
            
            // But actually, we only care if the FINAL counts match ANY valid tuple.
            // Valid tuples are those where counts are all odd and sum % 3 == 0.
            
            // So, for a trial digit d:
            // count_valid_completions = Sum over all Valid Tuples T of (ways to form T given we have used counts so far + d).
            
            Counts current_used = {{0}};
            int current_rem = 0;
            // The last digit is 5.
            // The first L-1 digits determine divisibility if we consider the last 5.
            
            // Let's iterate positions 0 to L-2 (since L-1 is fixed 5).
            for (int pos = 0; pos < L - 1; ++pos) {
                int power = pow10mod7[L - 1 - pos];
                
                for (int d_idx = 0; d_idx < 5; ++d_idx) {
                    int d = DIGITS[d_idx];
                    
                    // Try placing 'd'
                    // Calculate how many valid numbers start with 'res + d'
                    
                    long long ways = 0;
                    
                    // Temporarily update state
                    current_used.c[d_idx]++;
                    int next_rem = (current_rem + d * power) % 7;
                    
                    // Sum ways over valid target tuples
                    // A target tuple T is valid if T.c[i] >= current_used.c[i] for all i
                    // AND T is a valid tuple (odd counts, sum%3==0)
                    // AND the remaining counts form a suffix that satisfies the modulo 7 requirement.
                    // Modulo requirement:
                    // N = Prefix * 10^(suffix_len + 1) + Suffix * 10 + 5
                    // We maintain next_rem which is Prefix * 10^(suffix_len + 1)
                    // So we need: next_rem + 10 * Suffix + 5 == 0 (mod 7)
                    // 3 * Suffix == -(next_rem + 5) (mod 7)
                    // Suffix == -(next_rem + 5) * 5 (mod 7)
                    
                    long long term = (next_rem + 5) % 7;
                    int needed_suffix_rem = (int)(((-term * 5) % 7 + 7) % 7);
                    
                    // Check if SuffixCounts are non-negative
                    
                    for (const auto& T : all_tuples) {
                        // Check div 3
                        long long s = 0;
                        for(int k=0; k<5; ++k) s+=T.c[k]*DIGITS[k];
                        if (s%3 != 0) continue;
                        
                        // Check if T is reachable
                        bool possible = true;
                        Counts suffix_counts = {{0}};
                        for(int k=0; k<5; ++k) {
                            int needed = T.c[k] - current_used.c[k];
                            if (k == 2) needed--; // Reserved for last digit
                            if (needed < 0) { possible = false; break; }
                            suffix_counts.c[k] = needed;
                        }
                        if (!possible) continue;
                        
                        // Count permutations of suffix_counts matching needed_rem
                        array<long long, 7> c_rems = get_rem_counts_nolock(suffix_counts, local_memo);
                        ways += c_rems[needed_suffix_rem];
                    }
                    
                    if (target_in_L <= ways) {
                        // Accepted this digit
                        res += to_string(d);
                        current_rem = next_rem;
                        // current_used is already incremented
                        goto next_position; // Break from digit loop, continue to next pos
                    } else {
                        target_in_L -= ways;
                        current_used.c[d_idx]--; // Backtrack
                    }
                }
                // If we reach here, we failed to find a digit for this position
                cerr << "Error: Failed to reconstructed digit at pos " << pos << " L=" << L << " TargetRemaining=" << target_in_L << endl;
                return "ERROR";

                next_position:;
            }
            
            res += "5"; // Append last digit
            return res;
            
        } else {
            current_count += count_for_L;
        }
    }
}

int main() {
    init_pow();
    init_fact();
    
    // Validation
    cout << "Validating Theta(1)..." << endl;
    string t1 = find_nth(1);
    cout << "Theta(1) = " << t1 << " (Expected: 1117935)" << endl;
    if (t1 != "1117935") {
        cerr << "Validation Failed for Theta(1)!" << endl;
        // return 1;
    }

    cout << "Validating Theta(1000)..." << endl;
    string t1000 = find_nth(1000);
    cout << "Theta(1000) = " << t1000 << " (Expected: 11137955115)" << endl;
    if (t1000 != "11137955115") {
         cerr << "Validation Failed for Theta(1000)!" << endl;
         // return 1;
    }

    cout << "Calculating Theta(10^16)..." << endl;
    string ans = find_nth(10000000000000000LL);
    cout << "Theta(10^16) = " << ans << endl;

    return 0;
}

Python

import sys
import math

DIGITS = [1, 3, 5, 7, 9]
pow10mod7 = [1] * 50
for i in range(1, 50):
    pow10mod7[i] = (pow10mod7[i-1] * 10) % 7

memo = {}

def get_rem_counts(counts):
    total_len = sum(counts)
    if total_len == 0:
        res = [0]*7
        res[0] = 1
        return res
        
    if counts in memo:
        return memo[counts]
        
    total_res = [0]*7
    power = pow10mod7[total_len - 1]
    
    for i in range(5):
        if counts[i] > 0:
            next_counts = list(counts)
            next_counts[i] -= 1
            next_tuple = tuple(next_counts)
            
            sub_res = get_rem_counts(next_tuple)
            
            digit = DIGITS[i]
            cur_rem = (digit * power) % 7
            
            for r in range(7):
                if sub_res[r] > 0:
                    new_rem = (cur_rem + r) % 7
                    total_res[new_rem] += sub_res[r]
                    
    memo[counts] = total_res
    return total_res

def process_tuples(chunk):
    count = 0
    for c in chunk:
        sum_digits = sum(c[i] * DIGITS[i] for i in range(5))
        if sum_digits % 3 != 0:
            continue
            
        if c[2] < 1:
            continue
            
        remaining = list(c)
        remaining[2] -= 1
        
        rems = get_rem_counts(tuple(remaining))
        count += rems[3]
        
    return count

def generate_partitions(index, remaining_len, current, result):
    if index == 5:
        if remaining_len == 0:
            result.append(tuple(current))
        return
        
    for k in range(1, remaining_len + 1, 2):
        current[index] = k
        if remaining_len - k >= (4 - index):
            generate_partitions(index + 1, remaining_len - k, current, result)

def find_nth(N):
    current_count = 0
    L = 5
    while True:
        all_tuples = []
        generate_partitions(0, L, [0]*5, all_tuples)
        
        # We can just process locally since it's fast enough in Python using DP
        count_for_L = process_tuples(all_tuples)
        
        if current_count + count_for_L >= N:
            res = ""
            target_in_L = N - current_count
            current_used = [0]*5
            current_rem = 0
            
            for pos in range(L - 1):
                power = pow10mod7[L - 1 - pos]
                
                accepted = False
                for d_idx in range(5):
                    d = DIGITS[d_idx]
                    ways = 0
                    
                    current_used[d_idx] += 1
                    next_rem = (current_rem + d * power) % 7
                    
                    term = (next_rem + 5) % 7
                    needed_suffix_rem = (-term * 5) % 7
                    if needed_suffix_rem < 0:
                        needed_suffix_rem += 7
                        
                    for T in all_tuples:
                        s = sum(T[k]*DIGITS[k] for k in range(5))
                        if s % 3 != 0:
                            continue
                            
                        possible = True
                        suffix_counts = [0]*5
                        for k in range(5):
                            needed = T[k] - current_used[k]
                            if k == 2:
                                needed -= 1
                            if needed < 0:
                                possible = False
                                break
                            suffix_counts[k] = needed
                            
                        if not possible:
                            continue
                            
                        c_rems = get_rem_counts(tuple(suffix_counts))
                        ways += c_rems[needed_suffix_rem]
                        
                    if target_in_L <= ways:
                        res += str(d)
                        current_rem = next_rem
                        accepted = True
                        break
                    else:
                        target_in_L -= ways
                        current_used[d_idx] -= 1
                        
                if not accepted:
                    return "ERROR"
            
            res += "5"
            return res
            
        else:
            current_count += count_for_L
            L += 2

def solve():
    return find_nth(10000000000000000)

if __name__ == "__main__":
    assert find_nth(1) == "1117935"
    print(solve())

Java

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;

public class Euler974 {

    static class Counts implements Comparable<Counts> {
        int[] c = new int[5];

        Counts() {
        }

        Counts(int[] counts) {
            System.arraycopy(counts, 0, this.c, 0, 5);
        }

        @Override
        public int compareTo(Counts o) {
            for (int i = 0; i < 5; ++i) {
                if (c[i] != o.c[i])
                    return Integer.compare(c[i], o.c[i]);
            }
            return 0;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (!(obj instanceof Counts))
                return false;
            Counts other = (Counts) obj;
            for (int i = 0; i < 5; ++i) {
                if (c[i] != other.c[i])
                    return false;
            }
            return true;
        }

        @Override
        public int hashCode() {
            int hash = 0;
            for (int val : c) {
                hash = hash * 31 + val;
            }
            return hash;
        }
    }

    static final int[] DIGITS = { 1, 3, 5, 7, 9 };
    static Map<Counts, long[]> memo = new ConcurrentHashMap<>();
    static long[] pow10mod7 = new long[50];

    static void initPow() {
        pow10mod7[0] = 1;
        for (int i = 1; i < 50; ++i) {
            pow10mod7[i] = (pow10mod7[i - 1] * 10) % 7;
        }
    }

    static long[] getRemCounts(Counts counts) {
        int totalLen = 0;
        for (int x : counts.c)
            totalLen += x;

        if (totalLen == 0) {
            long[] res = new long[7];
            res[0] = 1;
            return res;
        }

        long[] cached = memo.get(counts);
        if (cached != null) {
            return cached;
        }

        long[] totalRes = new long[7];
        int power = (int) pow10mod7[totalLen - 1];

        for (int i = 0; i < 5; ++i) {
            if (counts.c[i] > 0) {
                Counts nextCounts = new Counts(counts.c);
                nextCounts.c[i]--;

                long[] subRes = getRemCounts(nextCounts);
                int digit = DIGITS[i];
                int currentRemContribution = (digit * power) % 7;

                for (int r = 0; r < 7; ++r) {
                    if (subRes[r] > 0) {
                        int newRem = (currentRemContribution + r) % 7;
                        totalRes[newRem] += subRes[r];
                    }
                }
            }
        }

        memo.put(counts, totalRes);
        return totalRes;
    }

    static long processTuples(List<Counts> tuples) {
        long count = 0;
        for (Counts c : tuples) {
            long sumDigits = 0;
            for (int i = 0; i < 5; ++i)
                sumDigits += (long) c.c[i] * DIGITS[i];
            if (sumDigits % 3 != 0)
                continue;

            if (c.c[2] < 1)
                continue;

            Counts remaining = new Counts(c.c);
            remaining.c[2]--;

            long[] rems = getRemCounts(remaining);
            count += rems[3];
        }
        return count;
    }

    static void generatePartitions(int index, int remainingLen, int[] current, List<Counts> result) {
        if (index == 5) {
            if (remainingLen == 0) {
                result.add(new Counts(current));
            }
            return;
        }

        for (int k = 1; k <= remainingLen; k += 2) {
            current[index] = k;
            if (remainingLen - k >= (4 - index)) {
                generatePartitions(index + 1, remainingLen - k, current, result);
            }
        }
    }

    static String findNth(long N) {
        long currentCount = 0;

        for (int L = 5;; L += 2) {
            List<Counts> allTuples = new ArrayList<>();
            int[] current = new int[5];
            generatePartitions(0, L, current, allTuples);

            long countForL = processTuples(allTuples);

            if (currentCount + countForL >= N) {
                StringBuilder res = new StringBuilder();
                long targetInL = N - currentCount;

                int[] currentUsed = new int[5];
                int currentRem = 0;

                for (int pos = 0; pos < L - 1; ++pos) {
                    int power = (int) pow10mod7[L - 1 - pos];

                    boolean accepted = false;
                    for (int dIdx = 0; dIdx < 5; ++dIdx) {
                        int d = DIGITS[dIdx];
                        long ways = 0;

                        currentUsed[dIdx]++;
                        int nextRem = (currentRem + d * power) % 7;

                        long term = (nextRem + 5) % 7;
                        int neededSuffixRem = (int) ((((-term * 5) % 7) + 7) % 7);

                        for (Counts T : allTuples) {
                            long s = 0;
                            for (int k = 0; k < 5; ++k)
                                s += (long) T.c[k] * DIGITS[k];
                            if (s % 3 != 0)
                                continue;

                            boolean possible = true;
                            Counts suffixCounts = new Counts();
                            for (int k = 0; k < 5; ++k) {
                                int needed = T.c[k] - currentUsed[k];
                                if (k == 2)
                                    needed--;
                                if (needed < 0) {
                                    possible = false;
                                    break;
                                }
                                suffixCounts.c[k] = needed;
                            }
                            if (!possible)
                                continue;

                            long[] cRems = getRemCounts(suffixCounts);
                            ways += cRems[neededSuffixRem];
                        }

                        if (targetInL <= ways) {
                            res.append(d);
                            currentRem = nextRem;
                            accepted = true;
                            break;
                        } else {
                            targetInL -= ways;
                            currentUsed[dIdx]--;
                        }
                    }
                    if (!accepted)
                        return "ERROR";
                }

                res.append('5');
                return res.toString();

            } else {
                currentCount += countForL;
            }
        }
    }

    public static String solve() {
        return findNth(10_000_000_000_000_000L);
    }

    public static void main(String[] args) {
        initPow();
        if (!findNth(1).equals("1117935")) {
            System.out.println("Validation failed");
            return;
        }
        System.out.println(solve());
    }
}