Imtiaz Germain Primes

Description

"Imtiaz Germain primes" is not a technical name in Mathematics, but my weird creation, in the memoir of the famous mathematician Sophie Germain. These primes can be generated by the following process:

1. Take a Safe prime
2. Apply 2p + 1 on it to obtain a composite number
3. Apply 2p + 1 once more to obtain a prime number


The idea can be further illustrated in the example.

Example

We check if 3 is a Sophie Germain prime. It has a safe prime 7 using 2p+1 so 3 is a Sophie Germain prime and can/cannot be an Imtiaz Germain prime. We take the safe prime, apply 2p+1 on it, and get 15 which must be composite according to the second step of the description, applying the same, we must get a prime next, which is 31 so 3 is an Imtiaz Germain prime. All Imtiaz Germain primes below 100M are available in Chapter 1 of the book I wrote here.

Write a program, which inputs any number, and mentions all Imtiaz Germain primes below the number. As long as fulfills the full output, you may output the Imtiaz Germain primes in reversed order. Since it is code golf, the shortest code in bytes win, if bytes are equated then the earliest posted program wins.

Test Cases

10 => 3
1500 => 3 23 29 53 113 233 293 419 593 653 659 683 1013 1103 1223 1439
10000 => 3 23 29 53 113 233 293 419 593 653 659 683 1013 1103 1223 1439 1559 1583 1973 2039 2273 2339 2549 2753 3299 3359 3593 3803 3863 4019 4409 4733 4793 4919 4943 5003 5279 5639 6173 6263 6269 6323 6563 6983 7433 7643 7823 8243 8273 8513


Thanks to Aira for writing this task for me, I am clearly unaware of how to write still. The following task is written to celebrate my first time beating 1k on a SE Network, and to fighting autism. And to someone... who is my entire life, to Sophie Germain, people say I am suffering hallucinations to see her, it is my love for her that I hallucinate her

• I read your book, it was integeresting :) Mar 5 at 12:09
• People say me it is crap, like I have a physical book here (people say it is crap, generated or not interesting and I heard it is integeresting), anyways this comment is a whole world for me despite of the fact the society really doesn't entertain me much because of my autistic trait :) anyways thank you so so...(to infinity) much! Mar 5 at 12:50
• May we output the Imtiaz Germain primes in reversed order? Mar 5 at 16:17
• yes, as long as they fulfill the full output, descending order is unique but allowed as the aim is just to output them only Mar 5 at 16:29

05AB1E, 14 13 bytes

ÅPʒ>3Lo*<pāÉQ


Try it online!

-1 thanks to @Kevin Cruijssen

I found a bunch of different ways for 14 bytes, but I can't find any 13 bytes solution ):

Lʒ>3Ýo*<pā3ÊQ
ÅPʒ>3Lo*<pJC5Q
ÅPʒ>3Lo*<pJƵ0Q
ÅPʒ>3Lo*<p2β5Q
ÅPʒ>3Lo*<p3LÉQ
ÅPʒ>3Lo*<pā+ÈP
Lʒ>3Ýo*<pJC13Q
Lʒ>3Ýo*<p2β13Q
Lʒ>3Ýo*<pJŽ4ιQ
Lʒ>3Ýo*<p4L3ÊQ


Explanation

ÅP         generate all primes up to (and including) the input number
ʒ          only keep those such that
>          p+1
3L         the list [1, 2, 3]
o          2^[1, 2, 3] = [2, 4, 8]
*          times p+1 = [2p+2, 4p+4, 8p+8]
<          -1 = [2p+1, 4p+3, 8p+7]
p          is prime
ā          length range, [1, 2, 3]
É          is odd? [1, 0, 1]
Q          equal to the results of is prime

• The last four bytes could be āÉQ for a 13-byter. :) I haven't been able to find anything shorter for the >3Lo*<, although >·xx)< or >Ƶ“S*< are some more alternatives. Mar 5 at 15:13

Vyxal, 13 12 bytes

'‡d›↔4ẎæB13=


Try it Online!

If I've understood the challenge correctly, for a number to be Imtiaz Germain, it has to first be prime, and applying 2p+1 3 times must produce the required pattern. Hence, the list [p, 2p + 1, 2(2p + 1) + 1, 2((2(2p + 1) + 1) + 1)] must equal [1, 1, 0, 1], which is 13 when converted from binary.

Accidentally the same algorithm as Jelly, which was posted while I was writing the explanation :p

Explained

'‡d›↔4ẎæB13=
'             # From the range [1, input], keep numbers N where:
4Ẏ       #   the first 4 items of
‡d›↔         #   applying lambda x: 2 * x + 1 until fixed-point (yes it's infinite, but lazy evaluation means it doesn't get stuck here)
æ      #   tested for primality
B     #   converted from binary
13=  #   equals 13. This works for the reason explained in the introduction.

