Хорошо известно, что нечетные простые числа появятся в треугольнике Паскаля ровно дважды. Однако не все числа, которые появляются ровно дважды в треугольнике Паскаля, являются простыми. Мы будем называть эти числа простыми числами Паскаля.

Простые числа Паскаля - это составные числа, которые появляются ровно дважды в треугольнике Паскаля. Первые несколько простых чисел Паскаля

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

Ваша задача - взять положительное целое число n в качестве входных и выходных значений true или false, в зависимости от того, является ли n простым числом Паскаля или нет. Это код-гольф, поэтому выигрывает самая короткая программа!

Wolfram Language (Mathematica) , 45 байт

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

Попробуйте онлайн!

Каждое составное число n появляется ровно дважды в строке n и не может появиться впоследствии. Таким образом, условием для простых чисел Паскаля является то, что они вообще не появляются в первых n-1 строках.

Насколько я могу судить, это короче, чем проверка того, что он появляется ровно дважды в первых n строках, и возможность использовать !PrimeQвместо этого.

Python 2 , 93 байта

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

Попробуйте онлайн!

Это именованная функция f , которая выводит через код выхода , 0 для простых чисел Паскаля, 1 в противном случае.

Как это работает?

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.

Это в основном проверяет, встречается ли n в первых n - 1 строках треугольника Паскаля или является ли оно простым, и выдает ошибку, если выполняется любое из этих двух условий.

Сохранено 1 байт благодаря ovs .

Желе , 11 10 9 байт

Благодаря:

• Мартин Эндер за -1 байт! (другой подход, используйте ’(+1), избегайте использования n2(-2), поэтому -1 в целом.
• Джонатан Аллан за исправление ошибки.
• Деннис за еще один байт.

Ḷc€ḶFċ=ÆP

Попробуйте онлайн!

Альтернативный подход , Джонатан Аллан . (недостатки)

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

Пояснение к последней строке:

• Как указал Мартин Эндер, « nпоявляется дважды в треугольнике Паскаля» эквивалентно « nне появляется в первых n-1строках».
• Мы хотим вернуть, trueесли число не простое (то есть ÆP == 0), а количество cравно нулю. Из этого мы можем вывести это ÆP == c.
  Можно доказать, что если они равны, то они равны 0, потому что:
  • ÆP вернуть логическое значение, которое может быть только 0 или 1.
  • Если он возвращает 1, то nэто простое число, поэтому он не может появиться в первых n-1строках (то есть, c == 0)

Haskell , 86 84 байта

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

Попробуйте онлайн!

объяснение

Функция pрекурсивно определяет вырожденный треугольник Паскаля:

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

Как мы видим (это решение 1несколько особенное), каждое число nпоявляется ровно дважды в n+1строке th, а все элементы последующих строк только nувеличиваются , поэтому нам нужно только проверить, находится ли где-то до nстроки th, чтобы увидеть, элемент дисквалифицирован:

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

Теперь у нас есть Trueвсе элементы , которые появляются более чем в два раза ( за исключение 1), поэтому все , что нам нужно, чтобы иметь дефектную isPrimeфункцию , которая возвращает Trueдля 1:

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

APL (Dyalog) , 44 34 24 19 байтов

5 байтов сохранено благодаря @Cowsquack

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

Попробуйте онлайн!

Как?

Мы уверены, что ни один не делает

⍳- диапазон 0.. n-1,

⍳∘.! - на декартовом биноме с самим собой

⊢∊- содержать n,

⍱- и не делает

⊢|⍨- nпо модулю каждого элемента

2↓⍳- диапазон 2..n-1

~0∊- не содержать 0(или неделимый)

JavaScript (Node.js) , 103 101 байт

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)

Попробуйте онлайн!

Рубин , ₉₇ 95 байт

->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}

Попробуйте онлайн!

Соскребли пару байтов.

R , 55 байт

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

Попробуйте онлайн!

sum(!n%%1:n)>2является составным тестом и outer(1:n-1,1:n,choose)вычисляет строки 0в n-1треугольнике Паскаля, поэтому мы должны убедиться, что nони там не отображаются.

05AB1E , 10 байтов

ÝDδcI¢IpÌQ

Попробуйте онлайн!

объяснение

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

Проверки, которые nвстречаются ровно дважды в первых n + 1 строках треугольника паскалей и не являются простыми.
Сравнение работает, так как в треугольнике нет простых чисел, которые могут встречаться 3 раза.

Haskell , 90 байт

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

Попробуйте онлайн!

Pyth , 10 байт

qP_Q/s.cRU

Попробуйте онлайн! или проверьте набор тестов.

JavaScript (Node.js) , 79 133 130 128 байт

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

Попробуйте онлайн!

злой премьер чекер +50 байт :(

Python 2 , 105 104 байта

спасибо пользователю 202729 за -1 байт

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

Попробуйте онлайн!