Detailed mathematical approach

Problem Summary

For every ordered pair \((x,y)\) with \(2 \le x,y \le N\), the problem asks for the number \(D(N)\) of distinct proto-logarithmic values that can occur. The central observation used by the C++, Python, and Java implementations is that every integer \(n \ge 2\) has a unique canonical form

$n=r^k,$

where \(r\) is not a perfect power and \(k \ge 1\) is maximal. Once both inputs are rewritten in that form, all duplicates are controlled by primitive bases and by reduced exponent ratios, so the count can be expressed using only \(L=\lfloor \log_2 N \rfloor\) and some short arithmetic tables.

Mathematical Approach

We write the final answer as

$D(N)=\operatorname{Rat}(N)+\operatorname{Irr}(N),$

where the first term counts values from the equal-base branch and the second counts values from the distinct-base branch.

Step 1: Rewrite Every Integer in Canonical Perfect-Power Form

Every integer \(n \ge 2\) can be written uniquely as \(n=r^k\) with \(r\) not a perfect power. Call such an \(r\) a primitive base. For a fixed primitive base \(r\), define its exponent capacity by

$A(r)=\max\{e \ge 1 : r^e \le N\}.$

So the numbers generated by \(r\) inside the range \([2,N]\) are exactly

$r,r^2,\dots,r^{A(r)}.$

If we rewrite an ordered pair as

$x=r^u,\qquad y=s^v,$

with \(1 \le u \le A(r)\) and \(1 \le v \le A(s)\), then the problem depends only on the ordered primitive bases \((r,s)\) and on the reduced fraction \(v/u\). This mirrors the usual identity

$\log_{r^u}(s^v)=\frac{v}{u}\cdot\frac{\log s}{\log r},$

which explains why the equal-base branch becomes rational and the distinct-base branch behaves like an irrational family indexed by \((r,s)\).

Step 2: Count Primitive Bases with Möbius Inversion

Let

$U(M)=\#\{r \in \mathbb{Z}_{\ge 2} : r \le M,\ \forall a,b \in \mathbb{Z}_{\ge 2},\ r \ne a^b\}.$

Every integer in \([2,M]\) has a unique representation \(r^e\) with primitive base \(r\), so counting all integers up to \(M\) gives

$M-1=\sum_{e=1}^{\lfloor \log_2 M \rfloor} U\!\left(\left\lfloor M^{1/e}\right\rfloor\right).$

Applying Möbius inversion yields the exact formula

$U(M)=\sum_{d=1}^{\lfloor \log_2 M \rfloor} \mu(d)\left(\left\lfloor M^{1/d}\right\rfloor-1\right).$

Now define \(B_A(N)\) to be the number of primitive bases whose exponent capacity is exactly \(A\). Then

$B_A(N)=U\!\left(\left\lfloor N^{1/A}\right\rfloor\right)-U\!\left(\left\lfloor N^{1/(A+1)}\right\rfloor\right).$

This partitions all primitive bases according to the largest exponent they can support inside the range.

Step 3: Count Reduced Exponent Ratios

For fixed bounds \(A\) and \(B\), define

$Q(A,B)=\#\{(u,v): 1 \le u \le A,\ 1 \le v \le B,\ \gcd(u,v)=1\}.$

This is exactly the number of distinct reduced fractions \(v/u\) that can appear when the denominator exponent is at most \(A\) and the numerator exponent is at most \(B\).

Using the standard Möbius count of visible lattice points,

$Q(A,B)=\sum_{d=1}^{\min(A,B)} \mu(d)\left\lfloor \frac{A}{d} \right\rfloor \left\lfloor \frac{B}{d} \right\rfloor.$

The implementations precompute this entire table once for all \(1 \le A,B \le L\), where

$L=\lfloor \log_2 N \rfloor.$

Step 4: Rational Branch

When the primitive bases coincide, say \(r=s\), the value depends only on the reduced fraction \(v/u\). Therefore the total number of distinct rational values is exactly the number of reduced positive fractions with both numerator and denominator at most \(L\):

$\operatorname{Rat}(N)=Q(L,L).$

This works because the primitive base \(2\) alone already supports exponents \(1,2,\dots,L\), since \(2^L \le N\) by definition of \(L\).

Step 5: Irrational Branch

