Is it a Chen prime?

Question

A number is a Chen prime if it satisfies two conditions:

• It is prime itself
• Itself plus two is either a prime or a semi-prime.

A prime is a number where it has exactly two divisors and those divisors consist of itself and one.

A semi-prime is a number which is the product of two primes. (Note that 12 = 2*2*3 is not semi-prime, but 25 = 5*5 is).

Your task is to determine if a number is a Chen prime. You should output any truthy value for yes and any falsy value for no.

The input will be any integer greater than or equal to one. It may also be taken as a string, character array, or an array or digits.

Examples:

101 -> truthy
223 -> falsy
233 -> truthy
1 -> falsy

This is OEIS A109611.

This is, in part, inspired by Am I a Sophie Germain prime? which, unfortunately, got closed as a duplicate, so I'm posting a somewhat related challenge which isn't a duplicate.

Answer 1

Brachylog, 7 bytes

ṗ+₂ḋl≤2

Try it online!

Explanation

ṗ         Input is prime       
   ḋ      The prime factorization of…
 +₂       … Input + 2…
    l≤2   … has 2 or less elements

Answer 2

05AB1E, 8 bytes

p¹ÌÒg3‹*

Try it online!

Explanation

p¹ÌÒg3‹*   Argument n
p          Push isPrime(n)
 ¹ÌÒ       Push list of prime factors of (n+2)
    g3‹    Length of list is lower than 3
       *   Multiplication of boolean values, 0 if either is 0 (false)

Answer 3

ArnoldC, 1339 bytes

LISTEN TO ME VERY CAREFULLY q
I NEED YOUR CLOTHES YOUR BOOTS AND YOUR MOTORCYCLE p
GIVE THESE PEOPLE AIR
HEY CHRISTMAS TREE c
YOU SET US UP 0
HEY CHRISTMAS TREE d
YOU SET US UP 0
HEY CHRISTMAS TREE l
YOU SET US UP p
STICK AROUND l
GET TO THE CHOPPER d
HERE IS MY INVITATION p
I LET HIM GO l
ENOUGH TALK
BECAUSE I'M GOING TO SAY PLEASE d
BULLSHIT
GET TO THE CHOPPER c
HERE IS MY INVITATION c
GET UP 1
ENOUGH TALK
YOU HAVE NO RESPECT FOR LOGIC
GET TO THE CHOPPER l
HERE IS MY INVITATION l
GET DOWN 1
ENOUGH TALK
CHILL
I'LL BE BACK c
HASTA LA VISTA, BABY
IT'S SHOWTIME
HEY CHRISTMAS TREE p
YOU SET US UP 0
GET YOUR ASS TO MARS p
DO IT NOW
I WANT TO ASK YOU A BUNCH OF QUESTIONS AND I WANT TO HAVE THEM ANSWERED IMMEDIATELY
HEY CHRISTMAS TREE n
YOU SET US UP 0
GET YOUR ASS TO MARS n
DO IT NOW q p
HEY CHRISTMAS TREE g
YOU SET US UP 42
GET TO THE CHOPPER g
HERE IS MY INVITATION n
YOU ARE NOT YOU YOU ARE ME 2
ENOUGH TALK
BECAUSE I'M GOING TO SAY PLEASE g
GET TO THE CHOPPER p
HERE IS MY INVITATION p
GET UP 2
ENOUGH TALK
GET YOUR ASS TO MARS n
DO IT NOW q p
GET TO THE CHOPPER g
HERE IS MY INVITATION 5
LET OFF SOME STEAM BENNET n
ENOUGH TALK
BECAUSE I'M GOING TO SAY PLEASE g
TALK TO THE HAND "t"
BULLSHIT
TALK TO THE HAND "f"
YOU HAVE NO RESPECT FOR LOGIC
BULLSHIT
TALK TO THE HAND "f"
YOU HAVE NO RESPECT FOR LOGIC
YOU HAVE BEEN TERMINATED

Try it online!

(This is my first post on codegolf.SE, please let me know if this is formatted incorrectly. I realize this byte count is not competitive, this is just for fun.)

Answer 4

Pyth, 10 bytes

&P_Q>3lP+2

Try it online!

How?

&P_Q>3lP+2  # input: Q
        +2  # Q + 2
       P    # prime factors
    >3l     # length lower than 3?
 P_Q        # Q is prime?
&           # and both results

Answer 5

Jelly, 10 bytes

+2ÆfL<3aÆP

Try it online!

Answer 6

Pari/GP, 29 bytes

