Problem 637: Flexible Digit Sum

Mathematical Analysis

Digital Root Connection

The function f(n,B) is closely related to the iterated digit sum in base B. The number of steps to reach a single digit is essentially the number of times we need to take the digit sum.

For base B, a number n has f(n,B) = 0 if n < B (already single digit). Otherwise, f(n,B) = 1 + f(digitsum_B(n), B), where digitsum_B computes the sum of digits in base B.

Key Property

The digital root of n in base B is:

• 0 if n = 0
• 1 + ((n-1) mod (B-1)) otherwise

The number of steps f(n,B) depends on the magnitude of n and its iterated digit sums.

Algorithm for f(n,B)

For each number i from 1 to 10^7:

1. Compute f(i, 10): repeatedly sum digits in base 10 until single digit
2. Compute f(i, 3): repeatedly sum digits in base 3 until single digit
3. If f(i, 10) == f(i, 3), add i to the running sum

Optimization

• f(n, B) = 0 if n < B
• f(n, B) = 1 if the digit sum of n in base B is a single digit
• f(n, B) = 2 if the digit sum of the digit sum is single digit, etc.

For base 10, most numbers up to 10^7 have f = 1 or 2 (since digit sum of 9999999 = 63, then 9, so f = 2). For base 3, numbers up to 10^7 can have f up to about 3 or 4.

Editorial

a. Compute f(i, 10) by iterating digit sums in base 10 b. Compute f(i, 3) by iterating digit sums in base 3 c. If equal, add i to result. We iterate over each i from 1 to 10^7. Finally, return result.

Pseudocode

For each i from 1 to 10^7:
Return result

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity Analysis

• Time: O(N * log(N)) where N = 10^7, since digit sum computation is O(log_B(n))
• Space: O(1) (streaming computation)

Answer

#include <bits/stdc++.h>
using namespace std;

/*
 * Project Euler 637: Flexible Digit Sum
 *
 * f(n,B) = number of digit-sum steps to reach a single digit in base B.
 * g(n,B1,B2) = sum of i <= n where f(i,B1) == f(i,B2).
 * Find g(10^7, 10, 3).
 */

int digitSum(int n, int base) {
    int s = 0;
    while (n > 0) {
        s += n % base;
        n /= base;
    }
    return s;
}

int f(int n, int base) {
    int steps = 0;
    while (n >= base) {
        n = digitSum(n, base);
        steps++;
    }
    return steps;
}

int main() {
    const int N = 10000000;
    long long result = 0;

    for (int i = 1; i <= N; i++) {
        if (f(i, 10) == f(i, 3)) {
            result += i;
        }
    }

    cout << result << endl;
    return 0;
}

"""
Project Euler 637: Flexible Digit Sum

f(n,B) = number of digit-sum steps to reach a single digit in base B.
g(n,B1,B2) = sum of i <= n where f(i,B1) == f(i,B2).
Find g(10^7, 10, 3).
"""

def digit_sum(n, base):
    """Compute the sum of digits of n in the given base."""
    s = 0
    while n > 0:
        s += n % base
        n //= base
    return s

def f(n, base):
    """Number of digit-sum steps to reach a single digit in given base."""
    steps = 0
    while n >= base:
        n = digit_sum(n, base)
        steps += 1
    return steps

def solve():
    N = 10**7
    result = 0
    for i in range(1, N + 1):
        if f(i, 10) == f(i, 3):
            result += i
    print(result)

if __name__ == "__main__":
    solve()