21
\$\begingroup\$

A number is a de Polignac number if and only if it is odd and cannot be represented in the form p + 2n where n is a non-negative integer and p is a prime integer.

Task

Write some code that takes a positive integer and determines if it is a de Polignac number. You may output two distinct values one for true and one for false. You should aim to minimize your byte count.

Test Cases

For positive cases here's the 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, ...

Here are some negative cases:

22, 57
\$\endgroup\$
5
  • \$\begingroup\$ Can we have truthy and falsy outputs instead of two distinct outputs? \$\endgroup\$
    – Okx
    Jun 30, 2017 at 15:33
  • \$\begingroup\$ @Okx I'm going to say no. \$\endgroup\$
    – Wheat Wizard
    Jun 30, 2017 at 15:33
  • \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$
    – Wheat Wizard
    Jun 30, 2017 at 15:41
  • 1
    \$\begingroup\$ Err... for the negative cases, it's basically any number not in the OEIS right? Making sure I've not missed something obvious. \$\endgroup\$ Jan 31, 2019 at 18:25
  • 1
    \$\begingroup\$ @MagicOctopusUrn Yes. \$\endgroup\$
    – Wheat Wizard
    Jan 31, 2019 at 18:30

23 Answers 23

11
\$\begingroup\$

Japt, 9 14 13 bytes

o!²mnU dj |Uv

Test it online! or Find all de Polignac integers under 1000.

Outputs 1 for falsy inputs and 0 for truthy.

Explanation

 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
\$\endgroup\$
5
  • \$\begingroup\$ This seems to be giving the wrong results for 2 & 3; it's returning false but they're not de Polignac numbers. \$\endgroup\$
    – Shaggy
    Jun 30, 2017 at 15:42
  • \$\begingroup\$ @Shaggy 3 is fixed, but we didn't have to handle even cases at first. Fixing. \$\endgroup\$ Jun 30, 2017 at 15:43
  • \$\begingroup\$ @Shaggy Fixed now. \$\endgroup\$ Jun 30, 2017 at 15:49
  • \$\begingroup\$ I was about to say it was a good thing the fix for 3 didn't cost any bytes then I saw the fix for 2 - Ouch! \$\endgroup\$
    – Shaggy
    Jun 30, 2017 at 15:50
  • \$\begingroup\$ :O +1 for competitive program that doesn't look like encoding error \$\endgroup\$
    – Downgoat
    Jun 30, 2017 at 21:34
8
\$\begingroup\$

Jelly, 11 10 bytes

Saved 1 byte thanks to @Dennis

Ḷ2*³_ÆPS<Ḃ

Try it online!

How it works

Ḷ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.
\$\endgroup\$
2
8
\$\begingroup\$

JavaScript (ES6),  56 54  53 bytes

Returns \$0\$ or \$1\$.

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

Try it online!

How?

We start with \$p = 1\$. We test whether \$y = n - p\$ is composite and yield a boolean accordingly. The next test is performed with \$p \times 2\$.

As soon as \$p\$ is greater than \$n\$, we stop the recursion and return \$n\$.

The results of all iterations are AND'd together, coercing the boolean values to either \$0\$ or \$1\$.

Provided that all intermediate results were truthy, we end up with a bitwise test such as:

1 & 1 & 1 & n

This gives \$1\$ if and only if \$n\$ is odd, which is the last condition required to validate the input as a de Polignac number.

