Math Is Fun Forum

  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: 25,002
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__':
    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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 25,002
Website

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?

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

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 25,002
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

Board footer

Powered by FluxBB