Sophie Safe primes

Description

Write a program or function that takes in a positive integer $$\n\$$ as input and outputs all Sophie Germain primes that are safe primes less than or equal to $$\n\$$. A prime number $$\p\$$ is a Sophie Germain prime if $$\2p+1\$$ is also a prime. A prime number $$\p\$$ is a safe prime if $$\p=2q+1\$$, where $$\q\$$ is also a prime. The output should be a list of the Sophie Germain primes that are also safe primes, in ascending order only.

Test Cases

[20] => 5, 11
[10000] => 5, 11, 23, 83, 179, 359, 719, 1019, 1439, 2039, 2063, 2459, 2819, 2903, 2963, 3023, 3623, 3779, 3803, 3863, 4919, 5399, 5639, 6899, 6983, 7079, 7643, 7823
[1000] => 5, 11, 23, 83, 179, 359, 719


Output primes $$\p\$$ such that both $$\\frac{p-1}{2}\$$ and $$\2p+1\$$ are prime less then, equal to a specific $$\n\$$ given in input. Shortest bytes answer will win, in case if bytes are equated, a tie will occur.

• This is A059455. Mar 9 at 9:38
• Please consider using standard sequence I/O rules for future challenges. Mar 9 at 10:40
• @Arnauld But they don't allow for the "all terms whose value does not exceed n" outputs...
– Neil
Mar 9 at 14:06
• @Neil True. Maybe that should be added? (But that question belongs to codegolf.meta.) Mar 9 at 14:38

Japt-f, 10 bytes

[UUÑÄUz]ej


Try it

Wolfram Language (Mathematica), 46 bytes

Select[Range@#,And@@PrimeQ@{#,(#-1)/2,2#+1}&]&


Try it online!

R, 71 bytes

f=\(n)if(n>4)c(f(n-1),n[all(Map(\(y)sum(!y%%2:y)<2,(n+1)*2^(-1:1)-1))])


Attempt This Online!

Heavily inspired by @Dominic van Essen's answer to Imtiaz Germain Primes.

05AB1E, 10 bytes

Lʒx>y2÷)pP


Try it online.

Explanation:

L       # Push a list in the range [1, (implicit) input-integer]
ʒ      # Filter it by:
x     #  Double the current value (without popping)
>    #  And increase it by 1
y     #  Push the current value again
2÷   #  Integer-divide it by 2
)     #  Wrap all three values into a list: [n,2n+1,(n-1)/2]
p    #  Check for each whether it's a prime number
P   #  Check if all three are truthy
# (after which the filtered list is output implicitly as result)

• Tested on ATO and it doesn't appear to work without the §. Mar 9 at 11:53
• @Shaggy Ah ok. Thanks for the confirmation. Then I'll report it as a bug later today. :) Mar 9 at 13:01
• Does 05AB1E have floor division? If so, could you save anything by floor dividing by 2 instead? Mar 9 at 13:04
• @Shaggy I already did when I made my reply to you. ;) I noticed that integer-dividing by 2 was a shorter alternative when I made my Java answer. Mar 9 at 13:54

Vyxal, 10 bytes

':d›n‹½WæA


Try it Online!

Ports japt. Quite literally get all numbers where n, 2n incremented, and n decremented halved are all prime. Here's a more fun 11 byter

Vyxal, 11 bytes

~æ~≬‹½æ'd›æ


Try it Online!

Explained

~æ~≬‹½æ'd›æ
~æ          # keep only from range [1, input] where prime
~≬---     # from that, keep where:
‹½       #   (n - 1) / 2
æ      #   is prime
'     # from that, keep where:
d›   #   2n + 1
æ  #   is prime


Java 8, 117 115 bytes

i->{for(;i-->5;)if(p(i)&p(i-~i)&p(i/2))System.out.println(i);};boolean p(int i){int k=i;for(;i%--k>0;);return k<2;}


Outputs each Sophie Safe prime on a separated newline in reversed order.
Based on my answer for the Imtiaz Germain Primes challenge.

Try it online.

Explanation:

i->{                          // Method with integer parameter and no return-type
for(;i-->5;)                //  Loop i in the range (input,5]:
if(p(i)                   //   If i is a prime number
&p(i-~i)               //   and 2i+1 is a prime number
&p(i/2))               //   and i integer-divided by 2 is a prime number:
System.out.println(i);} //    Print i with trailing newline

