# Sum of squares of four consecutive primes [closed]

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!!

• What is your input number meant to be? The input-th prime + following three? Mar 15, 2020 at 21:46
• No. The input number is meant to be any integer between 0 and 10ˆ8. For example: 2020 = 17ˆ2 + 19ˆ2 + 23ˆ2 + 29ˆ2. In this case, 2020 is not a prime number. The code must run for any input number on the range (0 < n < 10ˆ8). Thanks!
– R.R
Mar 15, 2020 at 21:48
• And what does the input number mean? Is it the first prime of the 4 or is it the index of the first prime in the list of all primes? Mar 15, 2020 at 21:50
• The user may enter with the number, between (0 < n < 10ˆ8), and the program may return the sum of squares of four consecutive primes.
– R.R
Mar 15, 2020 at 21:52
• @RodrigoCosta : You have much to add to your Question to make it a complete description of what you want. Mar 15, 2020 at 22:04

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$$)

• I like the algorithm you propose in your first paragraph, but I think there are some typos in the second paragraph: if $n \le 10^8$, $1/2\sqrt{n} \le 0.5 \cdot 10^4$ Mar 15, 2020 at 22:22
• Thanks for helping. I'm trying to apply the tips to solve the problem.
– R.R
Mar 15, 2020 at 22:59
• Alternatively, precompute all primes in the range and perform binary search on it. There aren't that many. Mar 16, 2020 at 11:05

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...

• I tried the erastotenes way, but no success. There's a chance that i may be stupid, but i still can't see the answer by this method.
– R.R
Mar 15, 2020 at 21:59
• Thanks @RobArthan Mar 15, 2020 at 22:01

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.

• This. There are only $667$ valid inputs, so just make a list of the corresponding outputs. Mar 16, 2020 at 10:17

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.

• Thanks for helping. I'll try this.
– R.R
Mar 15, 2020 at 22:12

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$$

Hi Rodrigo !

Your problem is not consistent for all kind of numbers, take for example the number 5 which is a number between $$(0, 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.

• In this case you mentioned above, (number 5), the program will show a message saying isn't possible to be written that way. But, i think the problem is consistent, because 2020, for example, can be written as follows: 2020 = 17ˆ2+19ˆ2+23ˆ2+29ˆ2. It seems that 87 (as shown above) is the smallest number that can be represented by this method (by this table: "oeis.org/A133524/b133524.txt"). Anyway, the program instruction given by the teacher is for the program to accept the mentioned range. It is quite a complicated problem for who is starting to learn C language, unfortunately.
– R.R
Mar 15, 2020 at 22:54
• I'm trying to find an algebraic expression that i can convert to C language. Functions, matrix, vectors and stuff isn't allowed to use in this program. Only basics: while, fors, ifs and basic main() stuff. Thanks for helping. I'm trying to understand all replies and work on them.
– R.R
Mar 15, 2020 at 22:56
• @R.R You do not mention this in your original question. Mar 16, 2020 at 11:00
• Tiago, thank you for helping, for spending your time writing the code, it's just amazing your will to help me out. I tried to run this code to understand its behavior but i had no success using PyCharm IDE. My Python's knowledge is zero. I'm actually beginning in C language. I'm not taking your time anymore, but thank you, sincerely! If it happens for you to have some time, please, would help me a lot if you try to explain me the "algorithm" behind the python code you created. Thanks again!!
– R.R
Mar 17, 2020 at 2:26