Imtiaz Germain Primes

Question

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.

Task

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

Answer 1

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

Answer 2

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.

Answer 3

Jelly, 13 bytes

Ḥ‘$3СẒḄ=ʋƇ13

Try it online!

How it works

Ḥ‘$3СẒḄ=ʋƇ13 - Main link. Takes an integer n on the left
         ʋ 13 - Last 4 links as a dyad f(i, 13):
  $           -   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)

Answer 4

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.

Answer 5

Arturo, 67 65 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

Answer 6

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

Answer 7

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!

Answer 8

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

Answer 9

Wolfram Language (Mathematica), 61 bytes

Select[Range@#,Boole@PrimeQ@NestList[2#+1&,#,3]=={1,1,0,1}&]&

Try it online!

Answer 10

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

Answer 11

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.

Answer 12

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.

Answer 13

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.

Answer 14

Java 8, 133 126 123 bytes

i->{for(;i-->3;)if(p(i)+p(i-~i)+p(8*i+7)<4&p(4*i+3)>1)System.out.println(i);};int p(int i){for(int k=i;k%--i>0;);return i;}

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(8*i+7)              //   and `8i+7` is a prime number
       <4                     //   (by checking if all three are 0 or 1)
       &p(4*i+3)              //   and `4i+3` is NOT a prime number
        >1)                   //   (by checking whether it's NOT 0 or 1)
      System.out.println(i);} //    Print `i` with trailing newline

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

Answer 15

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 }?

Answer 16

PARI/GP, 145 bytes

can find all desirable numbers up to 1e7 under the time limit in TIO.

Golfed version, try it online!

f(n)={seq=vector(4,i,0);for(i=1,4,seq[i]=n;n=2*n+1;);[isprime(s)|s<-seq]==[1,1,0,1]}
g(N)={res=[];forprime(p=2,N,if(f(p),res=concat(res,p)));res}

Ungolfed version

is_satisfying_condition(n) = {
  seq = vector(4, i, 0);
  for(i=1, 4, seq[i] = n; n = 2*n + 1;);
  return([isprime(s) | s <- seq] == [1, 1, 0, 1]);
}

select_primes(N) = {
  result = [];
  forprime(p = 2, N, if(is_satisfying_condition(p)==1, result = concat(result, p)));
  return(result);
}

g = select_primes(10000);
print(g);