// Separated method with integer parameter and boolean return-type,
// to check whether the given number (≥2) is a prime number
boolean p(int i){
int k=i;                    //  Set k to the given integer i
for(;i%--k>0;);             //  Decrease k before every iteration with --k
//  Keep looping as long as i is NOT divisible by k
return k<2;}                //  After the loop, check and return whether k is 1,
//  which means it's a prime number


JavaScript (ES6), 71 bytes

f=p=>p>4?f(p-1)+[[,p+' '][(P=x=>p%--x?P(x):x)(p)*P(p-=~p)*P(p>>=2)]]:''


Try it online!

Commented

f = p =>         // recursive function taking a prime candidate p
p > 4 ?          // if p is greater than 4:
f(p - 1) +     //   do a recursive call with p - 1
[[, p + ' '][  //   append p followed by a space iff the following
//   result is 1:
( P = x =>   //     helper recursive function taking x
p % --x ?  //     decrement x; if x is not a divisor of p:
P(x)     //       do recursive calls until it is
:          //     else:
x        //       return x (smallest proper divisor of p)
)(p) *       //     first call with p
P(p -= ~p) * //     second call with 2p + 1
P(p >>= 2)   //     third call with floor((2p + 1) / 4) which is
//     (p - 1) / 2 if p is odd
//   the product is 1 iff all calls return 1,
]]             //   i.e. all tested numbers are prime
:                // else:
''             //   stop


Thunno+, $$\ 16 \log_{256}(96) \approx\$$ 13.17 bytes

gzt2*1+s2,ZPsTNP


Attempt This Online!

Explanation

gzt2*1+s2,ZPsTNP  # Implicit input
g                 # Filter [1..input] by the following:          n
zt               #  Triplicate the number                       n, n, n
2*1+           #  Multiply by two and add one                 n, n, 2n+1
s2,        #  Swap and integer divide by two              n, 2n+1, n//2
ZP      #  Pair the top two items                      n, [2n+1, n//2]
sT    #  Swap and append to the list                 [2n+1, n//2, n]
NP  #  Are they all prime?


Raku, 41 bytes

{grep {is-prime $_&2*$_+1&$_/2-.5},1..$_}


Try it online!

This filters (greps) the numbers from 1 to the input argument to those where the conjunction (&) of the number ($_), twice that number plus one (2 *$_ + 1) and half the number minus one half ($_ / 2 - .5) is prime. The conjunction is prime if all of its elements are. J, 28 bytes [:I.1*/@p:i.>:@+:^:_1 0 1@,]  Attempt This Online! i.,] Integers from 0 to n. >:@+: Function f that computes i -> 1+2*i. f^:_1 0 1 Apply f -1 times (inverse), 0 times, and 1 time and collect results in a 3-row matrix. 1 p: For each integer, is it prime? */ Take the product of each column. I. Indices of 1s in the resulting vector. Excel, 118 bytes =LET( a,SEQUENCE(2*A1+1), b,IF(MMULT(N(MOD(a,TOROW(a))=0),a^0)=2,a), FILTER(b,1-ISNA(XMATCH(2*b+1,b)*XMATCH((b-1)/2,b))) )  Fails where A1>3663. Retina 0.8.2, 75 bytes .+$*

¶11$$
4A
A^(11+)\1+$1(1?)$1
A^(11+)\1+$A^1((11+)\2+)\1$
%1


Try it online! Link is to verbose version of code. Explanation: Based on my Retina answer to Imtiaz Germain Primes.

