Число является числом де Полиньяка тогда и только тогда, когда оно нечетное и не может быть представлено в виде p + 2 ^n, где n - неотрицательное целое число, а p - простое целое число.

задача

Напишите некоторый код, который принимает положительное целое число и определяет, является ли оно числом де Полиньяка. Вы можете вывести два разных значения, одно для истинного и одно для ложного. Вы должны стремиться минимизировать количество байтов.

Тестовые случаи

Для положительных случаев вот OEIS

1, 127, 149, 251, 331, 337, 373, 509, 599, 701, 757, 809, 877, 905, 907, 959, 977, 997, 1019, 1087, 1199, 1207, 1211, 1243, 1259, 1271, 1477, 1529, 1541, 1549, 1589, 1597, 1619, 1649, 1657, 1719, 1759, 1777, 1783, 1807, 1829, 1859, 1867, 1927, 1969, 1973, ...

Вот несколько негативных случаев:

22, 57

Japt , 9 14 13 байт

o!²mnU dj |Uv

Проверьте это онлайн! или Найти все целые числа де Полиньяка до 1000 .

Выходы 1для ложных входов и 0для правдивых.

объяснение

 o!²  mnU dj |Uv
Uo!p2 mnU dj |Uv  : Ungolfed
                  : Implicit: U = input integer (e.g. 9)
Uo                : Create the range [0..U), and map each item X to
  !p2             :   2 ** X.               [1, 2, 4, 8, 16, 32, 64, 128, 256]
      m           : Map each of these powers of 2 by
       nU         :   subtracting from U.   [8, 7, 5, 1, -7, -23, -57, -119, -247]
          d       : Return whether any item in the result is
           j      :   prime.                (5 and 7 are, so `true`)
             |    : Take the bitwise OR of this and
              Uv  :   U is divisble by (missing argument = 2).
                  : This gives 1 if U cannot be represented as p + 2^n or if U is even.
                  : Implicit: output result of last expression

Желе , 11 10 байт

Сохранено 1 байт благодаря @Dennis

Ḷ2*³_ÆPS<Ḃ

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

Как это устроено

Ḷ2*³_ÆPS<Ḃ   Main link. Argument: n (integer)
Ḷ            Lowered range; yield [0, 1, 2, ..., n-1].
 2*          Reversed exponentiation with 2; yield [1, 2, 4, ..., 2**(n-1)].
   ³_        Reversed subtraction with the input; yield [n-1, n-2, n-4, ..., n-2**(n-1)].
     ÆP      Replace each item with 1 if it is prime, 0 otherwise.
       S     Sum; yield a positive integer if any item was prime, 0 otherwise.
         Ḃ   Yield n % 2.
        <    Yield 1 if the sum is less than n % 2, 0 otherwise.
             This yields 1 if and only if the sum is 0 and n is odd.

JavaScript (ES6),  56 54  53 байта

Возвращает $0$ или $1$ .

f=(n,p=1,x=y=n-p)=>n>p?y%--x?f(n,p,x):x!=1&f(n,p*2):n

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

Как?

Начнем с $p = 1$ . Мы проверяем, является ли $y = n - p$ составным, и получаем логическое значение соответственно. Следующий тест выполняется с $p \times 2$ .

Как только $p$ больше $n$ , мы прекращаем рекурсию и возвращаем $n$ .

Результаты всех итераций объединяются в AND и приводят логические значения к $0$ или $1$ .

При условии, что все промежуточные результаты были правдивыми, мы получаем побитовый тест, такой как:

1 & 1 & 1 & n

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

Python 2 , 60 57 56 байт

f=lambda n,k=1,p=-1:k/n or(n-k&n-k-p%k>0)&n&f(n,k+1,p*k)

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

Желе , 10 байт

Альтернативное 10-байтовое представление Jelly к уже опубликованному.

_ÆRBS€’×ḂẠ

Монадическая ссылка, возвращающая 1 для чисел де Полиньяка и 0 в противном случае.

Попробуйте онлайн! или посмотрите те под 1000 .

Как?

