Is it a Pascal Prime?

Question

It is well known that odd primes will appear in Pascal's triangle exactly twice. However, not all numbers that appear exactly twice in Pascal's triangle are prime. We'll call these numbers Pascal primes.

Pascal primes are composite numbers that appear exactly twice in Pascal's triangle. The first few Pascal primes are

4, 8, 9, 12, 14, 16, 18, ...

Your challenge is to take a positive integer n as input and output true or false, depending on if n is a Pascal prime or not. This is code-golf, so the shortest program wins!

Answer 1

Wolfram Language (Mathematica), 45 bytes

CompositeQ@#&&Binomial~Array~{#-1,#}~FreeQ~#&

Try it online!

Every composite number n appears exactly twice on row n and cannot appear afterwards. So the condition for Pascal primes is that they don't appear at all within the first n-1 rows.

As far as I can tell, this is shorter than checking that it appears exactly twice within the first n rows and being able to use !PrimeQ instead.

Answer 2

Jelly, 11 10 9 bytes

Thanks to:

• Martin Ender for -1 byte! (another approach, use ’ (+1) avoid using n2 (-2), so -1 overall.
• Jonathan Allan for bug fix.
• Dennis for another -1 byte.

Ḷc€ḶFċ=ÆP

Try it online!

Alternative approach, by Jonathan Allan. (flawed)

----------- Explanation -----------
Ḷ            Lowered range. [0, 1, ..., n-1]
 c€Ḷ           `c`ombination `€`ach with `Ḷ`owered range [0...n-1]
    F        Flatten.
     ċ       Count the number of occurences of (n) in the list.
       ÆP    Returns 1 if (n) is a prime, 0 otherwise.
      =      Check equality.

Explanation for the last line:

• As pointed out by Martin Ender, "n appears twice in the Pascal triangle" is equivalent to "n doesn't appear in the first n-1 rows".
• We want to return true if the number is not a prime (that is, ÆP == 0) and the count c is zero. From that we can deduce that ÆP == c.
  It can be proven that if they are equal, then they are equal to 0, because:
  • ÆP return a boolean value, which can only be 0 or 1.
  • If it returns 1, then n is a prime, therefore it cannot appear in the first n-1 lines (that is, c == 0)

Answer 3

Python 2, 93 bytes

def f(n):l=[1];exec"(n in l)>=any(n%k<1for k in range(2,n))>q;l=map(sum,zip([0]+l,l+[0]));"*n

Try it online!

This is a named function f, which outputs via exit code, 0 for Pascal Primes, 1 otherwise.

How this works?

def f(n):l=[1];                       # Define a function f (arg. n) and a list l = [1].
exec"..."*n                           # Execute n times.
(n in l)                              # Boolean: "n is in l?" is greater than...
   >=any(n%k<1for k in range(2,n))    # the boolean: "Is n composite?"?
            >q;                       # If the boolean comparison returns a falsy
                                      # result, then continue on without any difference.
                                      # Otherwise, evaluate the other part of the
                                      # inequality, thus performing "is greater than q".
                                      # Since we have no variable "q", this terminates
                                      # with exit code 1, throwing a "NameError".
l=map(sum,zip([0]+l,l+[0]));          # Generate the next row in Pascal's triangle,
                                      # By zipping l prepended with a 0 with l appended
                                      # with a 0 and mapping sum over the result.

This basically checks whether n occurs in the first n - 1 rows of Pascal's triangle or if it is prime, and throws an error if any of these two conditions are met.

Saved 1 byte thanks to ovs.

Answer 4

APL (Dyalog), 44 34 24 19 bytes

5 bytes saved thanks to @Cowsquack

(~0∊⊢|⍨2↓⍳)⍱⊢∊⍳∘.!⍳

Try it online!

How?

We make sure that neither does

⍳ - range 0 .. n-1,

⍳∘.! - upon cartesian binomial with self

⊢∊ - contain n,

⍱ - nor does

⊢|⍨ - n modulo each item of

2↓⍳ - range 2 .. n-1

~0∊ - not contain 0 (a.k.a non-divisible)

Answer 5

Haskell, 86 84 bytes

p=[]:[zipWith(+)(1:x)x++[1]|x<-p]
f n=all((>0).rem n)[2..n-1]==any(elem n)(take n p)

Try it online!

Explanation

The function p recursively defines a degenerate Pascal's triangle:

[]
[1]
[2,1]
[3,3,1]
[4,6,4,1]
[5,10,10,5,1]

As we can see (in this solution 1 is somewhat special) every number n appears exactly twice in the n+1th row and all elements of the subsequent rows only get bigger, thus we only need to check if n is somewhere up to the nth row to see if an element is disqualified:

any(elem n)(take(n-1)p)

Now we have True for all elements that appear more than twice (except 1), so all we need is to have a faulty isPrime function that returns True for 1:

all((>0).rem n)[2..n-1]

Answer 6

JavaScript (Node.js), 103 101 bytes

n=>(r=x=>[...Array(n).keys(F=n=>n>0?n*F(n-1):1)].every(x))(i=>r(j=>F(i)/F(j)/F(i-j)-n))>r(i=>i<2|n%i)

Try it online!

Answer 7

Ruby, ₉₇ 95 bytes

->n{c=!r=[1,1]
(2...n).map{|i|c|=1>n%i
[n]&r=[0,*r,0].each_cons(2).map{|a,b|a+b}}&[[n]]==[]&&c}

Try it online!

Scraped a couple bytes off.

Answer 8

R, 55 bytes

function(n)sum(!n%%1:n)>2&!n%in%outer(1:n-1,1:n,choose)

Try it online!

sum(!n%%1:n)>2 is the composite test and outer(1:n-1,1:n,choose) computes rows 0 to n-1 of Pascal's triangle, so we make sure n does not appear there.

Answer 9

05AB1E, 10 bytes

ÝDδcI¢IpÌQ

Try it online!

Explanation

Ý            # push range [0 ... input]
 D           # duplicate
  δc         # double vectorized command binomial
    I¢       # count occurrences of input
      Ip     # check input for primality
        Ì    # add 2
         Q   # compare for equality

Checks that n occurs exactly twice in the first n+1 rows of pascals triangle and isn't prime.
The comparison works as there are no primes that can occur 3 times in the triangle.

Answer 10

Haskell, 90 bytes

f n=2==sum[1|i<-[0..n],j<-[0..i],p[j+1..i]`div`p[1..i-j]==n,mod(p[1..n-1]^2)n<1]
p=product

Try it online!

Answer 11

Pyth, 10 bytes

qP_Q/s.cRU

Try it online! or check the Test suite.

Answer 12

JavaScript (Node.js), 79 133 130 128 bytes

f=(n,a=[1])=>n<a.length||[...'0'.repeat(n)].filter((x,i)=>n%i<1).length>1&&a.indexOf(n)<0&&f(n,[...a.map((x,i)=>x+a[i-1]||1),1])

Try it online!

evil prime checker +50 bytes :(

Answer 13

Python 2, 105 104 bytes

thanks to user202729 for -1 byte

a=q=[1];n=input();r=n<4;p=1
for i in range(2,n):q=a+map(sum,zip(q[1:],q))+a;r+=n in q;p*=n%i
print p+r<1

Try it online!