Rosetta Code

De Polignac numbers

Revision as of 01:07, 27 September 2022 by Wherrera (talk | contribs) (→‎{{header|Python}})

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.

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.

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

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
Retrieved from "https://rosettacode.org/wiki/De_Polignac_numbers?oldid=330705"