# Is my number a de Polignac number?

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.

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

• Can we have truthy and falsy outputs instead of two distinct outputs? – Okx Jun 30 '17 at 15:33
• @Okx I'm going to say no. – Sriotchilism O'Zaic Jun 30 '17 at 15:33
• – Sriotchilism O'Zaic Jun 30 '17 at 15:41
• Err... for the negative cases, it's basically any number not in the OEIS right? Making sure I've not missed something obvious. – Magic Octopus Urn Jan 31 at 18:25
• @MagicOctopusUrn Yes. – Sriotchilism O'Zaic Jan 31 at 18:30

# Japt, 914 13 bytes

o!²mnU dj |Uv


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

• This seems to be giving the wrong results for 2 & 3; it's returning false but they're not de Polignac numbers. – Shaggy Jun 30 '17 at 15:42
• @Shaggy 3 is fixed, but we didn't have to handle even cases at first. Fixing. – ETHproductions Jun 30 '17 at 15:43
• @Shaggy Fixed now. – ETHproductions Jun 30 '17 at 15:49
• 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! – Shaggy Jun 30 '17 at 15:50
• :O +1 for competitive program that doesn't look like encoding error – Downgoat Jun 30 '17 at 21:34

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

• Ḷ2*⁸_ÆPS<Ḃ saves a byte. tio.run/##ASQA2/9qZWxsef//4bi2Mirigbhfw4ZQUzzhuIL/… – Dennis Jun 30 '17 at 16:41
• @Dennis Thanks, I knew there had to be a 3-byte alternative to ¬;ḂẠ. S<Ḃ is way outside the box though, at least for me :-) – ETHproductions Jun 30 '17 at 16:51

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

• Great technique. Probably the only valid answer that doesn't explicitly say n%2 or similar :P – ETHproductions Jun 30 '17 at 16:16
• 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. – Deadcode Feb 3 at 6:20
• @Deadcode Thanks for reporting this. Now fixed. – Arnauld Feb 3 at 10:23
• @Arnauld Ah, you're right :) Just to be certain, I did this and sure enough, it's fixed. – Deadcode Feb 3 at 20:47
• @Deadcode Neat! :) – Arnauld Feb 6 at 4:03

# Python 2, 6057 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!

• 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. – Deadcode Feb 3 at 6:15

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

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

• 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 :-) – ETHproductions Jul 1 '17 at 15:51

# 05AB1E, 9 8 bytes

-1 byte thanks to Emigna

Ýo-pZ¹È~


Outputs 0 for truthy inputs and 1 for falsy inputs.

Try it online!

• 1å could be Z. – Emigna Jul 1 '17 at 14:09
• @Emigna Ah. I knew there was a 1-byte alternative to that! – Okx Jul 1 '17 at 14:13

# 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

• I think this is also a Python 3 compatible answer? – Ari Cooper-Davis Jan 31 at 21:50
• 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. – Deadcode Feb 1 at 0:16
• @Deadcode explicit check to make sure the "prime" isn't 1; should work now – HyperNeutrino Feb 4 at 0:40

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

• 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 – H.PWiz Apr 21 at 16:54
• My shortest is very slow, though – H.PWiz Apr 21 at 16:55
• oh, (x(xx)+|\3\3+) -> (x\3?(xx)+) – H.PWiz Apr 21 at 17:03

# Mathematica, 41 bytes

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

• There's no builtin for this? Wow, I'm surprised. – HyperNeutrino Jun 30 '17 at 16:11
• 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]. – Greg Martin Jun 30 '17 at 17:58

# 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

# Pari/GP, 34 bytes

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


Try it online!

# 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

• =h2 would be 1 byte shorter but it doesn't work for 3 either. – Fatalize Aug 10 '18 at 13:20
• Note to (non mobile) self: 14 bytes Try it online!. Inspired by Jonathan Allan's Jelly answer. – sundar Aug 10 '18 at 23:50
• – sundar Aug 11 '18 at 0:16
• Reminder for your notes i guess? – Kroppeb Aug 20 '18 at 23:06
• @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. – sundar Feb 1 at 14:04

# 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
• 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). # 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  # Haskell, 104 102 bytes p x=[x]==[i|i<-[2..x],xmodi<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!

• p x=[x]==[i|i<-[2..x],xmodi<1] is a shorter primality test. – Sriotchilism O'Zaic Jun 30 '17 at 19:35
• @EinkornEnchanter Great catch! You golfed me two bytes! – maple_shaft Jul 1 '17 at 13:59
• You can also do filter p[1..k] instead of filter(p)[1..k] – Sriotchilism O'Zaic Jul 1 '17 at 14:02

# 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


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


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

# Pyth, 14 bytes

&%Q2!smP-^2dQl


Try it!

# Julia 0.4, 31 bytes

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


Try it online!

# 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


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