The 3*isprime(n) trick is stolen from Jonathan Allan 's answer.

n->bigomega(n+2)<3*isprime(n)

Try it online!

Answer 7

Python with sympy,  69  56 bytes

-13 bytes thanks to alephalpha (by upgrading to sympy 1.1 and using primeomega(n+2) to replace sum(factorint(n+2).values()))

...taking over from Gryphon's deleted submission.

from sympy import*
lambda n:primeomega(n+2)<3*isprime(n)

An unnamed function returning True for Chen primes and False otherwise.

Counts the factors of n+2 by summing its prime factor's multiplicities.

Note that 3 is multiplied by isprime(n) before the < comparison is made, so for non-prime n the code tests if n+2 has less than 0 factors (always yielding False), while for prime n it checks whether n+2 is prime or semi-prime.

Answer 8

Java 8, 85 84 83 bytes

n->{int a=n+2,b=0,c=0,i=1;for(;i++<n;b+=n%i<1?1:0)c+=a%i<1?1:0;return n>1&b<2&c<3;}

-1 bytes thanks to @OlivierGrégoire by using an iterative approach instead of recursive.

Explanation:

Try it here.

n->{            // Method with integer parameter and boolean return-type
  int a=n+2,    //  Start `a` at the input + 2
      b=0,c=0,  //  Start `b` and `c` at 0
      i=1;      //  Start `i` at 1
  for(;i++<n;   //  Loop from 1 to `n` (and raise `i` immediately by 1)
    b+=n%i<1?   //   If the input is divisible by `i`
        1       //    Raise `b` by 1
       :        //   Else:
        0)      //    Leave `b` as is
    c+=a%i<1?   //   If the input + 2 is divisible by `i`:
        1       //    Raise `c` by 1
       :        //   Else:
        0;      //    Leave `c` as is
                //  End of loop (implicit / single-line body)
  return n>1    //  Return if the input is larger than 1
         &b<2   //   And `b` is now smaller than 2
         &c<3;  //   And `c` is now smaller than 3
}               // End of method

Answer 9

JavaScript (ES6), 63 61 bytes

g=(e,i=e)=>i--<3?1:e%i?g(e,i):g(i)+1
f=e=>e>1&g(e)<2&g(e+2)<3

Test cases:<br><textarea id=i rows=6 oninput="go()">101&#10;223&#10;233&#10;1</textarea><br><pre id=q></pre><script>window.onload=function go(){document.getElementById('q').innerHTML=document.getElementById('i').value.split('\n').map(e=>e+' -> '+f(+e)).join('\n')}</script>

Defines a function f that takes n as argument and returns the result. Im very happy with how g turned out; it counts the number of prime factors in a number.

2 bytes saves thanks to Kevin Cruijssen's & trick.

Ungolfed

Ω = (n,          // Ω(n) = number of n's prime factors, n > 1.
    i = n) =>    // Start iterating from i = n - 1. Since we'll immediately
                 // decrement i, n is used here.
    --i          // Immediately decrement i.

    < 2          // If i = 0 or i = 1, n is a prime at this point.
    ? 1 :        // Therefore Ω(n) = 1.

    n % i != 0 ? // If n is not divisible by i,
    Ω(n, i)      // try again with i := i - 1 (immediately decremented, so use i).

    : Ω(i) + 1   // n is divisible by i. Since we're counting down from n - 1
                 // and i is the first such number, i is n's largest non-trivial
                 // divisor, and thus n/i is a prime.
                 // Therefore Ω(n) = Ω(i) + Ω(n/i) = Ω(i) + 1.

is_chen = n =>     // An integer n ≥ 1 is a Chen prime if and only if:
    n > 1          // n > 1,
    & Ω(n) < 2     // Ω(n) = 1 < 2, i.e. n is a prime, and
    & Ω(n + 2) < 3 // Ω(n + 2) < 3, i.e. n + 2 is a prime or a semiprime.

Answer 10

Japt, 22 20 19 13 12 bytes

U°j ©2¨°Uk l

• 6 bytes saved thanks to obarakon's suggestion of a different method.

Test it

Answer 11

Mathematica, 28 bytes

PrimeQ@#&&PrimeOmega[#+2]<3&

Answer 12

PHP, 64 bytes

for($i=$n=$argn+2;--$i;$argn%$i?:$q++)$n%$i?:++$p;echo$p<4^--$q;

prints 0 for truthy, other integers for falsy. Run as pipe with -nR or try it online.

breakdown

