26
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Can we return True for truthy and 2 or False for falsy (inconsistent falsy values)? \$\endgroup\$ – Mr. Xcoder Jul 10 '17 at 12:04
  • \$\begingroup\$ @Mr.Xcoder Never said you couldn't \$\endgroup\$ – Okx Jul 10 '17 at 12:06
  • \$\begingroup\$ For a semi-prime, does "exactly two prime factors" count multiplicity? Is 2 * 2 * 2 * 3 * 3 a semi-prime? What about 5 * 5? \$\endgroup\$ – Not a tree Jul 10 '17 at 12:09
  • \$\begingroup\$ @Notatree 5*5 is semi-prime, 2*2*2*3*3 is not. I said exactly two. \$\endgroup\$ – Okx Jul 10 '17 at 12:11
  • \$\begingroup\$ So it does count multiplicity, then? (You could argue that 2*2*2*3*3 has exactly two prime factors, namely 2 and 3, and 5*5 has one prime factor, namely 5.) Maybe you could edit that into the question? \$\endgroup\$ – Not a tree Jul 10 '17 at 12:17

20 Answers 20

12
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ I caught Neil at exactly 48,000 rep, and now you at exactly 22,222 :P \$\endgroup\$ – ETHproductions Jul 10 '17 at 16:29
11
\$\begingroup\$

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)
\$\endgroup\$
6
\$\begingroup\$

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

\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ >.< Outgolfed >.< \$\endgroup\$ – Mr. Xcoder Jul 10 '17 at 12:17
  • \$\begingroup\$ @Mr.Xcoder actually, I posted mine 5 minutes before \$\endgroup\$ – Uriel Jul 10 '17 at 12:19
  • \$\begingroup\$ Yeah, didn't see it because of the poor internet connection \$\endgroup\$ – Mr. Xcoder Jul 10 '17 at 12:23
4
\$\begingroup\$

Jelly, 10 bytes

+2ÆfL<3aÆP

Try it online!

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ @Gryphon - I took over, it may be beatable without any imports however. \$\endgroup\$ – Jonathan Allan Jul 10 '17 at 13:26
  • \$\begingroup\$ I've been outgolfed! The 3*isprime(n) trick is what I was looking for in cleaning up the conditional statement. \$\endgroup\$ – icosahedron Jul 10 '17 at 13:35
  • \$\begingroup\$ Ah, @icosahedron, I had not noticed yours, sorry - this is so similar I would have just commented to help you to improve yours. Feel free to treat this answer as such, just let me know and I'll delete this one. \$\endgroup\$ – Jonathan Allan Jul 10 '17 at 13:46
  • \$\begingroup\$ I think sympy has a primeomega function. \$\endgroup\$ – alephalpha Jul 10 '17 at 13:48
  • \$\begingroup\$ @alephalpha Thanks, just upgraded to 1.1 to see it, that'll save bytes! \$\endgroup\$ – Jonathan Allan Jul 10 '17 at 13:56
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ The iterative version is just a byte shorter: n->{int N=n+2,f=0,F=0,d=1;for(;d++<n;f+=n%d<1?1:0)F+=N%d<1?1:0;return n>1&f<2&F<3;}. \$\endgroup\$ – Olivier Grégoire Jul 10 '17 at 22:59
2
\$\begingroup\$

Mathematica, 28 bytes

PrimeQ@#&&PrimeOmega[#+2]<3&
\$\endgroup\$
2
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Can't you change both && to &? Since 0/1 are truthy/falsey values in JS as well? \$\endgroup\$ – Kevin Cruijssen Jul 10 '17 at 13:19
  • \$\begingroup\$ @KevinCruijssen That seems to work. Too bad | and & don't short-circuit, that might save even more bytes in g. \$\endgroup\$ – PurkkaKoodari Jul 10 '17 at 13:27
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ ...also note that you do not need f=, creating an unnamed function is fine for code-golf. \$\endgroup\$ – Jonathan Allan Jul 10 '17 at 13:48
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You can merge the two halves of your | closer together: ^((..+)\2+)(\1+|..)$. Also, a neat coincidence that you attempted this problem with regex at a similar time to me :) \$\endgroup\$ – H.PWiz Apr 17 at 23:01
  • \$\begingroup\$ I believe that you can use . instead of .? since the input is always at least 1 \$\endgroup\$ – H.PWiz Apr 18 at 11:01
0
\$\begingroup\$

Julia, 59 bytes

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

Pyt, 11 bytes

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

←Đṗ3*⇹2+ḋŁ>
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.