# 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, 2017 at 15:33
• @Okx I'm going to say no. Jun 30, 2017 at 15:33
• Jun 30, 2017 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. Jan 31, 2019 at 18:25
• @MagicOctopusUrn Yes. Jan 31, 2019 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. Jun 30, 2017 at 15:42
• @Shaggy 3 is fixed, but we didn't have to handle even cases at first. Fixing. Jun 30, 2017 at 15:43
• @Shaggy Fixed now. Jun 30, 2017 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! Jun 30, 2017 at 15:50
• :O +1 for competitive program that doesn't look like encoding error Jun 30, 2017 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/… Jun 30, 2017 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 :-) Jun 30, 2017 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 Jun 30, 2017 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. Feb 3, 2019 at 6:20
• @Deadcode Thanks for reporting this. Now fixed. Feb 3, 2019 at 10:23
• @Arnauld Ah, you're right :) Just to be certain, I did this and sure enough, it's fixed. Feb 3, 2019 at 20:47
• @Deadcode Neat! :) Feb 6, 2019 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. Feb 3, 2019 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,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        []       [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,0],]  [[1,0,0],[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               []       [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              []       [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               []       [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 :-) Jul 1, 2017 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. Jul 1, 2017 at 14:09
• @Emigna Ah. I knew there was a 1-byte alternative to that!
– Okx
Jul 1, 2017 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? Jan 31, 2019 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. Feb 1, 2019 at 0:16
• @Deadcode explicit check to make sure the "prime" isn't 1; should work now Feb 4, 2019 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 Apr 21, 2019 at 16:54
• My shortest is very slow, though Apr 21, 2019 at 16:55
• oh, (x(xx)+|\3\3+) -> (x\3?(xx)+) Apr 21, 2019 at 17:03

# Mathematica, 41 bytes

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

• There's no builtin for this? Wow, I'm surprised. Jun 30, 2017 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]. Jun 30, 2017 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. Aug 10, 2018 at 13:20
• Note to (non mobile) self: 14 bytes Try it online!. Inspired by Jonathan Allan's Jelly answer. Aug 10, 2018 at 23:50
• Aug 11, 2018 at 0:16
• Reminder for your notes i guess? Aug 20, 2018 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. Feb 1, 2019 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. Jun 30, 2017 at 19:35
• @EinkornEnchanter Great catch! You golfed me two bytes! Jul 1, 2017 at 13:59
• You can also do filter p[1..k] instead of filter(p)[1..k] Jul 1, 2017 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))
);
}