Am I a Sophie Germain prime? [duplicate]

Question

A Sophie Germain Prime is a prime number P such that 2P+1 is prime as well. Given a prime number as input, your task is to determine whether it is a Sophie Germain Prime.

Standard Input/Output rules and Default Loopholes apply. This is a decision-problem, so standard rules for this tag apply (returning two distinct and consistent values for each case, e.g: True/False).

---

Test Cases

Truthy (Sophie Germain primes)

These are the first few of them (OEIS A005384):

2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113

Falsy

7, 13, 17, 31, 37, 43, 47

---

Please note that answers with explanations are encouraged!

It's code-golf, hence the shortest code in bytes in every language wins!

Answer 1

x86-64 Machine Code, 24 bytes

01 FF FF C7 6A 01 59 89 F8 FF C1 99 F7 F9 85 D2 75 F5 39 F9 0F 94 C0 C3

The above code defines a function that takes a single parameter (the input value, known to be a prime) in EDI (following the System V AMD64 calling convention used on Gnu/Unix), and returns a Boolean result in AL (1 if the input is a Sophie Germain prime, 0 otherwise).

The implementation is very similar to the solution to this challenge, since all we really have to do is determine whether a number is prime using as little code as possible, which means an inefficient iterative loop.

Basically, we take the input and immediately transform it into 2 × input + 1. Then, starting with a counter set to 2, we loop through and check to see if the counter is a factor. The counter is incremented each time through the loop. As soon as a factor is found, the loop ends and that factor is compared against 2 × input + 1. If the factor is equal to the test value, then that means we didn't find any smaller factors, and therefore the number must be prime. And since we have thus confirmed that 2 × input + 1 is prime, this means that input must be a Sophie Germain prime.

Ungolfed assembly language mnemonics:

IsSophieGermainPrime:
   add   edi, edi            ; input *= 2
   inc   edi                 ; input += 1
   push  1
   pop   rcx                 ; counter = 1
   
.CheckDivisibility:
   inc   ecx                 ; increment counter
   mov   eax, edi            ; EAX = input (needs to be in EAX for IDIV; will be clobbered)
   cdq                       ; sign-extend EAX into EDX:EAX
   idiv  ecx                 ; EDX:EAX / counter
   test  edx, edx            ; check the remainder to see if divided evenly
   jnz   .CheckDivisibility  ; keep looping if not divisible by this one
   
   cmp   ecx, edi            ; compare counter to input
   sete  al                  ; set true if first found factor is itself;
   ret                       ;          otherwise, set false

Answer 2

Python,  46 43 41  40 bytes

-1 byte using code suggested elsewhere by Erik the Outgolfer (2*n+1 may be calculated as n-~n - that is, 2*n+1=n-(-1-n))

f=lambda n,p=3:p>n or(n-~n)%p*f(n,p+2)>0

A recursive function.

Returns True if the prime number input, n, is a Sophie Germain prime and False if not.

Try it online!

Works by multiplying the remainders of the division of the candidate number n-~n (which is equal to 2*n+1) after dividing by p, while p is less than n, starting at p=3 and incrementing by 2 at each iteration. This is sufficient since n is greater that the square root of 2*n+1 (n-~n) for n greater than 2. Also, since 2 is a Sophie Germain prime we can start testing with p=3 and add 2 at each iteration rather than 1. If the original n was greater than 2 the product of the resulting remainders is returned, so if the candidate has any factors the resulting 0 forces the result to be 0 too. The final >0 forces all the positive products to return True and the 0s to return False (to fulfil the "distinct and consistent" requirement).

Also beats:

...the 41 byte Python 3 (with sympy):

import sympy
lambda n:sympy.isprime(n-~n)

...and the 42 byte Python 2 full program Try It:

n=2*input()+1
p=3
while n%p:p+=2
print p<n

Answer 3

Python 2, 39 bytes

f=lambda n,k=3:n%k^k/2>0<f(n,k+2)or k>n

Try it online!

Alternate versions

f=lambda n,k=3:n%k^1>0<f(n-1,k+2)or k>n

f=lambda n,k=3:~-n%k>0<f(n-1,k+2)or k>n

f=lambda n,k=3:n%k!=1==f(n-1,k+2)or k>n

Answer 4

Mathematica , 13 bytes

PrimeQ[2#+1]&

Answer 5

CJam, 7 bytes

{2*)mp}

Try it online!

Answer 6

Pyth, 4 bytes

Almost an anagram for Pyth.

P_hy

Try it online!

Other semi-anagrams: Pt_y, P_tyh.

How?

   y   # Double
  h    # Increment
 _     # Negate
P      # Prime?

P for positive argument factorizes; to test primality one should provide the negation of the number tested.

Answer 7

MATL, 4 bytes

EQZp

Prints 1 for a Sophie Germain prime and 0 otherwise.

Try it at MATL Online

Explanation

        % Implicitly grab input as a number
E       % Multiply by 2 
Q       % Add one
Zp      % Check if this is a prime number
        % Implicitly display the result

Answer 8

05AB1E, 3 bytes

x>p

Prints 1 if the prime number input is a Sophie Germain prime, and 0 if it is not (prints 1 if double the input plus one is prime).