.+
$*  Convert to unary.  ¶11$$  Generate all numbers of the form 2n+1 up to the input. Due to golfing, the last entry is not odd, so I have to add 2 to each value so that the final odd entry is 2n+1. (Although, the non-golfy way only goes up to 2n-1 so wouldn't work anyway.) 4A  Deleting composite numbers won't work when the number to be tested is 0 or 1 so delete the small numbers manually. A^(11+)\1+$


Delete the remaining non-prime numbers.

1(1?)
$1  Integer divide by 2. A^(11+)\1+$


Delete all composite numbers.

A^1((11+)\2+)\1$ Delete all numbers that are 1 more than 2 times a composite number. %1  Convert the results to decimal. Charcoal, 26 bytes Ｉ⊕⊗Φ…²⊘⊕Ｎ⬤⊖×⊕ιＥ³Ｘ²λ⬤…²λ﹪λν  Try it online! Link is to verbose version of code. Explanation:  … Range from ² Literal integer 2 to Ｎ Input integer ⊕ Incremented ⊘ Halved Φ Filtered where ³ Literal integer 3 Ｅ Map over implicit range ² Literal integer 2 Ｘ Raised to power λ Inner value × Vectorised multiply by ι Outer value ⊕ Incremented ⊖ Vectorised decrement ⬤ All values satisfy … Range from ² Literal integer 2 λ To inner value ⬤ All values satisfy λ Inner value ﹪ Modulo i.e. is not a multiple of ν Innermost value ⊗ Vectorised double ⊕ Vectorised increment Ｉ Cast to string Implicitly print  Excel (ms365), 146 bytes =LET(x,SEQUENCE(A1*2+1),y,MAP(x,LAMBDA(z,SUM(--((z/x)=INT(z/x)))))=2,q,FILTER(x,y),FILTER(q,MAP(q,LAMBDA(p,SUM(--(q=(p-1)/2))*SUM(--(q=2*p+1))))))  EDIT: Since the above is rather slow (thought should work for all given samples), I was looking for ways to gain more speed. Just for fun, I created my own LAMBDA() based function called 'a' within Excel's name-manager based on one of the more simplistic ways to generate prime numbers; the Sieve of Eratosthenes: =LAMBDA(x,y,z,IF(x=MAX(y),SORT(y),a(SMALL(y,z),FILTER(y,MOD(y,x)+(y=x)),z+1)))  Now, since we can output all primenumbers, we can call this on the worksheet and do some filtering on the output: =LET(q,a(2,SEQUENCE(A1*2,,2),1),FILTER(q,MAP(q,LAMBDA(p,SUM(--(q=(p-1)/2))*SUM(--(q=2*p+1))))))  The combined byte-count == 173, but it is working faster then the original answer of 146 bytes. This makes me wonder if I, or someone, else can come up with ways to implement other known ways of generating primes and gain more speed. • =LET(a,SEQUENCE(2*A1+1),b,IF(MMULT(N(MOD(a,TOROW(a))=0),a^0)=2,a),FILTER(b,1-ISNA(XMATCH(2*b+1,b)*XMATCH((b-1)/2,b)))) is 118 bytes, though your version might be able to cope with an input of 10000 (although looking doubtful on my machine). Mar 9 at 12:16 • @JosWoolley, I did get a result using my (unfortunately more verbose) version. Your version gave me an error pop-up. – JvdV Mar 9 at 12:22 • Nice implementation of the Sieve of Eratosthenes! I just wonder whether the recursion limit for LAMBDAs will mean that this set-up is too restrictive? I understand that limit is 1024/x, where x is the number of parameters passed to LAMBDA. Since you're passing three parameters here, I presume that means a maximum of 341 iterations. Not sure how that translates into an upper bound on the largest integer parsable, though. Mar 9 at 16:29 • @JosWoolley would be interesting to test, I've only tried the upperbound as 10000*2, which worked relatively fast. – JvdV Mar 9 at 17:12 • @JosWoolley, FYI the ubound happened to be n == 19432 =). I did expect more of this.. – JvdV Mar 9 at 19:13 Factor + math.primes, 63 bytes [ primes-upto [ dup 2/ swap 2 * 1 + [ prime? ] both? ] filter ]  Try it online! • primes-upto get a list of primes up to the input • [ ... ] filter select $$\p\$$ where... • dup 2/ $$\\lfloor{p/2}\rfloor\$$ • swap 2 * 1 + and $$\2p+1\$$ • [ prime? ] both? are both prime Arturo, 45 bytes $=>[select..1&'n[every?@[1+n*2n/2n]=>prime?]]


Try it

$=>[ ; a function select..1&'n[ ; select numbers from 1 to <input>, assign current elt to n every? ; is every element in the block... @[1+n*2n/2n] ; ... [n/2, n, n*2+1] (where / is integer division) =>prime? ; prime? ] ; end select ] ; end function  Jelly, 16 bytes ÆRḤ‘$ÆP$Ƈ’H$ÆP$Ƈ  Try it online! ÆR - list of prime numbers up to the input Ḥ‘ - 2x+1$ÆP$Ƈ - evaluates as primes ’H - (x-1)/2$ÆP\$Ƈ - evaluates as primes (again)
`