De Polignac numbers
De Polignac numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Alphonse de Polignac, a French mathematician in the 1800s, conjectured that every positive odd integer could be formed from the sum of a power of 2 and a prime number.
He was subsequently proved incorrect.
The numbers that fail this condition are now known as de Polignac numbers.
Technically 1 is a de Polignac number, as there is no prime and power of 2 that sum to 1. De Polignac was aware but thought that 1 was a special case. However.
127 is also fails that condition, as there is no prime and power of 2 that sum to 127.
As it turns out, de Polignac numbers are not uncommon, in fact, there are an infinite number of them.
- Task
- Find and display the first fifty de Polignac numbers.
- Stretch
- Find and display the one thousandth de Polignac number.
- Find and display the ten thousandth de Polignac number.
- See also
J
Implementation:
depolignac=: (1+i.@>.&.-:) (-.,) i.@>.&.(2&^.) +/ i.&.(p:inv)
Task example:
5 10$depolignac 3000
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 1985 2171 2203 2213
Stretch:
T=: depolignac 3e5
999 { T
31941
9999 { T
273421
(We use 999 here for the 1000th number because 0 is the first J index.)
Phix
with javascript_semantics constant MAX_VALUE = 1_000_000, all_primes = get_primes_le(MAX_VALUE), powers_of_2 = sq_power(2,tagset(floor(log2(MAX_VALUE)),0)) sequence allvalues = repeat(true,MAX_VALUE), dePolignac = {} for i in all_primes do for j in powers_of_2 do if i + j < MAX_VALUE then allvalues[i + j] = false end if end for end for for n=1 to MAX_VALUE by 2 do if allvalues[n] then dePolignac &= n end if end for printf(1,"First fifty de Polignac numbers:\n%s\n",{join_by(dePolignac[1..50],1,10,"",fmt:="%5d")}) printf(1,"One thousandth: %,d\n",dePolignac[1000]) printf(1,"Ten thousandth: %,d\n",dePolignac[10000])
- Output:
First fifty de Polignac numbers: 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 1985 2171 2203 2213 One thousandth: 31,941 Ten thousandth: 273,421
Python
''' Rosetta code rosettacode.org/wiki/De_Polignac_numbers '''
from sympy import isprime
from math import log
from numpy import ndarray
max_value = 1_000_000
all_primes = [i for i in range(max_value + 1) if isprime(i)]
powers_of_2 = [2**i for i in range(int(log(max_value, 2)))]
allvalues = ndarray(max_value, dtype=bool)
allvalues[:] = True
for i in all_primes:
for j in powers_of_2:
if i + j < max_value:
allvalues[i + j] = False
dePolignac = [n for n in range(1, max_value) if n & 1 == 1 and allvalues[n]]
print('First fifty de Polignac numbers:')
for i, n in enumerate(dePolignac[:50]):
print(f'{n:5}', end='\n' if (i + 1) % 10 == 0 else '')
print(f'\nOne thousandth: {dePolignac[999]:,}')
print(f'\nTen thousandth: {dePolignac[9999]:,}')
- Output:
First fifty de Polignac numbers: 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 1985 2171 2203 2213 One thousandth: 31,941 Ten thousandth: 273,421
Raku
use List::Divvy;
use Lingua::EN::Numbers;
constant @po2 = (1..∞).map: 2 ** *;
my @dePolignac = lazy 1, |(2..∞).hyper.map(* × 2 + 1).grep: -> $n { all @po2.&upto($n).map: { !is-prime $n - $_ } };
say "First fifty de Polignac numbers:\n" ~ @dePolignac[^50]».&comma».fmt("%5s").batch(10).join: "\n";
say "\nOne thousandth: " ~ comma @dePolignac[999];
say "\nTen thousandth: " ~ comma @dePolignac[9999];
- Output:
First fifty de Polignac numbers: 1 127 149 251 331 337 373 509 599 701 757 809 877 905 907 959 977 997 1,019 1,087 1,199 1,207 1,211 1,243 1,259 1,271 1,477 1,529 1,541 1,549 1,589 1,597 1,619 1,649 1,657 1,719 1,759 1,777 1,783 1,807 1,829 1,859 1,867 1,927 1,969 1,973 1,985 2,171 2,203 2,213 One thousandth: 31,941 Ten thousandth: 273,421
Wren
import "./math" for Int
import "./fmt" for Fmt
var pows2 = (0..19).map { |i| 1 << i }.toList
var dp = [1]
var dp1000
var dp10000
var count = 1
var n = 3
while (true) {
var found = false
for (pow in pows2) {
if (pow > n) break
if (Int.isPrime(n-pow)) {
found = true
break
}
}
if (!found) {
count = count + 1
if (count <= 50) {
dp.add(n)
} else if (count == 1000) {
dp1000 = n
} else if (count == 10000) {
dp10000 = n
break
}
}
n = n + 2
}
System.print("First 50 De Polignac numbers:")
Fmt.tprint("$,5d", dp, 10)
Fmt.print("\nOne thousandth: $,d", dp1000)
Fmt.print("\nTen thousandth: $,d", dp10000)
- Output:
First 50 De Polignac numbers: 1 127 149 251 331 337 373 509 599 701 757 809 877 905 907 959 977 997 1,019 1,087 1,199 1,207 1,211 1,243 1,259 1,271 1,477 1,529 1,541 1,549 1,589 1,597 1,619 1,649 1,657 1,719 1,759 1,777 1,783 1,807 1,829 1,859 1,867 1,927 1,969 1,973 1,985 2,171 2,203 2,213 One thousandth: 31,941 Ten thousandth: 273,421