Math Is Fun Forum
You are not logged in.
- Topics: Active | Unanswered
#101 2014-11-04 05:38:32
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?
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__':
T = int(sys.stdin.readline())
for _ in range(T):
N, K = list(map(int, sys.stdin.readline().split()))
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
Re: Sum of R primes?
Logic please?
'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?
Logic please?
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
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