Project Euler Problem 800

Solution

Answer: 1412403576

Let

$$H(p,q)=p^q q^p$$

with distinct primes $p\neq q$. We must count the number of unordered prime pairs $(p,q)$ such that

$$p^q q^p \le 800800^{800800}.$$

Define

$$L = \log\left(800800^{800800}\right)=800800\log(800800).$$

Taking logarithms transforms the inequality into

$$q\log p + p\log q \le L.$$

So the problem becomes:

Count prime pairs $p<q$ satisfying

$$q\log p + p\log q \le L.$$

---

1. Mathematical analysis

Step 1 — Rewrite using logarithms

Because logarithm is strictly increasing,

$$p^q q^p \le N \iff q\log p + p\log q \le \log N.$$

For the target value,

$$N = 800800^{800800},$$

so

$$L = 800800\log(800800).$$

---

Step 2 — Monotonicity

For fixed $p$, define

$$f_p(q)=q\log p + p\log q.$$

For $q>1$,

$$f_p'(q)=\log p + \frac{p}{q}>0,$$

so $f_p(q)$ is strictly increasing in $q$.

Therefore, for each prime $p$, there is a largest prime $q$ satisfying the inequality. This allows a two-pointer approach.

---

Step 3 — Prime bound

The largest possible $q$ occurs when $p=2$:

$$q\log 2 + 2\log q \le L.$$

Hence approximately

$$q \lesssim \frac{L}{\log 2}.$$

Numerically this is about $1.57\times 10^7$, which is entirely feasible for a sieve of Eratosthenes.

---

Step 4 — Two-pointer counting

Let the primes be

$$p_0<p_1<\cdots<p_{m-1}.$$

We maintain a pointer $j$ starting at the largest prime index.

For each $i$:

• decrease $j$ while

$$p_j\log p_i + p_i\log p_j > L,$$

• then every prime between indices $i+1$ and $j$ works.

Add

$$j-i$$

to the count.

Because $j$ only moves downward, the algorithm is linear after sieving.

---

2. Python implementation

from math import log, isqrt

def hybrid_count(base, exponent):
    # L = log(base^exponent)
    L = exponent * log(base)

    # Maximum possible q occurs roughly when p = 2
    limit = int(L / log(2)) + 10

    # Sieve of Eratosthenes
    sieve = bytearray(b'\x01') * (limit + 1)
    sieve[0:2] = b'\x00\x00'

    for p in range(2, isqrt(limit) + 1):
        if sieve[p]:
            start = p * p
            sieve[start:limit + 1:p] = (
                b'\x00' * (((limit - start) // p) + 1)
            )

    primes = [i for i, v in enumerate(sieve) if v]
    logs = [log(p) for p in primes]

    # Two-pointer counting
    total = 0
    j = len(primes) - 1

    for i, p in enumerate(primes):

        while j > i and primes[j] * logs[i] + p * logs[j] > L:
            j -= 1

        if j <= i:
            break

        total += (j - i)

    return total

# Checks from the problem statement
print(hybrid_count(800, 1))      # C(800)
print(hybrid_count(800, 800))    # C(800^800)

# Final answer
print(hybrid_count(800800, 800800))

---

3. Code walkthrough

Computing $L$

L = exponent * log(base)

Since

$$\log(base^{exponent}) = exponent \log(base),$$

this avoids huge integers entirely.

---

Generating primes

We sieve all primes up to approximately

$$\frac{L}{\log 2}.$$

This safely includes every possible candidate for $q$.

---

Two-pointer section

while j > i and primes[j] * logs[i] + p * logs[j] > L:
    j -= 1

This shrinks the upper bound until the inequality holds.

Then all primes from index $i+1$ through $j$ are valid.

---

4. Verification

The program reproduces the given examples:

$$C(800)=2$$

and

$$C(800^{800})=10790.$$

So the method is consistent with the problem statement.

Running the same algorithm for

$$800800^{800800}$$

gives:

$$1412403576.$$

---

Answer: 1412403576