for($i=$n=$argn+2;--$i; # loop $i from N+1 to 1
    $argn%$i?:$q++)         # if $i divides N, increment $q
    $n%$i?:++$p;            # if $i divides N+2, increment $p
echo$p<4                # $p is 1 for a prime, 3 for a semiprime
    ^--$q;              # $q is 2 for prime; so this is 1^1 (==0) for a Chen Prime

consistent falsy value, 65 bytes:

for($i=$n=2+$k=$argn;--$i;$k%$i?:$q++)$n%$i?:++$p;echo$p<4&$q==2;

prints 1 for truthy and 0 for falsy.

Answer 13

Python 3 with SymPy, 73 71 bytes

lambda n:(sum(factorint(n+2).values())<3)&isprime(n)
from sympy import*

Try it online!

---

This is a more-golfed version of an answer posted here earlier, but it seems to have been deleted.

---

Thanks to @JonathanAllan for saving 2 bytes!

Answer 14

PHP, 87 bytes

for($b=($a=$argn)+$i=2;2<$a+$b;)$a%$i?$b%$i?$i++:++$d*$b/=$i:++$c*$a/=$i;echo$c<2&$d<3;

Try it online!

PHP, 87 bytes

for(;$n<2;)for($a=$argn+$n++*$i=2;1<$a;)$a%$i?$i++:++$r[$n]*$a/=$i;echo$r[1]<2&$r[2]<3;

Try it online!

Answer 15

APL NARS, 23 chars

{1≥⍵:0⋄(1=⍴π⍵)∧3>⍴π⍵+2}

Here π⍵ return the array of factors of ⍵ different from 1; some test:

  f←{1≥⍵:0⋄(1=⍴π⍵)∧3>⍴π⍵+2}
  f 101
1 
  f 223
0 
  f 233
1 
  f 1
0
  f ¯10
0

Answer 16

Ruby, 49 41 bytes

->n{/^(.?|((..+)\3+))(\2+|..)$/!~?l*n+=2}

Try it online!

Thanks H.PWiz for -8 bytes

How?

First thing, get a string of 'l' repeated n+2 times. Then apply a regex to check if:

• Length is 2 or 3 (.?)(..)
• Length is a composite number plus 2 ((..+)\1)(..)
• Length is a product of at least 3 numbers ((..+)\2)\1+

The 2 regex parts generate a fourth case which doesn't make sense and is safe to ignore: (.?)\2+, that resolves to empty string or a single character because \2 is empty.

Answer 17

Regex (ECMAScript), 31 bytes

^(?!((xx+)(\2(xx))*)(\1\4)+$)xx

Try it online! (showing all Chen primes ≤ 1000)

Given a string of n xs this regex will match if and only if n is a Chen prime.

It asserts that n is greater than 2 and that the string is not of the form ((xx+)(\2(xx))*)(\1\4)+
This regex has two meanings, depending on how many times (\2(xx)) is repeated.
When it is repeated 0 times, the regex can be simplified to (xx+)\1+, which matches composite numbers.
When it is repeated a positive number of times, the regex is equivalent to ((xx+)(\2xx)+)(\1xx)+

That regex requires some explanation, however, I will provide little insight.
If you go through the algebra you find that ((xx+)(\2xx)+)(\1xx)+ matches numbers of the form a*b*c-2 where a≥4,b≥2,c≥2.
So it will match (almost) whenever n+2 has more than 2 prime factors. (i.e neither prime nor semi-prime)
Note that it doesn't match 6, 16 or 25, but that this doesn't matter, because they are all composite.

So (?!((xx+)(\2(xx))*)(\1\4)+$) will match as long as n is not composite, and n+2 is either prime or semi-prime.
Unfortunately this includes 1 (and 0), so we then check that n is at least 2 with xx

A couple of different "31-byters" are:

^xx(?!((x*)(\2xx)+)\1?(\1xx)*$)
^(?!(xx((x*)(\3xx)+))\2?\1*$)xx

Answer 18

Julia, 59 bytes

x->((0∉x%(2:x-1))&(length(find(x->x==0,(x+2)%(2:x)))<=2))

Answer 19

Pyt, 11 bytes

3*isprime(x) stolen from Jonathan Allan's answer

←Đṗ3*⇹2+ḋŁ>

Answer 20

Haskell, 163 bytes

p k=last$(not$elem 0(map(mod k)[2..k-1])):[1>2|k<=1]
r=round
s n=p(r n)||any(\(a,b)->p(r a)&&p(r b))[(n/x,x)|x<-[2..n],n/x==(fromIntegral.r)n/x]
c n=p(r n)&&s(n+2)

Try it online!