Project Euler Problem 87 Statement

The smallest number expressible as the sum of a prime square, prime cube, and prime fourth power is $28$. In fact, there are exactly four numbers below fifty that can be expressed in such a way:

How many numbers below fifty million can be expressed as the sum of a prime square, prime cube, and prime fourth power?

Solution

Project Euler Problem 87 overview:

How many numbers below a given limit can be expressed as the sum of a prime square, prime cube, and prime fourth power? Specifically, for a number \( N \), find all distinct numbers of the form \( p^2 + q^3 + r^4 \) where \( p, q, r \) are prime numbers and \( p^2 + q^3 + r^4 \leq N \).

Code Breakdown

Let's dissect the provided Python code to see how it addresses this problem.

import math, bisect, itertools, Euler

for _ in range(int(input())):
    print(bisect.bisect_left(pq, int(input()) + 1))	

1. Importing Necessary Modules

import math, bisect, itertools, Euler

math: Provides mathematical functions, such as isqrt for integer square roots.
bisect: Offers efficient binary search functions, crucial for quickly counting valid sums.
itertools: Facilitates efficient iteration, especially for generating Cartesian products.>br> Euler: The prime_sieve() function.

2. Generating Valid Sums

pq = sorted({c**4 + b**3 + a * a for a, b, c in 
    itertools.product(Euler.prime_sieve(3162), Euler.prime_sieve(215), Euler.prime_sieve(56))})

Objective: Compute all possible sums of the form \( p^2 + q^3 + r^4 \), where \( p, q, r \) are primes within specific ranges.

Determining Sieve Limits:

• Primes for \( p^2 \):

  \( p^2 \leq N \) implies \( p \leq \sqrt{N} \). The sieve limit 3162 is chosen based on the maximum expected \( N \) (e.g., \( N \leq 10^{12} \)), since \( \sqrt{10^{12}} = 10^6 \), but considering practical constraints, 3162 is sufficient for the problem's limits.

• Primes for \( q^3 \):

  \( q^3 \leq N \) implies \( q \leq N^{1/3} \). The sieve limit 215 covers primes up to \( 215 \), since \( 215^3 \approx 9.94 \times 10^6 \).

• Primes for \( r^4 \):

  \( r^4 \leq N \) implies \( r \leq N^{1/4} \). The sieve limit 56 covers primes up to \( 56 \), since \( 56^4 = 9,834,496 \).

Using itertools.product:

Generates all possible combinations of primes \( (p, q, r) \) from the three sieve lists.

• Calculating Sums: For each combination, compute \( r^4 + q^3 + p^2 \).
• Using a Set {}: Ensures all sums are unique, eliminating duplicates automatically.
• Sorting the List: The sorted function organizes all unique sums in ascending order, facilitating efficient binary search operations later.

3. Handling Multiple Test Cases

for _ in range(int(input())):
    print(bisect.bisect_left(pq, int(input()) + 1))	

Input Handling:

• The program first reads an integer indicating the number of test cases.
• For each test case, it reads the limit \( N \).

Counting Valid Sums:

bisect.bisect_left(pq, N + 1):

• Performs a binary search to find the insertion point for \( N + 1 \) in the sorted list pq.
• This effectively counts the number of sums \( \leq N \) because bisect_left returns the index where \( N + 1 \) would be inserted to keep the list sorted.

Output:

• Prints the count of valid sums for each test case.

Example Walkthrough

Suppose we have a test case with \( N = 50 \):

1. Prime Lists:
   • \( p \) primes (up to 3162): [2, 3, 5, 7, ...]
   • \( q \) primes (up to 215): [2, 3, 5, 7, ...]
   • \( r \) primes (up to 56): [2, 3, 5, 7, ...]
2. Compute Sums:
   • For each combination \( (p, q, r) \), calculate \( p^2 + q^3 + r^4 \).
   • Example: \( 2^2 + 2^3 + 2^4 = 4 + 8 + 16 = 28 \).
   • Collect all such sums \( \leq 50 \).
3. Store and Sort:
   • Unique sums: {28, 33, 38, 35, ...}
   • Sorted list pq: [28, 33, 35, 38, ...]
4. Binary Search:
   • bisect.bisect_left(pq, 51) returns the count of sums \( \leq 50 \).
5. Output:
   • The number of valid sums below or equal to 50 is printed.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 87

HackerRank Project Euler 87: Given an integer $N$, $(1\le N\le 10^7)$, Find out how many numbers less than or equal to $N$ are there that can be expressed as a sum of a prime square, prime cube and prime fourth power.