Am I a Sophie Germain prime? [duplicate]

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 , 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


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

• Can I flip the True/False (i.e. output "False" if the prime is a SG prime, "True" otherwise)? Jul 9, 2017 at 12:18
• Personally, I think ir would have been best to not gusrantee primality of the input.
– Okx
Jul 9, 2017 at 13:47
• Does "returning two distinct values for each case" imply the values must be consistent rather than the tag text "either truthy or falsy" or may we return inconsistent, but if-testable, values? Jul 9, 2017 at 14:15
• You should have a set of values for truthy and their complement for falsy, if you choose to have them inconsistent. Can I define SG primes as truthy values? :P Jul 9, 2017 at 14:51
• I'm not going to vote to close because I have a dupe hammer, but this seems like it's a dupe of Is it a prime?, since the only difference is that the input isn't the number you're testing. Adding the offset (2n + 1) is a pretty trivial modification. Jul 9, 2017 at 16:33

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


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

• You do not need the brackets Jul 9, 2017 at 12:32
• 44 bytes, forgot to remove the space Jul 9, 2017 at 12:33
• @Mr.Xcoder was busy editing in for 43...I noticed :) Jul 9, 2017 at 12:34
• What is it with these weird looking recursive functions and out-golfing me... Jul 9, 2017 at 13:05
• @EriktheOutgolfer I wrote about that in the answer - the OP requests "two distinct values for each case", I had meant to ask, and have now. Jul 9, 2017 at 14:16

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

• I usually don't ask for one on Python answers... But could we have an explanation as to what is going on? Jul 9, 2017 at 18:53
• I've recreated the top solution in a more verbose way, altering some of the code but leaving the same logic. Though I'm still not quite sure why it works. Jul 10, 2017 at 6:19
• @totallyhuman If (2*n+1)%k gives 0, n%k gives either 0 or (k-1)/2. Since n is prime, n%k cannot give 0, so it suffices to check for the latter case. I'll add a more detailed explanation tomorrow. Jul 10, 2017 at 7:25

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
Zp      % Check if this is a prime number
% Implicitly display the result


Mathematica , 13 bytes

PrimeQ[2#+1]&

• TIO link? (mathics) Jul 9, 2017 at 12:17

CJam, 7 bytes

{2*)mp}


Try it online!

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.

• Why do you need to negate? Jul 9, 2017 at 12:21
• @totallyhuman P with negative argument check if -argument is prime, P with positive argument returns list of prime factors Jul 9, 2017 at 12:23
• It'd be great if you could find a way to make this an anagram of Pyth... Jul 9, 2017 at 12:47
• @daniero You're assumed prime input. Jul 9, 2017 at 12:53
• @BetaDecay I can do P_tyh (inc, double, dec) Jul 9, 2017 at 12:58

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


Python 2, 4743 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!

• Do you need to check up to 2*n+1? Jul 9, 2017 at 12:06
• (2*n+1) can be (n-~n). Jul 9, 2017 at 13:48
• @EriktheOutgolfer Oh, nice, thanks! Jul 9, 2017 at 13:49
• Basically (2*n+1) can also be (n+n+1) which can be (n+(n+1)), which in turn is the same as (n+-~n) or (n-~n). Jul 9, 2017 at 13:51

Brachylog, 5 bytes

×₂+₁ṗ


Try it online!

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?


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!

• Shave off 2 bytes by using i=1; at the start. Jul 9, 2017 at 13:48
• @G.Sliepen Thanks, but then the function would not be reusable, and therefore not a valid submission. Jul 9, 2017 at 14:29
• Suggest x-=~x instead of x=x*2+1 Jun 13, 2021 at 1:14

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!

Neim, 3 bytes

ᚫ>𝐌


Try it online!

-1 thanks to Okx.

• Neim has a 1-byte 'check for primality' token.
– Okx
Jul 9, 2017 at 13:54
• @Okx Oh I searched for it. Jul 9, 2017 at 13:58

Julia 0.6, 20 bytes

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

• Welcome to PPCG! Jul 9, 2017 at 17:33

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)))

• (2*n+1) can be replaced by (n-~n) in both versions. Jul 9, 2017 at 13:59
• Your first version can simply be lambda n:len(filter((n~-n).__mod__,range(2,n)))>n-3. Second version is essentially the same as totallyhuman's. Jul 9, 2017 at 14:01

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.

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).

Pari/GP, 17 bytes

p->isprime(2*p+1)


Try it online!

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


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

• you don't have to test input for primality Jul 9, 2017 at 12:53
• @Uriel Got it :) Jul 9, 2017 at 12:55

MATLAB / Octave, 18 bytes

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


Anonymous function.

Try it online!

Ruby 2.3.1, 44 bytes

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


Try it online!

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.

• What does GCC do with the empty "true" portion of the conditional operator? How does that get interpreted? Jul 9, 2017 at 15:46
• @CodyGray If the "true" part is empty, the value of the condition is returned instead of it. Jul 9, 2017 at 15:49
• @CodyGray Well, it's only returned to nowhere so don't worry. Jul 9, 2017 at 16:00
• Yes, I realize this is completely invalid and meaningless code that only just barely "works" if the stars are aligned just-so. I've been told that doesn't bother anyone on Code Golf, so I'm just trying my best to ignore it. I was intrigued, though, by the GCC extension with an empty "true" portion of a conditional operator, because I'd never seen that before and it wasn't immediately obvious to me how it worked. @Steadybox answered that with a reference, so much thanks! Jul 10, 2017 at 7:37

Julia 0.4, 17 16 bytes

1 byte saved thanks to @Tanj

x->isprime(x-~x)


isprime was deprecated in Julia 0.5.

• Identical to the PariGP submission... Jul 9, 2017 at 12:57
• @Mr.Xcoder polyglot then? Jul 9, 2017 at 13:02
• you can slightly reduce by computing 2*x+1 with x-~x ?
– Tanj
Jul 9, 2017 at 16:02
• 2x+1 is a bit more readable. Jul 9, 2017 at 16:44

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


,,,, 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                     []


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.

• Note current version uses Z instead of z Feb 1, 2019 at 4:51