De Polignac numbers

From Rosetta Code
Revision as of 10:28, 27 September 2022 by PureFox (talk | contribs) (Added Wren)
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

Translation of: Python
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

Library: Wren-math
Library: Wren-fmt
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