# Is it a Pascal Prime?

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!

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

# Python 2, 93 bytes

def f(n):l=;exec"(n in l)>=any(n%k<1for k in range(2,n))>q;l=map(sum,zip(+l,l+));"*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=;                       # Define a function f (arg. n) and a list l = .
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(+l,l+));          # 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.

• 93 bytes – ovs Jan 1 '18 at 18:07
• @ovs :o That’s clever! Thanks. – Mr. Xcoder Jan 1 '18 at 18:09

# Jelly, 1110 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€Ḷ           combination €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)
• 1 is not a Pascal prime; this says it is. – Jonathan Allan Jan 1 '18 at 14:18
• Ḷc€ḶFċoÆP¬ would work I think. – Jonathan Allan Jan 1 '18 at 14:19
• ċ=ÆP should work. – Dennis Jan 1 '18 at 14:42
• FYI I found a flaw in my approach and have deleted it. – Jonathan Allan Jan 1 '18 at 16:08
• BTW ḶcþFċ=ÆP should work too. – Mr. Xcoder Jan 1 '18 at 18:38

p=[]:[zipWith(+)(1:x)x++|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:

[]

[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]


# APL (Dyalog), 443424 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)

• Converting it into a train (∨/1↓1≠⊢∨⍳)∧(~⊢∊⍳∘.!⍳) is shorter by two bytes – user41805 Jan 1 '18 at 14:48
• @Cowsquack hmm I didn't notice it got so short that a train could fit (started as 40 byter). Thanks! – Uriel Jan 1 '18 at 14:49
• (0∊⊢|⍨2↓⍳)∧∘~⊢∊⍳∘.!⍳ for another two, I changed the primality checking algorithm – user41805 Jan 1 '18 at 15:13
• @Cowsquack oo clever. I've never seen that primality variation before – Uriel Jan 1 '18 at 15:17
• Rearranging the ~ gives (~0∊⊢|⍨2↓⍳)⍱⊢∊⍳∘.!⍳ for one less byte. – user41805 Jan 1 '18 at 16:22

# 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!

• 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))>F(n-1)**2%n threority works but in fact for small range – l4m2 Jan 2 '18 at 13:20

# Ruby, 97 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.

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

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

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


Try it online!

# Pyth, 10 bytes

qP_Q/s.cRU


Try it online! or check the Test suite.

# JavaScript (Node.js), 79133130 128 bytes

f=(n,a=)=>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 :(

# Python 2, 105 104 bytes

thanks to user202729 for -1 byte

a=q=;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!

• The pair of parentheses around p+r` seems redundant... – user202729 Jan 1 '18 at 13:55