Problem 976: Perfect Power Detection

Mathematical Foundation

Definition 1. Let $\mathcal{P}(N) = \{n \in \mathbb{Z} : 1 \le n \le N, \; n = a^b \text{ for some } a \ge 1, b \ge 2\}$. We seek $|\mathcal{P}(N)|$ for $N = 10^{18}$.

Theorem 1 (Reduction to Prime Exponents). Every perfect power $n = a^b$ with $b \ge 2$ can be written as $n = c^p$ for some prime $p$ and integer $c \ge 1$.

Proof. Write $b = pm$ where $p$ is a prime factor of $b$. Then $n = a^b = (a^m)^p = c^p$ with $c = a^m$. $\square$

Theorem 2 (Inclusion-Exclusion Formula). Let $P_p(N) = \{n \le N : n = a^p \text{ for some } a \ge 1\}$, so $|P_p(N)| = \lfloor N^{1/p} \rfloor$. Then:

where $\mathcal{Q} = \{p \text{ prime} : p \le \log_2 N\}$ is the set of relevant prime exponents.

Proof. By inclusion-exclusion on the sets $P_p(N)$. A number in $P_{p_1} \cap P_{p_2} \cap \cdots \cap P_{p_k}$ (with $p_i$ distinct primes) is an $\text{lcm}(p_1,\ldots,p_k)$-th power, i.e., a $(p_1 p_2 \cdots p_k)$-th power (since the $p_i$ are distinct primes). Thus $|P_{p_1} \cap \cdots \cap P_{p_k}| = \lfloor N^{1/(p_1\cdots p_k)} \rfloor$. The union has no contribution from primes $p > \log_2 N$ since $\lfloor N^{1/p} \rfloor = 1$ and $1 = 1^p$ is already counted. $\square$

Lemma 1 (Exponent Bound). For $N = 10^{18}$, the relevant primes are $\mathcal{Q} = \{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59\}$, since $\log_2(10^{18}) \approx 59.79$.

Proof. If $p \ge 61$ is prime, then $\lfloor (10^{18})^{1/p} \rfloor \le \lfloor (10^{18})^{1/61} \rfloor = 1$, so $P_p$ contributes only $\{1\}$, which is already in every $P_q$. $\square$

Lemma 2 (Truncation of Inclusion-Exclusion). For $N = 10^{18}$, any subset $S \subseteq \mathcal{Q}$ with $\prod_{p \in S} p > 59$ satisfies $\lfloor N^{1/\prod p} \rfloor = 1$. Thus only subsets with product $\le 59$ contribute nontrivially.

Proof. If $\prod_{p \in S} p = e > 59$, then $N^{1/e} < N^{1/60} = 10^{18/60} = 10^{0.3} \approx 2$, so $\lfloor N^{1/e} \rfloor = 1$. These terms contribute a net correction that must be carefully tracked (adding/subtracting 1). $\square$

Editorial

Count the number of distinct perfect powers a^b <= 10^18, where a >= 1 and b >= 2. A perfect power is an integer that can be expressed as a^b for integers a >= 1, b >= 2. Numbers like 64 = 2^6 = 4^3 = 8^2 should only be counted once. We relevant prime exponents. We then iterate over all non-empty subsets of primes where product <= log2(N). Finally, use inclusion-exclusion.

Pseudocode

Relevant prime exponents
Iterate over all non-empty subsets of primes where product <= log2(N)
Use inclusion-exclusion
for each non-empty subset S of primes
floor(N^{1/e}) = 1, handle separately
else
Handle the subsets with large products (contribute +/- 1)
by careful enumeration
Note: N^{1/e} must be computed with care for large N
Use integer Newton's method: find largest a such that a^e <= N
Adjust: check a^e <= N < (a+1)^e

Complexity Analysis

• Time: $O(2^{|\mathcal{Q}|})$ subsets to enumerate, but heavy truncation (most subsets have product $> 59$ and are trivial) reduces this drastically. The dominant cost is $\lfloor N^{1/2} \rfloor = 10^9$ only as a value, not a loop. Each IntegerRoot call is $O(\log N)$ Newton iterations with $O(e \log N)$-bit arithmetic. In practice: $O(2^{|\mathcal{Q}|}$) with $|\mathcal{Q}| = 17$, giving $\sim 131072$ subsets, each with constant-time root computation. Total: $O(2^{17} \log N) \approx O(10^7)$.
• Space: $O(|\mathcal{Q}|) = O(\log N / \log\log N)$.

