Detailed mathematical approach

Problem Summary

A hybrid integer is a number of the form \(p^q q^p\) where \(p\) and \(q\) are distinct primes. By unique factorization, two different prime pairs cannot produce the same number, so counting hybrid integers up to \(B^E\) is equivalent to counting prime pairs \(p<q\) such that

$p^q q^p \le B^E.$

The target input is \(B=800800\) and \(E=800800\). Direct evaluation of the powers is completely impractical, so the solution converts the inequality into a logarithmic comparison and then counts valid prime pairs with a monotone sweep.

Mathematical Approach

Define

$H(B,E)=\#\{(p,q): p<q,\ p^q q^p \le B^E\},$

where \(p\) and \(q\) are prime. The problem is to compute \(H(800800,800800)\).

Step 1: Reduce the Condition to a Prime-Pair Inequality

Because every hybrid integer is determined by its two prime bases, we can work directly with ordered pairs \(p<q\). There is no need to build the integer \(p^q q^p\) itself. We only need to decide whether the pair lies below the threshold \(B^E\).

This turns the original number-theoretic question into a comparison problem on prime pairs. Once a pair \((p,q)\) is accepted, it contributes exactly one hybrid integer.

Step 2: Linearize the Inequality with Logarithms

Let

$\Lambda = E\ln B.$

Since the natural logarithm is strictly increasing on positive numbers,

$p^q q^p \le B^E \iff \ln(p^q q^p)\le \ln(B^E).$

Using \(\ln(a^b)=b\ln a\), this becomes

$q\ln p + p\ln q \le \Lambda.$

This is the key transformation used by the implementations: enormous powers disappear, replaced by a sum of two moderate logarithmic terms.

Step 3: Derive a Finite Prime Search Range

Every admissible pair satisfies \(p\ge 2\), so \(\ln p \ge \ln 2\). Therefore

$q\ln 2 \le q\ln p \le q\ln p + p\ln q \le \Lambda.$

Hence any valid right prime must satisfy

$q \le \frac{\Lambda}{\ln 2}.$

So it is sufficient to generate all primes up to a bound of the shape

$Q=\left\lfloor\frac{\Lambda}{\ln 2}\right\rfloor + O(1).$

The small constant cushion used in practice is only there to absorb truncation and floating-point edge effects; mathematically, the search interval is already determined by the inequality above.

Step 4: Use Monotonicity to Get a Two-Pointer Count

Fix a prime \(p\), and consider

$f_p(x)=x\ln p + p\ln x \qquad (x>1).$

Its derivative is

$f_p'(x)=\ln p + \frac{p}{x} > 0,$

so \(f_p(x)\) is strictly increasing. That means that for a fixed left prime \(p\), the admissible right primes \(q\) form an initial segment of the prime list: once the inequality fails for some \(q\), it fails for all larger primes as well.

There is a second monotonicity. For a fixed right prime \(q\), the quantity

$g_q(x)=q\ln x + x\ln q$

also increases with \(x\), since

$g_q'(x)=\frac{q}{x}+\ln q > 0.$

Therefore, as the left prime moves forward through the sorted prime list, the largest valid right prime can only stay where it is or move left. This is exactly why one descending right pointer is enough for the whole count.

Step 5: Why Each Left Prime Contributes a Contiguous Block

Suppose the primes are \(r_0<r_1<\dots<r_{m-1}\). For a fixed index \(i\), let \(j\) be the largest index with \(i<j\) and

$r_j\ln r_i + r_i\ln r_j \le \Lambda.$

Then every prime \(r_k\) with \(i<k\le j\) is also valid, and every \(r_k\) with \(k>j\) is invalid. So the contribution of the left prime \(r_i\) is exactly

$j-i.$

Summing these contiguous block lengths over all left indices counts every admissible pair exactly once.

Worked Example: \(B=800\), \(E=1\)

Here

$\Lambda=\ln 800.$

The bound for the larger prime is

$q\le \frac{\ln 800}{\ln 2}=\log_2 800 < 10,$

so we only need the primes \(2,3,5,7\).

Now test the possible pairs:

$\begin{aligned} (2,3)&:&3\ln 2 + 2\ln 3 = \ln(72) \le \ln(800),\\ (2,5)&:&5\ln 2 + 2\ln 5 = \ln(800),\\ (2,7)&:&7\ln 2 + 2\ln 7 = \ln(6272) > \ln(800),\\ (3,5)&:&5\ln 3 + 3\ln 5 = \ln(6075) > \ln(800). \end{aligned}$

All remaining pairs are even larger, so the only hybrid integers not exceeding \(800\) are

$2^3 3^2 = 72,\qquad 2^5 5^2 = 800.$

Thus \(H(800,1)=2\), matching the small checkpoint used by the implementations.

How the Code Works

The C++, Python, and Java implementations follow the same pipeline. First they compute \(\Lambda=E\ln B\) in floating point and derive a safe upper limit slightly above \(\Lambda/\ln 2\). Then they generate every prime up to that limit with a sieve of Eratosthenes.

Next they precompute \(\ln p\) once for each prime so the inner comparison never recalculates logarithms. After that, they place one pointer at the beginning of the prime list and another at the end. For each left prime, the right pointer moves left until the inequality \(q\ln p + p\ln q \le \Lambda\) becomes true. At that moment, all primes between the two pointers form valid pairs with the chosen left prime, so the implementation adds the size of that block to the answer.

Because the right pointer only moves in one direction, the counting pass is linear in the number of generated primes. A tiny numerical tolerance is included in the comparison so that boundary cases representing exact equality are not lost to floating-point rounding.

Complexity Analysis

Let

$Q=\left\lfloor\frac{\Lambda}{\ln 2}\right\rfloor + O(1).$

Generating all primes up to \(Q\) by sieve costs \(O(Q\log\log Q)\) time and \(O(Q)\) memory. Precomputing the logarithms costs \(O(\pi(Q))\) time and memory proportional to the prime list. The two-pointer sweep is \(O(\pi(Q))\), because the left pointer visits each prime once and the right pointer can only move left across the list once.

Therefore the overall running time is

$O(Q\log\log Q),$

with linear memory

$O(Q).$

Footnotes and References

1. Problem page: https://projecteuler.net/problem=800
2. Prime numbers: Wikipedia — Prime number
3. Natural logarithm: Wikipedia — Natural logarithm
4. Sieve of Eratosthenes: Wikipedia — Sieve of Eratosthenes
5. Fundamental theorem of arithmetic: Wikipedia — Fundamental theorem of arithmetic