When \(r \ne s\), the value belongs to the distinct-base branch. For a fixed ordered pair of primitive bases \((r,s)\), the only collisions come from reducing the fraction \(v/u\), so that pair contributes exactly \(Q(A(r),A(s))\) distinct values.

How many ordered primitive-base pairs have capacities \(A\) and \(B\)? If \(A \ne B\), the capacities already force different bases, so the count is

$P_{A,B}(N)=B_A(N)\,B_B(N).$

If \(A=B\), we must exclude choosing the same primitive base twice, so

$P_{A,A}(N)=B_A(N)\bigl(B_A(N)-1\bigr).$

Hence the entire irrational branch is

$\operatorname{Irr}(N)=\sum_{A=1}^{L}\sum_{B=1}^{L} P_{A,B}(N)\,Q(A,B).$

Worked Example: \(N=5\)

Here \(L=\lfloor \log_2 5 \rfloor=2\). The primitive bases not exceeding \(5\) are \(2,3,5\). Their exponent capacities are

$A(2)=2,\qquad A(3)=1,\qquad A(5)=1.$

So the capacity classes are

$B_1(5)=2,\qquad B_2(5)=1.$

The reduced-ratio counts are

$Q(1,1)=1,\qquad Q(1,2)=2,\qquad Q(2,1)=2,\qquad Q(2,2)=3.$

The rational branch contributes

$\operatorname{Rat}(5)=Q(2,2)=3,$

corresponding to the reduced fractions \(1\), \(2\), and \(1/2\).

For the irrational branch, the ordered-pair counts are

$P_{1,1}(5)=2,\qquad P_{1,2}(5)=2,\qquad P_{2,1}(5)=2,\qquad P_{2,2}(5)=0.$

Therefore

$\operatorname{Irr}(5)=2 \cdot 1 + 2 \cdot 2 + 2 \cdot 2 = 10,$

and the total is

$D(5)=3+10=13.$

This matches the first exact checkpoint used by the implementations.

How the Code Works

The C++, Python, and Java implementations first compute \(L=\lfloor \log_2 N \rfloor\) and build the Möbius values \(\mu(1),\dots,\mu(L)\) with a sieve. Because all later formulas depend only on exponent bounds up to \(L\), this immediately compresses the problem from a search over numbers up to \(N\) into a search over exponents up to roughly \(60\) for the target input.

Next, the implementation evaluates exact integer \(k\)-th roots such as \(\lfloor N^{1/k} \rfloor\). It starts from a floating-point estimate and then corrects it with integer power checks, so no rounding error leaks into the Möbius sums. Those exact roots feed the formula for \(U(M)\), and from there the code derives every \(B_A(N)\).

After that, the implementation fills the table \(Q(A,B)\) for all \(1 \le A,B \le L\) using the Möbius formula for coprime exponent pairs. Once this table exists, the rational part is just the single lookup \(Q(L,L)\).

The remaining work is the double sum for the irrational part. Off the diagonal \(A \ne B\), the number of ordered base pairs is \(B_A(N)B_B(N)\). On the diagonal, the code uses \(B_A(N)(B_A(N)-1)\) so that a primitive base is not paired with itself in the distinct-base branch.

For the full target \(N=10^{18}\), the answer is reported modulo \(10^9\). For smaller checkpoints, the implementations also support exact arithmetic, and the built-in validations verify values such as \(D(5)=13\), \(D(10)=69\), \(D(100)=9607\), and \(D(10000)=99959605\).

Complexity Analysis

Let \(L=\lfloor \log_2 N \rfloor\). The Möbius sieve is \(O(L)\). Building the coprime-ratio table requires

$\sum_{A=1}^{L}\sum_{B=1}^{L} O(\min(A,B))=O(L^3)$

operations and is the dominant asymptotic cost in the local implementations. The final irrational double sum is \(O(L^2)\), and the storage cost is \(O(L^2)\) because the \(Q(A,B)\) table is kept in memory. For the target input \(N=10^{18}\), we only have \(L=59\), so the method is easily fast enough.

Footnotes and References

1. Problem page: Project Euler 652
2. Perfect powers: Wikipedia - Perfect power
3. Möbius function: Wikipedia - Möbius function
4. Möbius inversion formula: Wikipedia - Möbius inversion formula
5. Coprime integers: Wikipedia - Coprime integers