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

You are not logged in.

- Topics: Active | Unanswered

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

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

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

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

Agnishom wrote:

Does Goldbach help?

This code uses the Rabin-Miller algorithm and Goldbach conjecture

Agnishom wrote:

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

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

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

Agnishom wrote:

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

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