18
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Relevant OEIS. \$\endgroup\$ – Martin Ender Jan 1 '18 at 13:27
  • 2
    \$\begingroup\$ Can we output True if it isn't a Pascal prime and false if it is? \$\endgroup\$ – caird coinheringaahing Jan 1 '18 at 13:44
  • \$\begingroup\$ This sequence is OEIS sequence A002808's intersection with OEIS sequence A137905. \$\endgroup\$ – totallyhuman Jan 1 '18 at 19:27
  • \$\begingroup\$ @cairdcoinheringaahing no, it must be in the given requirement. \$\endgroup\$ – Simply Beautiful Art Jan 1 '18 at 19:43
  • \$\begingroup\$ 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). \$\endgroup\$ – manassehkatz Jan 2 '18 at 15:40

13 Answers 13

10
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

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

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

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

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)

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

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!

\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – l4m2 Jan 2 '18 at 13:20
2
\$\begingroup\$

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.

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

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.

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

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.

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

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!

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

Pyth, 10 bytes

qP_Q/s.cRU

Try it online! or check the Test suite.

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

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 :(

\$\endgroup\$
0
\$\begingroup\$

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!

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

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.