\$\endgroup\$
8
  • 3
    \$\begingroup\$ Great technique. Probably the only valid answer that doesn't explicitly say n%2 or similar :P \$\endgroup\$ Jun 30, 2017 at 16:16
  • \$\begingroup\$ This has false negatives for de Polignac numbers of the form 2^M+1, such as 262145 and 2097153 (subsequent ones are 4722366482869645213697, 38685626227668133590597633, 5192296858534827628530496329220097, etc.). It's not the largeness of the numbers that's a problem, since it correctly identifies 262139, 262259, 2097131, and 2097187, for example. Of course due to the recursion, I had to enlarge the stack size to something very huge to test this, and only tested the ranges around the first two 2^M+1 de Polignac numbers listed above. \$\endgroup\$
    – Deadcode
    Feb 3, 2019 at 6:20
  • 1
    \$\begingroup\$ @Deadcode Thanks for reporting this. Now fixed. \$\endgroup\$
    – Arnauld
    Feb 3, 2019 at 10:23
  • 1
    \$\begingroup\$ @Arnauld Ah, you're right :) Just to be certain, I did this and sure enough, it's fixed. \$\endgroup\$
    – Deadcode
    Feb 3, 2019 at 20:47
  • 1
    \$\begingroup\$ @Deadcode Neat! :) \$\endgroup\$
    – Arnauld
    Feb 6, 2019 at 4:03
7
\$\begingroup\$

Python 2, 60 57 56 bytes

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

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Wow, this is impressively inefficient. Prime test via Wilson's theorem. On the plus side it works correctly for 262145 and 2097153 (assuming unlimited stack and bignum size); some of the other submissions don't. Its is-prime algorithm yields "truthy" for 4, because (-6)%4=2, but this ends up not being a problem because even numbers are rejected by the &n&. The number 5 would be a false negative if it were a de Polignac number, because 1+4=5, but this isn't a problem because 2+3=5 anyway. \$\endgroup\$
    – Deadcode
    Feb 3, 2019 at 6:15
7
\$\begingroup\$

Jelly, 10 bytes

An alternative 10-byte Jelly submission to the one already posted.

_ÆRBS€’×ḂẠ

A monadic link returning 1 for de Polignac numbers and 0 otherwise.

Try it online! or see those under 1000.

How?

_Æ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
\$\endgroup\$
1
  • \$\begingroup\$ Took me about 10 minutes to understand how this works... great technique, I couldn't think of a good way to check if an array contained no powers of two :-) \$\endgroup\$ Jul 1, 2017 at 15:51
7
\$\begingroup\$

05AB1E, 9 8 bytes

-1 byte thanks to Emigna

Ýo-pZ¹È~

Outputs 0 for truthy inputs and 1 for falsy inputs.

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ could be Z. \$\endgroup\$
    – Emigna
    Jul 1, 2017 at 14:09
  • \$\begingroup\$ @Emigna Ah. I knew there was a 1-byte alternative to that! \$\endgroup\$
    – Okx
    Jul 1, 2017 at 14:13
6
\$\begingroup\$

Python 2, 99 bytes

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

Try it online!

-4 bytes thanks to Leaky Nun

-2 bytes thanks to Wondercricket

+8 bytes to fix a mistake

-1 byte thanks to Mr. Xcoder

-3 bytes thanks to Einkorn Enchanter

+12 bytes to fix a mistake

\$\endgroup\$
3
  • \$\begingroup\$ I think this is also a Python 3 compatible answer? \$\endgroup\$ Jan 31, 2019 at 21:50
  • \$\begingroup\$ This has a false negative for 1 and for all de Polignac numbers of the form 2^M+1, such as 262145 and 2097153 (subsequent ones are 4722366482869645213697, 38685626227668133590597633, 5192296858534827628530496329220097, etc.). It's not the largeness of the numbers that's a problem, since it correctly identifies 262139, 262259, 2097131, and 2097187, for example. \$\endgroup\$
    – Deadcode
    Feb 1, 2019 at 0:16
  • 1
    \$\begingroup\$ @Deadcode explicit check to make sure the "prime" isn't 1; should work now \$\endgroup\$
    – hyper-neutrino
    Feb 4, 2019 at 0:40
6
\$\begingroup\$

Regex (ECMAScript), 97 bytes

This problem posed an interesting case for working around the problem of lacking non-atomic lookahead. And it's the only time so far that I've had a good reason to put both versions of the power of 2 test, ((x+)(?=\2$))*x$ and (?!(x(xx)+)\1*$), in the same regex, and the only time so far I've needed to protect the prime test against matching 1, as (?!(xx+)\1+$)xx, when used in a larger regex.

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

