Problem 800: Hybrid Integers

Mathematical Analysis

Key Observation: Logarithmic Transformation

A hybrid-integer has the form $p^q \cdot q^p$ where $p < q$ are distinct primes. We need to count how many such pairs $(p, q)$ satisfy:

Taking logarithms of both sides:

This transforms the problem from comparing astronomically large numbers to comparing manageable floating-point values.

Counting Strategy

For each prime $p$, we find the largest prime $q > p$ such that:

For a fixed $p$, as $q$ increases, the left side grows roughly as $q \ln p$ (since the $q \ln p$ term dominates). So for each $p$, we can use binary search among primes to find the maximum valid $q$.

The number of valid primes $q$ for a given $p$ is $\pi(q_{\max}) - \pi(p)$, where $\pi$ is the prime-counting function and $q_{\max}$ is the largest prime satisfying the inequality.

Upper Bound on $p$

When $p = q$, the inequality becomes $2p \ln p \leq 800800 \ln 800800$, giving approximately $p \leq 800800$. So we only need primes up to about 800800.

Editorial

Count hybrid-integers p^q * q^p <= 800800^800800 where p, q are distinct primes. Using logarithmic transformation: qln(p) + pln(q) <= 800800*ln(800800). We generate all primes up to a sufficient bound using the Sieve of Eratosthenes. We then iterate over each prime $p$ (in increasing order), use binary search to find the largest prime $q > p$ with $q \ln p + p \ln q \leq L$. Finally, add $\pi(q_{\max}) - \pi(p)$ to the count (number of primes between $p+1$ and $q_{\max}$).

Pseudocode

Generate all primes up to a sufficient bound using the Sieve of Eratosthenes
Let $L = 800800 \cdot \ln(800800)$
For each prime $p$ (in increasing order), use binary search to find the largest prime $q > p$ with $q \ln p + p \ln q \leq L$
Add $\pi(q_{\max}) - \pi(p)$ to the count (number of primes between $p+1$ and $q_{\max}$)
Stop when even $q = \text{nextprime}(p)$ violates the bound

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

• Sieve: $O(N \log \log N)$ where $N \approx 800800$.
• Main loop: For each of the $\sim N/\ln N$ primes $p$, a binary search taking $O(\log(N/\ln N))$.
• Total: $O(N \log \log N)$ dominated by the sieve.

Answer

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

int main() {
    // We need to count pairs (p, q) with p < q both prime such that
    // p^q * q^p <= 800800^800800
    // Equivalently: q*ln(p) + p*ln(q) <= 800800*ln(800800)

    const int LIMIT = 800800;
    const double L = (double)LIMIT * log((double)LIMIT);

    // Sieve of Eratosthenes
    // Upper bound: q can be at most around LIMIT (when p=2, q*ln2 <= L => q ~ L/ln2 ~ 800800*ln(800800)/ln(2))
    // ln(800800) ~ 13.59, so q_max ~ 800800*13.59/0.693 ~ 15.7M
    // But we need a tighter bound. For p=2: q*ln(2) + 2*ln(q) <= L
    // q ~ L/ln(2) ~ 800800*13.59/0.693 ~ 15,700,000
    const int SIEVE_LIMIT = 16000000;

    vector<bool> is_prime(SIEVE_LIMIT + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; (long long)i * i <= SIEVE_LIMIT; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= SIEVE_LIMIT; j += i)
                is_prime[j] = false;
        }
    }

    vector<int> primes;
    primes.reserve(1100000);
    for (int i = 2; i <= SIEVE_LIMIT; i++)
        if (is_prime[i])
            primes.push_back(i);

    long long count = 0;
    int n = primes.size();

    // Two-pointer approach: for increasing p, q_max decreases
    int right = n - 1;

    for (int i = 0; i < n; i++) {
        long long p = primes[i];
        double lnp = log((double)p);

        // We need q > p, so j > i
        // q*ln(p) + p*ln(q) <= L
        // As p increases, the max valid q decreases
        if (right <= i) right = i + 1;

        // Shrink right pointer
        while (right >= 0 && right > i) {
            long long q = primes[right];
            double val = (double)q * lnp + (double)p * log((double)q);
            if (val <= L) break;
            right--;
        }

        if (right <= i) break; // no valid q for this p

        count += (long long)(right - i);
    }

    cout << count << endl;

    return 0;
}

"""
Project Euler Problem 800: Hybrid Integers

Count hybrid-integers p^q * q^p <= 800800^800800 where p, q are distinct primes.
Using logarithmic transformation: q*ln(p) + p*ln(q) <= 800800*ln(800800)
"""

import math

def sieve(limit):
    """Sieve of Eratosthenes"""
    is_prime = bytearray([1]) * (limit + 1)
    is_prime[0] = is_prime[1] = 0
    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            is_prime[i*i::i] = bytearray(len(is_prime[i*i::i]))
    return [i for i in range(2, limit + 1) if is_prime[i]]

def solve():
    LIMIT = 800800
    L = LIMIT * math.log(LIMIT)

    # For p=2, max q ~ L/ln(2) ~ 15.7M
    SIEVE_LIMIT = 16_000_000
    primes = sieve(SIEVE_LIMIT)

    count = 0
    n = len(primes)
    right = n - 1

    for i in range(n):
        p = primes[i]
        lnp = math.log(p)

        if right <= i:
            right = i + 1

        while right > i:
            q = primes[right]
            val = q * lnp + p * math.log(q)
            if val <= L:
                break
            right -= 1

        if right <= i:
            break

        count += right - i

    print(count)

if __name__ == "__main__":
    solve()