Try it online!

How?

x>p - implicit input: number n
x   - pop n then push n, 2*n
 >  - pop 2*n then push 2*n+1
  p - pop 2*n+1 then push is prime? (2*n+1) {True:1; False:0}
    - implicit print of top of stack

Answer 9

Python 2, 47 43 42 bytes

-4 bytes thanks to Leaky Nun. -1 byte thanks to Erik the Outgolfer.

lambda n:all((n-~n)%i for i in range(2,n))

Try it online!

Answer 10

Brachylog, 5 bytes

×₂+₁ṗ

Try it online!

Answer 11

Jelly, 4 bytes

Ḥ‘ÆP

A monadic link returning 1 if the prime number input is a Sophie Germain prime, and 0 if it is not (yields 1 if double the input plus one is prime, 0 otherwise).

Try it online!

How?

Ḥ‘ÆP - Link: number n
Ḥ    - double n
 ‘   - increment
  ÆP - is prime?

Answer 12

C, 43 bytes

i;f(x){for(x=x*2+1,i=1;x%++i;);return x>i;}

Returns 0 if x is a Sophie Germain prime, 1 otherwise.

Try it online!

C (gcc), 38 bytes

i;f(x){for(x=x*2+1,i=1;x%++i;);x=x>i;}

Try it online!

Answer 13

PHP, 39 bytes

prints 1 for true and nothing for false

for($d=$n=$argn*2+1;$n%--$d;);echo$d<2;

Try it online!

Answer 14

Neim, 3 bytes

ᚫ>𝐌

Try it online!

-1 thanks to Okx.

Answer 15

Julia 0.6, 20 bytes

x->∉(0,(x-~x)%3:x)

Answer 16

Python 2, 55 bytes:

lambda n:len(filter(lambda p:(2*n+1)%p,range(2,n)))>n-3

Python 2, 48 bytes, different logic:

lambda n:all(map(lambda p:(2*n+1)%p,range(2,n)))

Answer 17

Clojure, 60 bytes

#((fn[n](some(fn[a](=(mod n a)0))(range 2 n)))(+(* 2 %)1))

Try it online!

This is an anonymous function - to use the function, do this:

(#(...) {number}) ; This will output a value

Returns False if prime is a Sophie Germain prime, True otherwise.

Answer 18

Japt, 5 bytes

*2Ä j

Test it online! Probably won't get shorter than this...

An alternative solution which might be shorter in other languages:

¤Ä n2 j

Test it online! ¤ converts the input to binary, Ä appends a 1, and n2 converts back from base 2 (Japt doesn't have a built-in for converting from binary).

Answer 19

Pari/GP, 17 bytes

p->isprime(2*p+1)

Try it online!

Answer 20

QBIC, 7 bytes

?µ:*2+1

Explanation

?        PRINT
 µ       the result of the prime-test (-1 for true. 0 for false)
  :*2+1  with the input times 2 plus 1 as argument

Answer 21

braingasm, 8 5 bytes

;*+q:

Works like this:

;          Input a number
 *+        Double and increase it
   q:      Print 1 or 0 depending on wether the current number is prime

edit: don't need prime check on input

Answer 22

MATLAB / Octave, 18 bytes

@(x)isprime(2*x+1)

Anonymous function.

Try it online!

Answer 23

Ruby 2.3.1, 44 bytes

lambda{|p|(2...2*p+1).all?{|r|(2*p+1)%r!=0}}

Try it online!

Answer 24

C (gcc), 46 bytes

f(x,i){for(i=2;i<x;)(x-~x)%i++?:(x=i=0);x=!x;}

Try it online!

Returns 0 if SG prime, 1 otherwise.

Answer 25

Julia 0.4, 17 16 bytes

1 byte saved thanks to @Tanj

x->isprime(x-~x)

isprime was deprecated in Julia 0.5.

Answer 26

Excel VBA, 59 Bytes

Anonymous VBE immediate window function that takes input from cell [A1] to and outputs to the vbe immediate window

Must be run in a clean module or the value of j must be reset to 0 before use

n=[2*A1-1]:For i=2To n-1:j=IIf(n/i=Int(n/i),i,j):Next:?j<>0

Answer 27

,,,, 5 bytes

2×1+p

Unlike other golflangs, ,,, doesn't have builtins for incrementing and doubling because I thought I'd rather use those bytes for other things. :P

Explanation

Take input 23 for example.

2×1+p

       implicit input                      [23]
2      push 2                              [23, 2]
 ×     pop 23 and 2 and push 23 * 2        [46]
  1    push 1                              [46, 1]
   +   pop 46 and 1 and push 46 + 1        [47]
    p  pop 47 and push whether it is prime [1]
       implicit output                     []

Answer 28

cQuents, 9 bytes

#|2A+1?pz

Had to fix an interpreter bug to get this working, so no TIO link.

Explanation

#|2A+1      The last item in the input, which will become n, equals the first item 
            in the input times two, plus one.
      ?     Mode: query. Returns true if n is in the sequence, and false otherwise.
       pz   Sequence: each item is the next prime after the previous item.