• Comment Deleted above, because you are right but your program does not outputs all numbers. Mar 5 at 3:56
• Sorry @lyxal you are right, i really read the explanation as if if I were ishowspeed Mar 5 at 3:57
• @AitzazImtiaz do you mean it times out before printing all numbers? Mar 5 at 3:57
• yes unfortunately, btw is there any solution for it @lyxal Mar 5 at 3:58
• @AitzazImtiaz you can increase the time out online using the T flag Mar 5 at 3:58

$- Last 2 links as a monad g(i): Ḥ - 2i ‘ - 2i+1 3Ð¡ - Collect [i, g(i), g(g(i)), g(g(g(i)))] Ẓ - Is prime? Ḅ - Convert from binary = - Does that equal 13? I.e. is the pattern [prime, prime, composite, prime]? Ƈ - Filter 1 ≤ i ≤ n by f(i, 13)  • Almost exactly what I was going for! Mar 5 at 3:51 Retina 0.8.2, 107 bytes .+$*
1
8$* 1{8}$7$*1¶ A^(11+)\1+$
1(1?)
$1 G^(11+)\1+$
1(1?)
$1 A^(11+)\1+$
1(1?)
$1 A^(11+)\1+$
%1


Try it online! Explanation:

.+
$*  Convert to unary. 1 8$*


Multiply by 8.

1{8}
$7$*1¶


Generate all numbers of the form 8k+7 less than that.

A^(11+)\1+$ Delete all composite numbers. 1(1?)$1


Integer divide by 2.

G^(11+)\1+$ Delete all prime numbers. 1(1?)$1


Integer divide by 2.

A^(11+)\1+$ Delete all composite numbers. 1(1?)$1


Integer divide by 2.

