### PROBLEM LINKS

### DIFFICULTY

EASY

### EXPLANATION

Chef’s conjecture is actually false for 127 and 351, but no other counterexamples are known. The conjecture is similar to Goldbach’s weak conjecture, which states that every odd number greater than 7 can be expressed as the sum of three odd primes. Goldbach’s weak conjecture his been conditionally proven, contingent on the Riemann hypothesis.

To solve Chef’s conjecture for small numbers, it suffices to loop through all possible values of P_{2} and P_{3}, for each value checking if N-P_{2}^{2}-P_{3}^{3} is prime. This approach can be optimized by trying large values of P_{3} first, since it’s easier to find solutions to P_{1}+P_{2}^{2} = N-P_{3}^{3} when the right hand side is small (due to the higher density of primes at lower levels).

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.