_ÆRBS€’×ḂẠ - Link: number, n  e.g.  1    3      5                  6                   127
 ÆR        - prime range            []   [2]    [2,3,5]            [2,3,5]             [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127]
_          - subtract from n        []   [1]    [3,2,0]            [4,3,1]             [125,124,122,120,116,114,110,108,104,98,96,90,86,84,80,74,68,66,60,56,54,48,44,38,30,26,24,20,18,14,0]
   B       - convert to binary      []   [[1]]  [[1,1],[1,0],[0]]  [[1,0,0],[1,1],[1]  [[1,1,1,1,1,0,1],[1,1,1,1,1,0,0],[1,1,1,1,0,1,0],[1,1,1,1,0,0,0],[1,1,1,0,1,0,0],[1,1,1,0,0,1,0],[1,1,0,1,1,1,0],[1,1,0,1,1,0,0],[1,1,0,1,0,0,0],[1,1,0,0,0,1,0],[1,1,0,0,0,0,0],[1,0,1,1,0,1,0],[1,0,1,0,1,1,0],[1,0,1,0,1,0,0],[1,0,1,0,0,0,0],[1,0,0,1,0,1,0],[1,0,0,0,1,0,0],[1,0,0,0,0,1,0],[1,1,1,1,0,0],[1,1,1,0,0,0],[1,1,0,1,1,0],[1,1,0,0,0,0],[1,0,1,1,0,0],[1,0,0,1,1,0],[1,1,1,1,0],[1,1,0,1,0],[1,1,0,0,0],[1,0,1,0,0],[1,0,0,1,0],[1,1,1,0],0]
    S€     - sum €ach               []   [1]    [2,1,0]            [1,2,1]             [6,5,5,4,4,4,5,4,3,3,2,4,4,3,2,3,2,2,4,3,4,2,3,3,4,3,2,2,2,3,0]
      ’    - decrement              []   [0]    [1,0,-1]           [0,1,0]             [5,4,4,3,3,3,4,3,2,2,1,3,3,2,1,2,1,1,3,2,3,1,2,2,3,2,1,1,1,2,-1]
        Ḃ  - n mod 2                1    1      1                  0                   1
       ×   - multiply               []   [0]    [1,0,-1]           [0,0,0]             [5,4,4,3,3,3,4,3,2,2,1,3,3,2,1,2,1,1,3,2,3,1,2,2,3,2,1,1,1,2,-1]
         Ạ - all truthy?            1    0      0                  0                   1

05AB1E , 9 8 байт

-1 байт благодаря Emigna

Ýo-pZ¹È~

Выходы 0для достоверных входов и 1ложных входов.

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

Python 2 , 99 байт

lambda n:n&1-any(n-2**k>1and all((n-2**k)%j for j in range(2,n-2**k))for k in range(len(bin(n))-2))

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

-4 байта благодаря Лаки Нун

-2 байта благодаря Wondercricket

+8 байт, чтобы исправить ошибку

-1 байт благодаря мистеру Xcoder

-3 байта благодаря Einkorn Enchanter

+12 байт, чтобы исправить ошибку

Регулярное выражение (ECMAScript), 97 байт

Эта проблема представляла интересный случай для решения проблемы отсутствия неатомарного взгляда. И пока единственный раз, когда у меня была веская причина поставить обе версии теста степени 2, ((x+)(?=\2$))*x$и (?!(x(xx)+)\1*$)в одном и том же регулярном выражении, и единственный раз, когда мне нужно было защитить основной тест от сопоставления. 1, как (?!(xx+)\1+$)xxпри использовании в большем регулярном выражении.

^(?!(xx)*$|(x+)((?!(xx+)\4+$).*(?=\2$)((x+)(?=\6$))*x$|(?!(x(xx)+)\7*$).*(?=\2$)(?!(xx+)\9+$)xx))

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

# For the purposes of these comments, the input number = N.
^
# Assert that N is not the sum of a prime number and a power of 2.
(?!
    (xx)*$                 # Assert that N is odd.
|
    # Since we must cycle through all values for a number X and a corresponding number
    # N-X, this cannot be in an atomic lookahead. The problem then becomes that it
    # consumes characters. Thus we must let X be the larger of the two and N-X be the
    # smaller, and do tests on X followed by tests on N-X. We can't just test X for
    # being prime and N-X for being a power of 2, nor vice versa, because either one
    # could be smaller or larger. Thus, we must test X for being either prime or a
    # power of 2, and if it matches as being one of those two, do the opposite test on
    # N-X.
    # Note that the prime test used below, of the form (?!(xx+)\2+$), has a false match
    # for 0 and 1 being prime. The 0 match is harmless for our purposes, because it
    # will only result in a match for N being a power of 2 itself, thus rejecting
    # powers of 2 as being de Polignac numbers, but since we already require that N is
    # odd, we're already rejecting powers of 2 implicitly. However, the 1 match would
    # break the robustness of this test. There can be de Polignac numbers of the form
    # 2^M+1, for example 262145 and 2097153. So we must discard the 1 match by changing
    # the prime test to "(?!(xx+)\2+$)xx". We only need to do this on the N-X test,
    # though, because as X is the larger number, it is already guaranteed not to be 1.
    (x+)           # \2 = N-X = Smaller number to test for being prime or a power of 2;
                   # tail = X = larger number to test for being prime or a power of 2.
    (
        (?!(xx+)\4+$)      # Test X for being prime.
        .*(?=\2$)          # tail = N-X
        ((x+)(?=\6$))*x$   # Test N-X for being a power of 2. Use the positive version
                           # since it's faster and doesn't have a false match of 0.
    |
        (?!(x(xx)+)\7*$)   # Test X for being a power of 2. Use the negative version
                           # because the testing of X has to be in a lookahead, and
                           # putting the positive version in a positive lookahead would
                           # be worse golf. It doesn't matter that this can have a false
                           # match of 0, because X is guaranteed never to be 0.
        .*(?=\2$)          # tail = N-X
        (?!(xx+)\9+$)xx    # Test N-X for being prime. We must prevent a false match of
                           # 1 for the reason described above.
    )
)

Regex (ECMAScript + молекулярный взгляд), 53 52 байта

^(?!(xx)*$|(?*xx+(((x+)(?=\4$))*x$))\2(?!(xx+)\5+$))

# For the purposes of these comments, the input number = N.
^
# Assert that N is not the sum of a prime number and a power of 2.
(?!
    (xx)*$                   # Assert that N is odd.
|
    (?*
        xx+                  # Force N - \2 to be > 1, because the prime test used
                             # below has a false match of 1, which would otherwise
                             # give us false negatives on de Polignac numbers of the
                             # form 2^M+1, such as 262145 and 2097153.
        (((x+)(?=\4$))*x$)   # Cycle through subtracting all possible powers of 2 from
                             # tail, so we can then test {N - {power of 2}} for being
                             # prime.
                             # \2 = the power of 2
    )
    \2                       # tail = N - \2
    (?!(xx+)\5+$)            # Test tail for being prime. If it matches, this will fail
                             # the outside negative lookahead, showing that N is not a
                             # de Polignac number.
)

Эта версия не только намного чище, но и намного быстрее, потому что вместо того, чтобы циклически обходить все возможные способы, которыми N является суммой двух чисел, она может просто циклически вычитать каждую степень 2 из N и проверять разницу на простое число. ,

Молекулярный взгляд может быть легко преобразован в взгляд с переменной длиной:

Regex (.NET или ECMAScript 2018), 55 54 байта

^(?!(xx)*$|xx+(((x+)(?=\4$))*x$)(?<=(?<!^\5+(x+x))\2))

Попробуйте онлайн! (.NET)
Попробуйте онлайн! (ECMAScript 2018)

# For the purposes of these comments, the input number = N.
^
# Assert that N is not the sum of a prime number and a power of 2.
(?!
    (xx)*$                 # Assert that N is odd.
|
    xx+                    # Force N - \2 to be > 1, because the prime test used
                           # below has a false match of 1, which would otherwise
                           # give us false negatives on de Polignac numbers of the
                           # form 2^M+1, such as 262145 and 2097153.
    (((x+)(?=\4$))*x$)     # Cycle through subtracting all possible powers of 2 from
                           # tail, so we can then test {N - {power of 2}} for being
                           # prime.
                           # \2 = the power of 2
    (?<=
        (?<!^\5+(x+x))     # Test tail for being prime. If it matches, this will fail
                           # the outside negative lookahead, showing that N is not a
                           # de Polignac number.
        \2                 # tail = N - \2
    )
)

Mathematica, 41 байт

OddQ@#&&!Or@@PrimeQ[#-2^Range[0,Log2@#]]&

PHP , 75 байт

печатает 1 для правды и 0 для фальши

for($t=1&$argn;0<$d=$n=$argn-2**$i++;$d-1?:$t&=0)for(;--$d&&$n%$d;);echo$t;

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

Попробуйте онлайн! Полиньяк целых чисел до 10000

Par / GP , 34 байта

n->n%2*prod(i=0,n,!isprime(n-2^i))

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

Брахилог , 15 13 байт

/₂ℕ|>ṗ;?-₍ḃ+1

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

Выходные числа де Полиньяк до 1000.

Возвращает false.для чисел де Полиньяк и в true.противном случае.

Основано на удаленном ответе @ LeakyNun, с несколькими исправлениями ошибок (опубликовано с их разрешения).

(-2 байта, используя метод @Jonathan Allan, чтобы проверить, является ли число степенью двойки.)

Данный номер не является номером де Полиньяка, если:

/₂ℕ              It's an even number
   |>ṗ           Or there exists a prime number less than the input
      ;?-₍       which when subtracted from the input
          ḃ      gives a result that has a binary form
           +     such that the sum of the bits 
            1    is 1

Желе , 13 байт

ÆRạl2=Ḟ$o/o‘Ḃ

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

ÆRạl2=Ḟ$o/     Main link; argument is z
ÆR             Generate all primes in the range [2..z]
  ạ            Absolute difference with z for each prime
   l2          Logarithm Base 2
     =Ḟ$       For each one, check if it's equal to its floored value (i.e. if it is an integer)
        o/     Reduce by Logical OR to check if any prime plus a power of two equals the z
          o‘Ḃ  Or it's not an odd number. If it's not an odd number, then automatically return 1 (false).

Выходы 1для ложных и 0истинных.

Perl 6 , 55 байт

{so$_%2&&$_∉((1,2,4...*>$_) [X+] grep &is-prime,^$_)}

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

• (1, 2, 4 ... * > $_) является последовательностью степеней двойки до входного аргумента (Perl выводит геометрический ряд из предоставленных элементов).
• grep &is-prime, ^$_ список простых чисел до входного аргумента.
• [X+] оценивает сумму всех элементов перекрестного произведения двух рядов.

Я мог бы обойтись без soна два байта меньше, но тогда он возвращает два разных ложных значения ( 0и False).

Аксиома, 86 байт

f(n:PI):Boolean==(~odd?(n)=>false;d:=1;repeat(n<=d or prime?(n-d)=>break;d:=d*2);n<=d)

тест и результаты

(21) -> for i in 1..600 repeat if f(i) then output i
   1
   127
   149
   251
   331
   337
   373
   509
   599

Haskell, 104 102 байта

p x=[x]==[i|i<-[2..x],x`mod`i<1]
h k|even k=1>2|2>1=notElem k$((+)<$>(2^)<$>[0..k])<*>filter(p)[1..k]

объяснение

• p - это функция, которая находит простые числа (очень неэффективно!)
• Создание списка (+)примененной к 2 ^ частичной функции, которая применяется к списку [0..input]
• Применяя вышеизложенное к списку, отфильтрованному 1 для ввода простых чисел
• Результирующий декартово произведение каждого возможного значения ищется, чтобы убедиться, что в декартовом произведении нет входных данных.
• Охраняется, чтобы гарантировать, что четный ввод автоматически ложен.

ОБНОВЛЕНИЕ: кричите Einkorn Enchanter для игры в гольф два байта!

Common Lisp, 134 байта

(lambda(x)(flet((p(x)(loop for i from 2 below x always(>(mod x i)0))))(or(evenp x)(do((j 1(* j 2))(m()(p(- x j))))((or(>= j x)m)m)))))

Возврат, NILесли аргумент является числом Полиньяка, в Tпротивном случае.

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

Ungolfed:

(lambda (n)
  (flet ((prime? (x)                 ; x is prime
           loop for i from 2 below x ; if for i in [2..n-1]
           always (> (mod x i) 0)))  ; is x is not divisible by i
    (or (evenp n)                    ; if n is even is not a Polignac number
        (do ((j 1( * j 2))           ; loop with j = 2^i, i = 0, 1,... 
             (m () (prime? (- n j)))); m = n - 2^i is prime?
            ((or (>= j n)            ; terminate if 2^i ≥ n
                 m)                  ; or if n - 2^i is prime
             m)))))                  ; not a polignac if n - 2^i is prime

APL (Dyalog Extended) , 12 байт

⍱2∘|⍲0⍭⊢-2*…

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

Анонимный префикс неявной функции. Возвращает 1 для правдивых, 0 для ложных.

В значительной степени основано на ответе Japt ETHProductions .

Спасибо @ Adám за помощь в игре в гольф, мой оригинальный ответ, и за создание Dyalog Extended в этом отношении.

Как:

⍱2∘|⍲0⍭⊢-2*…   ⍝ Tacit prefix function; input will be called ⍵
           …    ⍝ Inclusive Range [0..⍵]
         2*     ⍝ 2 to the power of each number in the range
       ⊢-       ⍝ Subtract each from ⍵
     0⍭         ⍝ Non-primality check on each resulting number
    ⍲           ⍝ Logical NAND
 2∘|            ⍝ Mod 2
⍱               ⍝ Not any (bitwise OR reduction, then negated)

Python 2 , 98 байт

lambda x:not(x%2<1or any((lambda x:x>1and all(x%j for j in range(2,x)))(x-2**i)for i in range(x)))

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

Pyth , 14 байт

&%Q2!smP-^2dQl

Попытайся!

Юлия 0,4 , 31 байт

n->n%2*!any(ispow2,n-primes(n))

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

APL (NARS) 80 символов, 160 байтов

∇r←f w;n
r←¯1⋄→0×⍳(w≤0)∨w≥9E9⋄r←0⋄→0×⍳0=2∣w⋄n←r←1
→0×⍳w≤n⋄→3×⍳0πw-n⋄n×←2⋄→2
r←0
∇

Функция 0π - это функция, которая возвращает свой аргумент, простое или нет. Для меня эта функция не должна быть рекурсивной, поэтому она немного длиннее ... Тест:

  {1=f ⍵:⍵⋄⍬}¨1..1000
1  127  149  251  331  337  373  509  599  701  757  809  877  905  907  959  977  997 

для входа <= 0 или входа> = 9E9 возвращается ¯1 (ошибка)

  f¨0 ¯1 ¯2 900000000001
¯1 ¯1 ¯1 ¯1 

C # (интерактивный компилятор Visual C #) , 107 байт

x=>{var r=Enumerable.Range(2,x);return x%2>0&r.All(p=>r.Any(d=>d<p&p%d<1)|r.All(n=>x!=p+Math.Pow(2,n-2)));}

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

Не самый эффективный код, но, похоже, работает. Мое оригинальное решение отфильтровывало простые числа перед проверкой их в формуле, и оно работало намного лучше. Текущая версия на 11 байт короче.

// input x is an integer
x=>{
  // we need to generate several
  // ranges. since this is verbose,
  // generate 1 and keep a reference
  var r=Enumerable.Range(2,x);
  // this is the main condition
  return
     // input must be odd
     x%2>0&
     // generate all possible p's
     // over our range and ensure that
     // they satisfy the following
     r.All(p=>
       // either p is not prime
       r.Any(d=>d<p&p%d<1)
       |
       // or there is no n that satisfies
       // the formula: x=p+2^n
       r.All(n=>x!=p+Math.Pow(2,n-2))
     );
}