Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫  π  -¹ ² ³ °

You are not logged in.

## #101 2014-11-04 05:38:32

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,858
Website

### Re: Sum of R primes?

I do not know what overextended means but it is okay.

'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

## #102 2014-11-04 05:45:30

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

### Re: Sum of R primes?

It means I am stretched too thin. I will help you if you need help.

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

## #103 2014-11-04 07:29:33

ShivamS
Member
Registered: 2011-02-07
Posts: 3,648

### Re: Sum of R primes?

Agnishom wrote:

Does Goldbach help?

This code uses the Rabin-Miller algorithm and Goldbach conjecture

I believe that this solution works (it is in Python 3)

``````import math, random, sys

def is_probable_prime(n, k = 7):

if n < 6:
return [False, False, True, True, False, True][n]

elif n & 1 == 0:
return False

else:
s, d = 0, n - 1

while d & 1 == 0:
s, d = s + 1, d >> 1

for a in random.sample(range(2, n - 2), min(n - 4, k)):
x = pow(a, d, n)

if x != 1 and x + 1 != n:
for r in range(1, s):
x = pow(x, 2, n)

if x == 1:
return False
elif x == n - 1:
a = 0
break

if a:
return False

return True

if __name__ == '__main__':

for _ in range(T):

if N < 2 * K:
print('No')

elif K == 1:
print('Yes' if is_probable_prime(N) else 'No')

elif K == 2:
if N % 2 == 0:
print('Yes')
else:
print('Yes' if is_probable_prime(N - 2) else 'No')

else:
print('Yes')``````

Last edited by ShivamS (2014-11-04 07:35:59)

Offline

## #104 2014-11-04 12:46:34

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,858
Website

### Re: Sum of R primes?

'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

## #105 2014-11-04 14:17:31

ShivamS
Member
Registered: 2011-02-07
Posts: 3,648

### Re: Sum of R primes?

Agnishom wrote:

Assume that the Goldbach conjecture is true (to the limit in the problem).

Now, break it into cases:

N < 2K: The answer is “No”, because the sum of K primes is at least 2K.
N ≥ 2K and K = 1: The answer is “Yes” if N is prime, and “No” otherwise.
N ≥ 2K, K = 2 and N is even: The answer is “Yes” (by Goldbach’s conjecture).
N ≥ 2K, K = 2 and N is odd: The answer is “Yes” if N − 2 is prime, and “No” otherwise. This is because the sum of two odd primes is even, and the only even prime number is 2, so one of the prime numbers in the sum must be 2.
N ≥ 2K and K ≥ 3: The answer is “Yes”. This is because if N is even, then N − 2(K − 2) is also even, so it is the sum of two primes, say p and q (by Goldbach’s conjecture). Thus, N is the sum of the K primes 2, 2, 2, ..., p, q. And if N is odd, then N − 3 − 2(K − 3) is even, so it is the sum of two primes, say p and q. Thus, N is the sum of the K primes 3, 2, 2, ..., p, q.

Last edited by ShivamS (2014-11-05 01:40:52)

Offline

## #106 2014-11-04 19:39:36

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,858
Website

### Re: Sum of R primes?

N ≥ 2K and K ≥ 3: The answer is “Yes”. This is because if N is even, then N − 2(K − 2) is also even, so it is the sum of two primes, say p and q (by Goldbach’s conjecture). Thus, N is the sum of the K primes 2, 2, 2, ..., p, q. And if N is odd, then N − 3 − 2(K − 3) is even, so it is the sum of two primes, say p and q. Thus, N is the sum of the K primes 3, 2, 2, ..., p, q.

That is excellent. Thanks!

'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline