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

• Relevant OEIS. Jan 1, 2018 at 13:27
• Can we output True if it isn't a Pascal prime and false if it is? Jan 1, 2018 at 13:44
• This sequence is OEIS sequence A002808's intersection with OEIS sequence A137905. Jan 1, 2018 at 19:27
• @cairdcoinheringaahing no, it must be in the given requirement. Jan 1, 2018 at 19:43
• I'm surprised nobody has posted an answer in Pascal. I will if I get the time (and if I can find my old Pascal compiler). Jan 2, 2018 at 15:40

## 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, 2018 at 18:07
• @ovs :o That’s clever! Thanks. Jan 1, 2018 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. Jan 1, 2018 at 14:18
• Ḷc€ḶFċoÆP¬ would work I think. Jan 1, 2018 at 14:19
• ċ=ÆP should work. Jan 1, 2018 at 14:42
• FYI I found a flaw in my approach and have deleted it. Jan 1, 2018 at 16:08
• BTW ḶcþFċ=ÆP should work too. Jan 1, 2018 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 Jan 1, 2018 at 14:48
• @Cowsquack hmm I didn't notice it got so short that a train could fit (started as 40 byter). Thanks! Jan 1, 2018 at 14:49
• (0∊⊢|⍨2↓⍳)∧∘~⊢∊⍳∘.!⍳ for another two, I changed the primality checking algorithm Jan 1, 2018 at 15:13
• @Cowsquack oo clever. I've never seen that primality variation before Jan 1, 2018 at 15:17
• Rearranging the ~ gives (~0∊⊢|⍨2↓⍳)⍱⊢∊⍳∘.!⍳ for one less byte. Jan 1, 2018 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, 2018 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... Jan 1, 2018 at 13:55