Try it online!

# 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 + molecular lookahead), 53 52 bytes

^(?!(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.
)

This version is not only much cleaner, but much faster, because instead of having to cycle through all possible ways that N is the sum of two numbers, it can just cycle through subtracting every power of 2 from N and test the difference for being prime.

The molecular lookahead can be easily converted to a variable-length lookbehind:

Regex (.NET or ECMAScript 2018), 55 54 bytes

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

Try it online! (.NET)
Try it online! (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
    )
)
\$\endgroup\$
3
  • \$\begingroup\$ Your regex can be optimised to ^(?!(x+)((?!(xx+)\3+$)x*(?!(x(xx)+)\4*$)|x(?!(x(xx)+)\6*$)x*(?!(xx+)\8+$)x)?\1$) without too much difficulty. Then, with some careful thought, can be golfed further to ^(?!(x+)((x?)(?!(x(x\3)+)\4+$)x*(?!(x(xx)+|\3\3+)\6+$)\3)?\1$). Shorter may yet be possible \$\endgroup\$
    – H.PWiz
    Apr 21, 2019 at 16:54
  • \$\begingroup\$ My shortest is very slow, though \$\endgroup\$
    – H.PWiz
    Apr 21, 2019 at 16:55
  • \$\begingroup\$ oh, (x(xx)+|\3\3+) -> (x\3?(xx)+) \$\endgroup\$
    – H.PWiz
    Apr 21, 2019 at 17:03
4
\$\begingroup\$

Mathematica, 41 bytes

OddQ@#&&!Or@@PrimeQ[#-2^Range[0,Log2@#]]&
\$\endgroup\$
2
  • 1
    \$\begingroup\$ There's no builtin for this? Wow, I'm surprised. \$\endgroup\$
    – hyper-neutrino
    Jun 30, 2017 at 16:11
  • 1
    \$\begingroup\$ It's so annoying here that Mathematica deems negative primes to be prime, or else you could save bytes by replacing PrimeQ[#-2^Range[0,Log2@#]] with PrimeQ[#-2^Range[0,#]] and then by PrimeQ[#-2^Range@#/2]. \$\endgroup\$ Jun 30, 2017 at 17:58
4
\$\begingroup\$

PHP, 75 bytes

prints 1 for truthy and 0 for falsy

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

Try it online!

Try it online! Polignac Integers under 10000

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

Pari/GP, 34 bytes

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

Try it online!

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

Brachylog, 15 13 bytes

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

Try it online!

Output de Polignac numbers upto 1000.

Returns false. for de Polignac numbers and true. otherwise.

Based on @LeakyNun's deleted answer, with a few bugfixes (posted with their permission).