Answer

#include <bits/stdc++.h>
using namespace std;
int main() {
    // For 10^18 we need careful computation
    // Count distinct a^b with a>=1, b>=2, a^b <= 10^18
    // Use set of (base reduced to primitive form)
    long long N = 1000000000000000000LL;
    set<long long> seen;
    seen.insert(1);
    for (int b = 2; b <= 60; b++) {
        long long a = 2;
        while (true) {
            // Compute a^b, watch for overflow
            long long val = 1;
            bool overflow = false;
            for (int i = 0; i < b; i++) {
                if (val > N / a) { overflow = true; break; }
                val *= a;
            }
            if (overflow || val > N) break;
            seen.insert(val);
            a++;
        }
    }
    cout << (long long)seen.size() << endl;
    return 0;
}

"""
Problem 976: Perfect Power Detection

Count the number of distinct perfect powers a^b <= 10^18, where a >= 1 and b >= 2.

A perfect power is an integer that can be expressed as a^b for integers a >= 1, b >= 2.
Numbers like 64 = 2^6 = 4^3 = 8^2 should only be counted once.

Key results:
    - Enumerate all a^b for b = 2..60 (since 2^60 > 10^18), a = 2..iroot(N,b)
    - Use a set to deduplicate (e.g., 64 appears as 2^6, 4^3, 8^2)
    - Include 1 = 1^b for any b
    - answer = number of distinct perfect powers <= 10^18

Methods:
    1. iroot             — integer b-th root via Newton + binary search
    2. count_perfect_powers_brute — brute force enumeration with dedup set
    3. count_by_exponent — count of b-th powers for each exponent b
    4. perfect_power_density — fraction of integers <= N that are perfect powers
"""

from collections import Counter

def iroot(n, b):
    """Compute floor(n^(1/b)) exactly."""
    if n <= 0:
        return 0
    if b == 1:
        return n
    # Initial guess from floating point
    x = int(round(n ** (1.0 / b)))
    # Check neighborhood
    for dx in range(-3, 4):
        y = x + dx
        if y >= 1 and y ** b <= n and (y + 1) ** b > n:
            return y
    # Fallback: binary search
    lo, hi = 1, int(n ** (1.0 / b)) + 2
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if mid ** b <= n:
            lo = mid
        else:
            hi = mid - 1
    return lo

def count_perfect_powers_brute(N, max_exp=60):
    """Enumerate all a^b <= N for a>=2, b>=2..max_exp. Return deduplicated set."""
    seen = set()
    for b in range(2, max_exp + 1):
        r = iroot(N, b)
        if r < 2:
            break
        for a in range(2, r + 1):
            v = a ** b
            if v <= N:
                seen.add(v)
    seen.add(1)  # 1^b for any b
    return seen

def count_by_exponent(N, max_exp=60):
    """For each b, how many distinct b-th powers a^b <= N (a >= 2)."""
    exponents = []
    counts = []
    for b in range(2, max_exp + 1):
        r = iroot(N, b)
        if r < 2:
            break
        exponents.append(b)
        counts.append(r - 1)  # a = 2..r
    return exponents, counts

def perfect_power_density(max_exp_scale=12):
    """Count perfect powers <= 10^k for k=1..max_exp_scale."""
    ks = []
    counts = []
    densities = []
    for k in range(1, max_exp_scale + 1):
        Nk = 10 ** k
        pp = count_perfect_powers_brute(Nk, max_exp=60)
        ks.append(k)
        counts.append(len(pp))
        densities.append(len(pp) / Nk)
    return ks, counts, densities

#  Verification
# Perfect powers <= 100: 1,4,8,9,16,25,27,32,36,49,64,81,100 = 13
pp_100 = count_perfect_powers_brute(100)
assert len(pp_100) == 13, f"Expected 13 perfect powers <= 100, got {len(pp_100)}"
assert 64 in pp_100  # 2^6 = 4^3 = 8^2
assert 27 in pp_100  # 3^3

# iroot checks
assert iroot(1000000, 2) == 1000
assert iroot(1000000, 3) == 100
assert iroot(1024, 10) == 2

#  Main computation
N = 10 ** 18
seen = count_perfect_powers_brute(N)
answer = len(seen)
print(answer)

#  Visualization — 4-panel figure