Sum of squares of four consecutive primes

Question

I need to create a C code for a sum of square of four consecutive primes, for an input number between 0 and 10ˆ8. However, i can't find a general formula to do this.

For example: the user input for 87 and 204, the program returns the sum of squares of four consecutive primes as result.

             87 = 2ˆ2 + 3ˆ2 + 5ˆ2 + 7ˆ2

             204 = 3ˆ2 + 5ˆ2 + 7ˆ2 + 11ˆ2

If the number couldn't be written as a sum of squares of four consecutive primes, the program may return a message saying isn't possible. Any help is appreciated. Thanks!!

Answer 1

A very naive way would be to use the sieve of eratosthenes (I think its called that way) to enumerate all primes up to $\sqrt{\text{input}/2}$ and check any four consecutive primes if their sum of squares matches the input...

Answer 2

If there is a solution then it will usually be of the form N = p1^2 + p2^2 + p3^2 + p4^2, where p1 and p2 are the first two primes smaller than Sqrt(N)/2, and p3 and p4 are the first two primes larger than Sqrt(N)/2.

This should always be the case for larger N. For smaller N you may also need to test three primes smaller than Sqrt(N)/2 and one larger or one smaller and three larger.

Answer 3

If $n$ is the sum of the squares of four consecutive primes, then the biggest of the four primes is $>\frac12\sqrt{n}$ and the smallest is $<\frac12\sqrt n$. So look for the next three primes $\ge \frac12\sqrt n$ and the previous three primes $<\frac12\sqrt n$. Among these six primes, try all consecutive quadruples.

Now for the underlying problem of finding primes near $\frac12\sqrt n$, note that this number $\le 5\cdot 10^8$, so detecting primeness is easy - for example by trial division against a prepared table of the $2503$ primes $\le 22367$ (which is certainly enough because the third prime after $5\cdot 10^8$ is not larger than $5\cdot 10^8+41$)

Answer 4

Hi Rodrigo !

---

Your problem is not consistent for all kind of numbers, take for example the number 5 which is a number between $(0<n<1.0*10ˆ8)$, it can't unfortunately be written as sum of squared prime numbers.

---

But if your main objective is only doing for the cases that this actually work I would create a list of prime numbers with a function that I would call prime_generator() and square those numbers and then append those numbers into a list, until the square of the number that you are appending is larger than your input. Then I would create a function that would iterate trough the list of prime squared numbers an try all the combinations of possible sums (this could be a really big problem in terms of optimisation) that would result on your input. When the sum was discovered the program would stop and would give you the actually prime squared numbers that you are looking for.

---

vetor = int(input())
primes = [x for x in range(2,5100) if not [t for t in range(2,x) if not x%t]]  #prime_generator

square_primes = [i**2 for i in primes]

soma = []

for i in range(0,len(square_primes)):
   try:
      soma.append(square_primes[i]+square_primes[i+1]+square_primes[i+2]+square_primes[i+3])
except:
       break

if vetor in soma:
    print(vetor, '=' , primes[soma.index(vetor)],"ˆ2" ,'+', primes[soma.index(vetor)+1],"ˆ2" ,'+',primes[soma.index(vetor)+2],"ˆ2",'+',primes[soma.index(vetor)+3],"ˆ2")
else:
    print("This number can't be expressed in these conditions")

---

I made this code in Python 3.7 to you !

---

Hope this helps.

---

Answer 5

If you are going to compute a list of primes then you may as well also compute a list of sums of 4 consecutive primes at compile time. Then just binary search the second list (or use a hashmap prime to index) and reverse index into the first one.

Answer 6

the square of an odd number is $1 \pmod 8.$ Once the input exceeds 87, the only possibilities for a positive outcome are those $n$ with $$ n \equiv 4 \pmod 8 $$

Note that $204 = 8 \cdot 25 + 4$