(-2 bytes by using @Jonathan Allan's method to check if the number is a power of two.)

The given number is not a de Polignac number if:

/₂ℕ              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
\$\endgroup\$
8
  • \$\begingroup\$ =h2 would be 1 byte shorter but it doesn't work for 3 either. \$\endgroup\$
    – Fatalize
    Aug 10, 2018 at 13:20
  • \$\begingroup\$ Note to (non mobile) self: 14 bytes Try it online!. Inspired by Jonathan Allan's Jelly answer. \$\endgroup\$
    – Sundar R
    Aug 10, 2018 at 23:50
  • \$\begingroup\$ 13 Try it online! \$\endgroup\$
    – Sundar R
    Aug 11, 2018 at 0:16
  • \$\begingroup\$ Reminder for your notes i guess? \$\endgroup\$
    – Kroppeb
    Aug 20, 2018 at 23:06
  • 1
    \$\begingroup\$ @Deadcode It used to be working when this was posted, and something about division seems to have changed in the meantime - for eg. Try it online! returns false instead of 64. The change is likely from this commit to the language, but I haven't been active here in a while, so don't know if it's intentional or a bug. \$\endgroup\$
    – Sundar R
    Feb 1, 2019 at 14:04
3
\$\begingroup\$

Jelly, 13 bytes

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

Try it online!

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

Outputs 1 for false and 0 for true.

\$\endgroup\$
6
  • \$\begingroup\$ Ḷ2*ạfÆRṆ then check for parity \$\endgroup\$
    – Leaky Nun
    Jun 30, 2017 at 16:29
  • \$\begingroup\$ @LeakyNun Ḷ2*ạfÆRṆo‘Ḃ returns 1 for both 127 and 22; that's not right. Unless that's not what you suggested. \$\endgroup\$
    – hyper-neutrino
    Jun 30, 2017 at 16:31
  • \$\begingroup\$ you need to use and, not or. (or you can remove my last negation and then proceed to do it in 9/10 bytes) \$\endgroup\$
    – Leaky Nun
    Jun 30, 2017 at 16:32
  • \$\begingroup\$ @LeakyNun Your snippet there gives 0 for 149. \$\endgroup\$ Jun 30, 2017 at 16:33
  • \$\begingroup\$ @ETHproductions right. Changing to _@ fixes it. \$\endgroup\$
    – Leaky Nun
    Jun 30, 2017 at 16:36
2
\$\begingroup\$

Perl 6, 55 bytes

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

Try it online!

  • (1, 2, 4 ... * > $_) is a sequence of the powers of two until the input argument (Perl infers the geometric series from the provided elements).
  • grep &is-prime, ^$_ is the list of prime numbers up to the input argument.
  • [X+] evaluates the sum of all elements of the cross product of the two series.

I could have done without the so for two bytes less, but then it returns two distinct falsy values (0 and False).

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

Axiom, 86 bytes

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

test and results

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

Haskell, 104 102 bytes

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]

Explanation

  • p is a function that finds prime numbers (very inefficient!)
  • Creating a list of (+) applied to 2^ partial function which is applied to a list [0..input]
  • Applying the above to a list filtered 1 to input for primes
  • Resulting cartesian product of every possible value is searched to ensure input does not exist in cartesian product
  • Guarded to ensure that an even input is automatically false.

UPDATE: Shout out to Einkorn Enchanter for golfing two bytes!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ p x=[x]==[i|i<-[2..x],x`mod`i<1] is a shorter primality test. \$\endgroup\$
    – Wheat Wizard
    Jun 30, 2017 at 19:35
  • \$\begingroup\$ @EinkornEnchanter Great catch! You golfed me two bytes! \$\endgroup\$ Jul 1, 2017 at 13:59
  • 1
    \$\begingroup\$ You can also do filter p[1..k] instead of filter(p)[1..k] \$\endgroup\$
    – Wheat Wizard
    Jul 1, 2017 at 14:02
1
\$\begingroup\$

Common Lisp, 134 bytes

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

Return NIL when the argument is a Polignac number, T otherwise.

Try it online!

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

APL (Dyalog Extended), 12 bytes

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

Try it online!

Anonymous prefix tacit function. Returns 1 for truthy, 0 for falsy.

Largely based on ETHProductions' Japt answer.

Thanks to @Adám for helping with golfing my original answer, and for making Dyalog Extended for that matter.

How:

⍱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)
 
\$\endgroup\$
0
\$\begingroup\$

Python 2, 98 bytes

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

Try it online!

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

Pyth, 14 bytes

&%Q2!smP-^2dQl

Try it!

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

Julia 0.4, 31 bytes

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

Try it online!

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

APL(NARS) 80 chars, 160 bytes

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

The function 0π is the function that return its argument is prime or not. For me this function has not be recursive so it is a little more long... Test:

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

for input <=0 or input >=9E9 it return ¯1 (error)

  f¨0 ¯1 ¯2 900000000001
¯1 ¯1 ¯1 ¯1 
\$\endgroup\$
0
\$\begingroup\$

C# (Visual C# Interactive Compiler), 107 bytes

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

Try it online!

Not the most efficient code, but seems to work. My original solution filtered for primes before testing them in the formula and it performed much better. The current version is 11 bytes shorter.

// 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))
     );
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.