A^(11+)\1+$ Delete all composite numbers. %1  Convert the results to decimal. Arturo, 6765 64 bytes $=>[select..1&'x[map@++repeat[1+2*<=]3x=>prime?=@[<=x>0x=0x>0]]]


Try it

$=>[ ; a function select 1..& 'x [ ; select numbers from 1 to <input> and assign current elt to x map [...] => prime? ; map over a block for primality @ ; evaluate a block ++ [...] x ; append x to the end of a block repeat [1+2*<=] 3 ; create the block [1+2*<=1+2*<=1+2*<=] = ; is this equal to... @[<=x>0x=0x>0] ; shortest way I could think of to make [true true false true] ] ; end select ] ; end function  Thunno+, $$\ 17 \log_{256}(96) \approx \$$ 13.99 bytes g1+4R2@*1-NiJB13=  Attempt This Online! Explanation g1+4R2@*1-NiJB13= # Implicit input: + flag adds one g # Filter the range by the following: p 1+ # Add one p+1 4R # Push range(4) p+1, [0, 1, 2, 3] 2@ # Push 2 ** each p+1, [1, 2, 4, 8] * # Multiply each [p+1, 2p+2, 4p+4, 8p+8] 1- # Subtract one [p, 2p+1, 4p+3, 8p+7] Ni # Are they prime? J # Join into a single string B # Convert from binary 13= # Equals 13 (0b1101)?  JavaScript (ES6), 79 bytes Returns a list. f=n=>--n?(g=d=>q%--d?g(d):(q-=~q,d<2))(q=n)&g(q)&!g(q)&g(q)?[...f(n),n]:f(n):[]  Try it online! Commented f = n => // n = upper bound --n ? // decrement n; if it's not 0: ( g = d => // g is a helper function taking d = q q % --d ? // decrement d; if d is not a divisor of q: g(d) // do recursive calls until it is : // else: ( q -= ~q, // update q to 2q + 1 d < 2 // return true if d = 1 ) // i.e. the original q was prime )(q = n) & // test n (should be prime) g(q) & // test 2n+1 (should be prime) !g(q) & // test 4n+3 (should be composite) g(q) // test 8n+7 (should be prime) ? // if all tests pass: [ ...f(n), // append the result of a recursive call n // followed by n ] // : // else: f(n) // just do a recursive call : // else: [] // stop  JavaScript (V8), 75 bytes Prints the terms in reverse order. n=>{for(;--n;)(g=d=>q%--d?g(d):(q-=~q,d<2))(q=n)&g(q)&!g(q)&g(q)&&print(n)}  Try it online! Java 8, 133 126 bytes i->{for(;i-->3;)if(p(i)&p(i-~i)&!p(4*i+3)&p(8*i+7))System.out.println(i);};boolean p(int i){int k=i;for(;i%--k>0;);return k<2;}  Outputs each Imtiaz Germain prime on a separated newline in reversed order. Try it online. Explanation: i->{ // Method with integer parameter and no return-type for(;i-->3;) // Loop i in the range (input,3]: if(p(i) // If i is a prime number &p(i-~i) // and 2i+1 is a prime number &!p(4*i+3) // and 4i+3 is NOT a prime number &p(8*i+7)) // and 8i+7 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  Wolfram Language (Mathematica), 61 bytes Select[Range@#,Boole@PrimeQ@NestList[2#+1&,#,3]=={1,1,0,1}&]&  Try it online! Charcoal, 25 bytes ＩΦＮ⁼1101⭆⊖Ｅ⁴×⊕ιＸ²λ⬤…²λ﹪λν  Try it online! Link is to verbose version of code. Explanation:  Ｎ Input limit Φ Filter on implicit range ⁴ Literal integer 4 Ｅ Map over implicit range ι Outer value ⊕ Incremented × Multiplied by ² Literal integer 2 Ｘ Raised to power λ Inner value ⊖ Vectorised decrement ⭆ Map over values and join … Range from ² Literal integer 2 λ To inner value ⬤ All values satisfy λ Inner value ﹪ Modulo i.e. is not a multiple of ν Innermost value ⁼ Equals 1101 Literal string 1101 Ｉ Cast to string Implicitly print  J, 27 26 bytes [:I.0</@:p:0 1 7 3*&.>:/i.  Try it online! • i.: Make a list of the integers from 0 (inclusive) to the given number (exclusive). • 0 1 7 3 * &. >: /: • First, apply >: (increase by 1) to both 0 1 7 3 and the list from above. • Then, multiply (*) them; / modifies the rank to produce a table of values. • Finally, apply the inverse of >:, decreasing the values by 1. • 0 < / @: p:: • 0 p: produces 0 for primes and 1 for non-primes. • Then (@:, composition), < / inserts (/) < ('less than') between items, turning a b c d into a < (b < (c < d)). For Boolean (0/1) arguments, a < b is 1 if and only if a is 0 and b is 1. Therefore, the result of this is 1 precisely when its input is 0 0 0 1. • [: I.: Make a list of the indices of 1s. A cap ([:) is used to make this monadic. R, 78 75 bytes Edit: -1 byte thanks to pajonk f=\(x)if(x)c(x[all(sapply(x*2^(0:3)-1,\(y)sum(!y%%2:y)<2)-!-2:1)]-1,f(x-1))  Attempt This Online! n, 2*n+1, 2*(2*n+1)+1 and 2*(2*(2*n+1)+1)+1 can be reformulated as x*2^(0:3)-1 using x=n+1. So, we just check these for primes, and test that the desired result (TRUE TRUE FALSE TRUE) is always different to !-2:1 (FALSE FALSE TRUE FALSE), returning x-1 if so. • -1 byte by using the way of checking primes I've always seen in code-golf: \(y)sum(!y%%2:y)<2 Mar 6 at 20:03 Raku, 50 bytes {grep {is-prime$_&2*$_+1&8*$_+7&none 4*$_+3},^$_}


Try it online!

• grep { ... }, ^$_ returns all nonnegative integers less than the input argument $_ that satisfies the bracketed predicate.
• $_ & 2*$_+1 & 8*$_+7 & none 4*$_+3 is a conjunction of $_, the number being tested, as well as twice that number plus one, eight times that number plus seven, and a none junction of four times that number plus three. • is-prime tests the primality of that junction, returning a truthy value if $_, 2*$_+1, and 8*$_+7 are all prime, and 4*\$_+3 is NOT prime.

Python, 118 114 112 111 bytes

lambda n:[i for i in range(n+1)if[*map(lambda x:all(x%k for k in range(2,x)),[i,i-~i,4*i+3,8*i+7])]==[1,1,0,1]]


Attempt This Online!

Python, 123 119 118 bytes

f=lambda n,i=2:i<n and([*map(lambda x:all(x%k for k in range(2,x)),[i,i-~i,4*i+3,8*i+7])]==[1,1,0,1])*[i]+f(n,i+1)or[]


Attempt This Online!

Probably can be improved.

-1 from both by using a trick from @KevinCruijssen's Java answer

Commented

lambda n: [i for i in range(n + 1) if  # Anonymous function, taking an integer n
# Filter [0..n] by the following:
[*map(                               # Apply a function to each item of a list:
lambda x:all(x%k for k in range(2, x)) #  Prime check function
, [i, i-~i, 4*i+3, 8*i+7])         #  Applied to the list [i, 2*i+1, 4*i+3, 8*i+7]
] == [1, 1, 0, 1]]                   # i, 4*i+3, and 8*i+7 are prime, and 2*i+1 is not

f=lambda n, i=2: i<n and (             # Define a recursive function, f, taking an integer n,
# and using an integer, i, as the recursive variable
# If i is less than n:
[...] == [1, 1, 0, 1]              #  (same as above)
) * [i] + f(n, i+1) or []            #  If true, add i. Make a recursive call with i+1
#  Stop if i >= n


Factor + combinators.extras math.primes, 78 bytes

[ iota [ [ dup 2 * 1 + ] thrice 4array [ prime? ] map { t t f t } = ] filter ]


Try it online!

• iota [ ... ] filter select numbers up to input
• [ dup 2 * 1 + ] thrice push n, n*2+1, tos*2+1, tos*2+1 to the stack
• 4array gather them into a sequence
• [ prime? ] map primality test each element
• { t t f t } = is it equal to { t t f t }?