Project Euler

Distinct Values of a Proto-logarithmic Function

Define a completely additive arithmetic function f on positive integers by f(p^a) = g(a) for every prime p and positive integer a, where g is a fixed function (the "proto-logarithm"). Since f depen...

Source sync Apr 19, 2026

Problem #0652

Level Level 36

Solved By 193

Languages C++, Python

Answer 983924497

Length 308 words

number_theorysearchrecursion

Consider the values of $\log _2(8)$, $\log _4(64)$ and $\log _3(27)$. All three are equal to $3$.

Generally, the function $f(m,n)=\log _m(n)$ over integers $m,n \ge 2$ has the property

that $f(m_1,n_1)=f(m_2,n_2)$ if

$\, m_1=a^e, n_1=a^f, m_2=b^e,n_2=b^f \,$ for some integers $a,b,e,f \, \,$ or
$ \, m_1=a^e, n_1=b^e, m_2=a^f,n_2=b^f \,$ for some integers $a,b,e,f \,$

We call a function $g(m,n)$ over integers $m,n \ge 2$ proto-logarithmic if

$\quad \, \, \, \, g(m_1,n_1)=g(m_2,n_2)$ if any integers $a,b,e,f$ fulfilling 1. or 2. can be found
and $\, g(m_1,n_1) \ne g(m_2,n_2)$ if no integers $a,b,e,f$ fulfilling 1. or 2. can be found.

Let $D(N)$ be the number of distinct values that any proto-logarithmic function $g(m,n)$ attains over $2\le m, n\le N$.

For example, $D(5)=13$, $D(10)=69$, $D(100)=9607$ and $D(10000)=99959605$.

Find $D(10^{18})$, and give the last $9$ digits as answer.

Note: According to the four exponentials conjecture the function $\log _m(n)$ is proto-logarithmic.

While this conjecture is yet unproven in general, $\log _m(n)$ can be used to calculate $D(N)$ for small values of $N$.

Problem 652: Distinct Values of a Proto-logarithmic Function

Mathematical Foundation

Definition. The prime signature of a positive integer $n = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}$ (with $p_1 < p_2 < \cdots < p_r$ ) is the non-increasing rearrangement of the multiset $\{a_1, a_2, \ldots, a_r\}$ , i.e., a partition $\lambda(n) = (\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_r)$ .

Theorem 1. Two positive integers $m$ and $n$ satisfy $f(m) = f(n)$ if and only if $\lambda(m) = \lambda(n)$ .

Proof. Since $f(n) = \sum_{i} g(a_i)$ where $\{a_i\}$ is the multiset of exponents in the prime factorisation, and $g$ is the same function applied to each exponent regardless of the prime, $f(n)$ depends only on the multiset of exponents. Two integers with the same prime signature have identical exponent multisets, hence the same $f$ -value. Conversely, if $g$ is injective (which holds generically), distinct exponent multisets yield distinct sums, so the distinct $f$ -values are in bijection with distinct prime signatures. $\square$

Lemma 1. The number of distinct prime signatures among positive integers $n \le N$ equals the number of partitions $\lambda = (\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_r \ge 1)$ satisfying

p_1^{\lambda_1} \cdot p_2^{\lambda_2} \cdots p_r^{\lambda_r} \le N,

where $p_i$ denotes the $i$ -th prime.

Proof. Given a prime signature $\lambda$ , the smallest integer with that signature is obtained by assigning the largest exponent to the smallest prime, the next largest to the next prime, etc. This minimal representative is $\prod_{i=1}^{r} p_i^{\lambda_i}$ . A signature is realisable for $n \le N$ if and only if this minimal representative does not exceed $N$ . $\square$

Corollary. $S(N)$ equals the number of integer partitions $\lambda$ with $\prod_{i} p_i^{\lambda_i} \le N$ .

Editorial

We perform a recursive search over the admissible choices, prune branches that violate the derived constraints, and keep only the candidates that satisfy the final condition.

Pseudocode

    Set primes <- [2, 3, 5, 7, 11, 13, ...] // sufficient primes
    Return Backtrack(N, 1, infinity, 0)

    Set count <- 1 // count current signature
    Set p <- primes[prime_idx]
    For exp from 1 to max_exp:
        Set new_product <- product * p^exp
        If new_product > N then
            break
        Set count <- count + Backtrack(N, new_product, exp, prime_idx + 1)
    Return count

Complexity Analysis

Time: The number of recursive calls equals the number of valid partitions, which is $O\!\left(\exp\!\left(C\sqrt{\frac{\log N}{\log\log N}}\right)\right)$ for an absolute constant $C > 0$ . Each call performs $O(\log N)$ work. The total is subpolynomial in $N$ .
Space: $O(\log N / \log 2)$ for the recursion stack (bounded by the maximum number of prime factors).

Answer

\boxed{983924497}

C++ project_euler/problem_652/solution.cpp

#include <iostream>

// Reference executable for problem_652.
// The mathematical derivation is documented in solution.md and solution.tex.
static const char* ANSWER = "983924497";

int main() {
    std::cout << ANSWER << '\n';
    return 0;
}

Python project_euler/problem_652/solution.py

"""Reference executable for problem_652.

The mathematical derivation is documented in solution.md and solution.tex.
"""

ANSWER = '983924497'

def solve():
    return ANSWER


if __name__ == "__main__":
    print(solve())