Prime numbers whose neighboring pairs are tetraprimes
Prime numbers whose neighboring pairs are tetraprimes 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.
- Definitions
The following definitions are needed for this task.
A tetraprime is a positive integer which is the product of four distinct primes. For example, 1155 is a tetraprime because 1155 = 3 x 5 x 7 x 11.
The neighboring pairs of a prime are the two consecutive numbers immediately preceding or immediately following that prime. For example, (5, 6) and (8, 9) are the neighboring pairs of the prime 7.
- Task
1. Find and show here all primes less than 100,000 whose preceding neighboring pair are both tetraprimes.
2. Find and show here all primes less than 100,000 whose following neighboring pair are both tetraprimes.
3. Of the primes in 1 and 2 above how many have a neighboring pair one of whose members has a prime factor of 7?
4. For the primes in 1 and 2 above, consider the gaps between consecutive primes. What are the minimum, median and maximum gaps?
5. Repeat these calculations for all primes less than 1 million but for 1 and 2 just show the number of primes - don't print them out individually.
If it is difficult for your language to meet all of these requirements, then just do what you reasonably can.
- Stretch
Repeat the calculations for all primes less than 10 million.
- References
- OEIS sequence A361796: Prime numbers preceded by two consecutive numbers which are products of four distinct primes (or tetraprimes).
- OEIS sequence A362578: Prime numbers followed by two consecutive numbers which are products of four distinct primes (or tetraprimes).
ALGOL 68
Constructs a table of prime factors without using division/modulo operations.
To run this with Algol 68G, you will need to specify a large heap size, with e.g.: -heap 256M on the command line.
BEGIN # find primes whose neighbouring pairs are tetraprimes - i.e. have 4 #
# distinct prime factors #
PR read "rows.incl.a68" PR # include row utilities, including MEDIAN #
INT max prime = 10 000 000; # the largest possible prime to comsider #
# construct table of prime factor counts #
# numbers with non-distinct prime factors will have negative counts #
[ 0 : max prime + 2 ]INT pfc;
FOR i FROM LWB pfc TO UPB pfc DO pfc[ i ] := 0 OD;
FOR n FROM 2 TO UPB pfc OVER 2 DO
IF pfc[ n ] = 0 THEN # i is prime #
INT power := 1;
INT n to power := n;
INT start := n + n;
WHILE FOR j FROM start BY n to power TO UPB pfc DO
IF pfc[ j ] >= 0 THEN
# no duplicate factors yet #
pfc[ j ] +:= 1
ELSE
# already have a duplicate factor #
pfc[ j ] +:= -1
FI;
IF power > 1 THEN
IF pfc[ j ] > 0 THEN pfc[ j ] := - pfc[ j ] FI
FI
OD;
power +:= 1;
LONG INT long n to power := LENG n to power * n;
long n to power <= UPB pfc
DO
start := n to power := SHORTEN long n to power
OD
FI
OD;
# show the statistics and optionally the primes with a tetraprime pair #
# at offset 1 and offset 2 from the prime #
PROC show neighbour pairs = ( INT max n, BOOL show primes, INT offset 1, offset 2 )VOID:
BEGIN
# array of prime gaps, used to find the median gap #
# should be large enough for the stretch task #
[ 1 : 12 000 ]INT gaps; FOR i TO UPB gaps DO gaps[ i ] := 0 OD;
INT t count := 0, f7 count := 0;
INT prev prime := 0;
INT min gap := max int, max gap := 0, gap pos := 0;
# note the lowest tetraprime is 210 #
FOR i FROM 211 BY 2 TO max n DO
IF pfc[ i ] = 0 THEN
# have a prime #
IF pfc[ i + offset 1 ] = 4 AND pfc[ i + offset 2 ] = 4 THEN
# the previous pair are tetraprimes #
IF prev prime > 0 THEN
INT this gap = i - prev prime;
IF min gap > this gap THEN min gap := this gap FI;
IF max gap < this gap THEN max gap := this gap FI;
gaps[ gap pos +:= 1 ] := this gap
FI;
prev prime := i;
IF ( i + offset 1 ) MOD 7 = 0 OR ( i + offset 2 ) MOD 7 = 0 THEN
f7 count +:= 1
FI;
t count +:= 1;
IF show primes THEN
print( ( " ", whole( i, -5 ) ) );
IF t count MOD 10 = 0 THEN print( ( newline ) ) FI
FI
FI
FI
OD;
IF show primes THEN print( ( newline ) ) ELSE print( ( " " ) ) FI;
print( ( "Found ", whole( t count, 0 ), " such primes", " of which " ) );
print( ( whole( f7 count, 0 ), " have 7 as a factor of one of the pair", newline ) );
IF NOT show primes THEN print( ( " " ) ) FI;
print( ( " gaps between the primes: min: ", whole( min gap, 0 ) ) );
print( ( ", average: ", whole( ROUND AVERAGE gaps[ : gap pos ], 0 ) ) );
print( ( ", median: ", whole( ROUND MEDIAN gaps[ : gap pos ], 0 ) ) );
print( ( ", max: ", whole( max gap, 0 ), newline, newline ) )
END # show neighbour paris # ;
# show some tetraprimes and statistics about them #
PROC show tetraprime neighbours = ( INT max n, BOOL show primes )VOID:
BEGIN
print( ( "Primes below ", whole( max n, 0 ) ) );
print( ( " preceded by a tetraprime pair:", newline ) );
show neighbour pairs( max n, show primes, -1, -2 );
print( ( "Primes below ", whole( max n, 0 ) ) );
print( ( " followed by a tetraprime pair:", newline ) );
show neighbour pairs( max n, show primes, 1, 2 )
END # show tetraprime pairs # ;
# task #
show tetraprime neighbours( 100 000, TRUE );
show tetraprime neighbours( 1 000 000, FALSE );
show tetraprime neighbours( 10 000 000, FALSE )
END- Output:
Primes below 100000 preceded by a tetraprime pair:
8647 15107 20407 20771 21491 23003 23531 24767 24971 27967
29147 33287 34847 36779 42187 42407 42667 43331 43991 46807
46867 51431 52691 52747 53891 54167 58567 63247 63367 69379
71711 73607 73867 74167 76507 76631 76847 80447 83591 84247
86243 87187 87803 89387 93887 97547 97847 98347 99431
Found 49 such primes of which 31 have 7 as a factor of one of the pair
gaps between the primes: min: 56, average: 1891, median: 1208, max: 6460
Primes below 100000 followed by a tetraprime pair:
8293 16553 17389 18289 22153 26893 29209 33409 35509 36293
39233 39829 40493 41809 45589 48109 58393 59629 59753 59981
60493 60913 64013 64921 65713 66169 69221 71329 74093 75577
75853 77689 77933 79393 79609 82913 84533 85853 87589 87701
88681 91153 93889 96017 97381 98453
Found 46 such primes of which 36 have 7 as a factor of one of the pair
gaps between the primes: min: 112, average: 2004, median: 1460, max: 10284
Primes below 1000000 preceded by a tetraprime pair:
Found 885 such primes of which 503 have 7 as a factor of one of the pair
gaps between the primes: min: 4, average: 1119, median: 756, max: 7712
Primes below 1000000 followed by a tetraprime pair:
Found 866 such primes of which 492 have 7 as a factor of one of the pair
gaps between the primes: min: 4, average: 1146, median: 832, max: 10284
Primes below 10000000 preceded by a tetraprime pair:
Found 10815 such primes of which 5176 have 7 as a factor of one of the pair
gaps between the primes: min: 4, average: 924, median: 648, max: 9352
Primes below 10000000 followed by a tetraprime pair:
Found 10551 such primes of which 5069 have 7 as a factor of one of the pair
gaps between the primes: min: 4, average: 947, median: 660, max: 10284
C
This follows the lines of the Wren example except that primesieve is used to iterate through the primes rather than sieving for them in advance. As a result, runs quickly - under 0.8 seconds on my machine.
/* gcc `pkg-config --cflags glib-2.0` tetraprime.c -o tp `pkg-config --libs glib-2.0` -lprimesieve */
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <locale.h>
#include <primesieve.h>
#include <glib.h>
#define TEN_MILLION 10000000
void primeFactors(int n, int *factors, int *length) {
if (n < 2) return;
int count = 0;
int inc[8] = {4, 2, 4, 2, 4, 6, 2, 6};
while (!(n%2)) {
factors[count++] = 2;
n /= 2;
}
while (!(n%3)) {
factors[count++] = 3;
n /= 3;
}
while (!(n%5)) {
factors[count++] = 5;
n /= 5;
}
for (int k = 7, i = 0; k*k <= n; ) {
if (!(n%k)) {
factors[count++] = k;
n /= k;
} else {
k += inc[i];
i = (i + 1) % 8;
}
}
if (n > 1) {
factors[count++] = n;
}
*length = count;
}
bool hasDups(int *pf, int length) {
int i;
if (length == 1) return false;
for (i = 1; i < length; ++i) {
if (pf[i] == pf[i-1]) return true;
}
return false;
}
bool contains(int *pf, int length, int value) {
int i;
for (i = 0; i < length; ++i) {
if (pf[i] == value) return true;
}
return false;
}
int compare(const void* a, const void* b) {
int arg1 = *(const int*)a;
int arg2 = *(const int*)b;
if (arg1 < arg2) return -1;
if (arg1 > arg2) return 1;
return 0;
}
// Note that 'gaps' will only contain even numbers here.
int median(int *gaps, int length) {
int m = length/2;
if (length & 1 == 1) return gaps[m];
return (gaps[m] + gaps[m-1])/2;
}
int main() {
int i, p, c, k, length, sevens, min, max, med;
int j = 100000, sevens1 = 0, sevens2 = 0;
int pf1[24], pf2[24], pf3[24], pf4[24], *gaps;
bool cond1, cond2, cond3, cond4;
const char *t;
GArray *tetras1 = g_array_new(FALSE, FALSE, sizeof(int));
GArray *tetras2 = g_array_new(FALSE, FALSE, sizeof(int));
GArray *tetras;
primesieve_iterator it;
primesieve_init(&it);
setlocale(LC_NUMERIC, "");
while (j <= TEN_MILLION) {
p = primesieve_next_prime(&it);
if (p < j) {
primeFactors(p-2, pf1, &length);
cond1 = length == 4 && !hasDups(pf1, length);
primeFactors(p-1, pf2, &length);
cond2 = length == 4 && !hasDups(pf2, length);
primeFactors(p+1, pf3, &length);
cond3 = length == 4 && !hasDups(pf3, length);
primeFactors(p+2, pf4, &length);
cond4 = length == 4 && !hasDups(pf4, length);
if (cond1 && cond2) {
g_array_append_val(tetras1, p);
if (contains(pf1, 4, 7) || contains(pf2, 4, 7)) ++sevens1;
}
if (cond3 && cond4) {
g_array_append_val(tetras2, p);
if (contains(pf3, 4, 7) || contains(pf4, 4, 7)) ++sevens2;
}
} else {
for (i = 0; i < 2; ++i) {
tetras = (i == 0) ? tetras1 : tetras2;
sevens = (i == 0) ? sevens1 : sevens2;
c = tetras->len;
t = (i == 0) ? "preceding" : "following";
printf("Found %'d primes under %'d whose %s neighboring pair are tetraprimes", c, j, t);
if (j == 100000) {
printf(":\n");
for (k = 0; k < tetras->len; ++k) {
printf("%5d ", g_array_index(tetras, int, k));
if (!((k+1) % 10)) printf("\n");
}
printf("\n");
}
printf("\nof which %'d have a neighboring pair one of whose factors is 7.\n\n", sevens);
length = c - 1;
gaps = (int *)malloc(length * sizeof(int));
for (k = 0; k < length; ++k) {
gaps[k] = g_array_index(tetras, int, k+1) - g_array_index(tetras, int, k);
}
qsort(gaps, length, sizeof(int), compare);
min = gaps[0];
max = gaps[length - 1];
med = median(gaps, length);
printf("Minimum gap between those %'d primes : %'d\n", c, min);
printf("Median gap between those %'d primes : %'d\n", c, med);
printf("Maximum gap between those %'d primes : %'d\n", c, max);
printf("\n");
free(gaps);
}
j *= 10;
}
}
g_array_free(tetras1, FALSE);
g_array_free(tetras2, FALSE);
return 0;
}
- Output:
Identical to Wren example.
FreeBASIC
#include "isprime.bas"
Dim Shared As Boolean Have7 'A tetraprime factor is 7
Function isTetraprime(n As Integer) As Boolean
Dim As Boolean distinto
Dim As Integer div = 2, count = 0
While n >= div*div
distinto = True
While n Mod div = 0
If Not distinto Then Return False
distinto = False
count += 1
If div = 7 Then Have7 = True
n /= div
Wend
div += 1
Wend
If n > 1 Then count += 1
Return count = 4
End Function
Dim As Integer signo = -1
Dim As Integer TenPower = 1e5
Dim As Integer f, g, n, m, count, count7
Dim As Integer Gap, GapMin, GapMax, GapSum
For f = 5 To 7
For g = 1 To 2 'preceding or following neighboring pairs
count = 0
count7 = 0
m = 0
GapMin = -1
GapMax = 0
GapSum = 0
If f = 5 Then Print '100_000
For n = 3 To TenPower-1
If isPrime(n) Then
Have7 = False
If isTetraprime(n+1*signo) Then
If isTetraprime(n+2*signo) Then
count += 1
If f = 5 Then
Print Using "#######"; n;
If count Mod 10 = 0 Then Print
End If
If Have7 Then count7 += 1
If m <> 0 Then
Gap = n - m
If Gap <= GapMin Then GapMin = Gap
If Gap > GapMax Then GapMax = Gap
GapSum += Gap
End If
m = n
End If
End If
n += 1
End If
Next n
Print Using !"\nFound ##,### primes under ##,###,### whose preceding neighboring pair are tetraprimes"; count; TenPower
Print Using "of which #,### have a neighboring pair, one of whose factors is 7."; count7
Print Using !"\nMinimum gap between & primes : ##,###"; count; GapMin
Print Using "Average gap between & primes : ##,###"; count; (GapSum / (count-1))
Print Using "Maximum gap between & primes : ##,###"; count; GapMax
signo = signo * -1
Next g
TenPower *= 10
Next f
Sleep
- Output:
8647 15107 20407 20771 21491 23003 23531 24767 24971 27967 29147 33287 34847 36779 42187 42407 42667 43331 43991 46807 46867 51431 52691 52747 53891 54167 58567 63247 63367 69379 71711 73607 73867 74167 76507 76631 76847 80447 83591 84247 86243 87187 87803 89387 93887 97547 97847 98347 99431 Found 49 primes under 100,000 whose preceding neighboring pair are tetraprimes of which 31 have a neighboring pair, one of whose factors is 7. Minimum gap between 49 primes : 56 Average gap between 49 primes : 1,891 Maximum gap between 49 primes : 6,460 8293 16553 17389 18289 22153 26893 29209 33409 35509 36293 39233 39829 40493 41809 45589 48109 58393 59629 59753 59981 60493 60913 64013 64921 65713 66169 69221 71329 74093 75577 75853 77689 77933 79393 79609 82913 84533 85853 87589 87701 88681 91153 93889 96017 97381 98453 Found 46 primes under 100,000 whose preceding neighboring pair are tetraprimes of which 36 have a neighboring pair, one of whose factors is 7. Minimum gap between 46 primes : 112 Average gap between 46 primes : 2,004 Maximum gap between 46 primes : 10,284 Found 885 primes under 1,000,000 whose preceding neighboring pair are tetraprimes of which 503 have a neighboring pair, one of whose factors is 7. Minimum gap between 885 primes : 4 Average gap between 885 primes : 1,119 Maximum gap between 885 primes : 7,712 Found 866 primes under 1,000,000 whose preceding neighboring pair are tetraprimes of which 492 have a neighboring pair, one of whose factors is 7. Minimum gap between 866 primes : 4 Average gap between 866 primes : 1,146 Maximum gap between 866 primes : 10,284 Found 10,815 primes under 10,000,000 whose preceding neighboring pair are tetraprimes of which 5,176 have a neighboring pair, one of whose factors is 7. Minimum gap between 10815 primes : 4 Average gap between 10815 primes : 924 Maximum gap between 10815 primes : 9,352 Found 10,551 primes under 10,000,000 whose preceding neighboring pair are tetraprimes of which 5,069 have a neighboring pair, one of whose factors is 7. Minimum gap between 10551 primes : 4 Average gap between 10551 primes : 947 Maximum gap between 10551 primes : 10,284
Go
package main
import (
"fmt"
"rcu"
"sort"
)
func hasDups(pf []int) bool {
le := len(pf)
if le == 1 {
return false
}
for i := 1; i < le; i++ {
if pf[i] == pf[i-1] {
return true
}
}
return false
}
func contains(pf []int, value int) bool {
for i := 0; i < len(pf); i++ {
if pf[i] == value {
return true
}
}
return false
}
// Note that 'gaps' will only contain even numbers here.
func median(gaps []int) int {
le := len(gaps)
m := le / 2
if le&1 == 1 {
return gaps[m]
}
return (gaps[m] + gaps[m-1]) / 2
}
func main() {
const LIMIT = int(1e7)
primes := rcu.Primes(LIMIT)
highest5 := primes[sort.SearchInts(primes, int(1e5))-1]
highest6 := primes[sort.SearchInts(primes, int(1e6))-1]
highest7 := primes[len(primes)-1]
var tetras1, tetras2 []int
sevens1, sevens2 := 0, 0
j := 100_000
for _, p := range primes {
pf1 := rcu.PrimeFactors(p - 2)
cond1 := len(pf1) == 4 && !hasDups(pf1)
pf2 := rcu.PrimeFactors(p - 1)
cond2 := len(pf2) == 4 && !hasDups(pf2)
pf3 := rcu.PrimeFactors(p + 1)
cond3 := len(pf3) == 4 && !hasDups(pf3)
pf4 := rcu.PrimeFactors(p + 2)
cond4 := len(pf4) == 4 && !hasDups(pf4)
if cond1 && cond2 {
tetras1 = append(tetras1, p)
if contains(pf1, 7) || contains(pf2, 7) {
sevens1++
}
}
if cond3 && cond4 {
tetras2 = append(tetras2, p)
if contains(pf3, 7) || contains(pf4, 7) {
sevens2++
}
}
if p == highest5 || p == highest6 || p == highest7 {
for i := 0; i < 2; i++ {
tetras := tetras1
if i == 1 {
tetras = tetras2
}
sevens := sevens1
if i == 1 {
sevens = sevens2
}
c := len(tetras)
t := "preceding"
if i == 1 {
t = "following"
}
fmt.Printf("Found %s primes under %s whose %s neighboring pair are tetraprimes", rcu.Commatize(c), rcu.Commatize(j), t)
if p == highest5 {
fmt.Printf(":\n")
for k := 0; k < c; k++ {
fmt.Printf("%5d ", tetras[k])
if (k+1)%10 == 0 {
fmt.Println()
}
}
fmt.Println()
}
fmt.Println()
fmt.Printf("of which %s have a neighboring pair one of whose factors is 7.\n\n", rcu.Commatize(sevens))
gaps := make([]int, c-1)
for k := 0; k < c-1; k++ {
gaps[k] = tetras[k+1] - tetras[k]
}
sort.Ints(gaps)
mins := rcu.Commatize(gaps[0])
maxs := rcu.Commatize(gaps[c-2])
meds := rcu.Commatize(median(gaps))
cs := rcu.Commatize(c)
fmt.Printf("Minimum gap between those %s primes : %s\n", cs, mins)
fmt.Printf("Median gap between those %s primes : %s\n", cs, meds)
fmt.Printf("Maximum gap between those %s primes : %s\n", cs, maxs)
fmt.Println()
}
j *= 10
}
}
}
- Output:
Identical to Wren example.
Nim
To improve performance, we used int32 instead of int which are 64 bits long on 64 bits platforms. We also avoided to search all the factors by stopping if the number of factors is greater than four or if the same factor occurs more than one time.
import std/[algorithm, bitops, math, strformat, strutils, sugar]
### Sieve of Erathostenes.
type Sieve = object
data: seq[byte]
func `[]`(sieve: Sieve; idx: Positive): bool =
## Return value of element at index "idx".
let idx = idx shr 1
let iByte = idx shr 3
let iBit = idx and 7
result = sieve.data[iByte].testBit(iBit)
func `[]=`(sieve: var Sieve; idx: Positive; val: bool) =
## Set value of element at index "idx".
let idx = idx shr 1
let iByte = idx shr 3
let iBit = idx and 7
if val: sieve.data[iByte].setBit(iBit)
else: sieve.data[iByte].clearBit(iBit)
func newSieve(lim: Positive): Sieve =
## Create a sieve with given maximal index.
result.data = newSeq[byte]((lim + 16) shr 4)
func initPrimes(lim: int32): seq[int32] =
## Initialize the list of primes from 3 to "lim".
var composite = newSieve(lim)
composite[1] = true
for n in countup(3, sqrt(lim.toFloat).int, 2):
if not composite[n]:
for k in countup(n * n, lim, 2 * n):
composite[k] = true
for n in countup(3i32, lim, 2):
if not composite[n]:
result.add n
### Task functions.
func isTetraPrime(n: int32): bool =
## Return true if "n" is a tetraprime.
var n = n
if n < 2: return
const Inc = [4, 2, 4, 2, 4, 6, 2, 6] # Wheel.
var count = 0
if (n and 1) == 0:
inc count
n = n shr 1
if (n and 1) == 0: return
if n mod 3 == 0:
inc count
n = n div 3
if n mod 3 == 0: return
if n mod 5 == 0:
inc count
n = n div 5
if n mod 5 == 0: return
var k = 7i32
var i = 0
while k * k <= n:
if n mod k == 0:
inc count
n = n div k
if count > 4 or n mod k == 0: return
inc k, Inc[i]
i = (i + 1) and 7
if n > 1: inc count
result = count == 4
func median(a: openArray[int32]): int32 =
## Return the median value of "a".
let m = a.len div 2
result = if (a.len and 1) == 0: (a[m] + a[m-1]) div 2 else: a[m]
type Position {.pure.} = enum Preceding = "preceding", Following = "following"
proc printResult(list: seq[int32]; count: int; lim: int; pos: Position; display: bool) =
## Print the result for the given list and the given count.
let c = if display: ':' else: '.'
let lim = insertSep($lim)
echo &"Found {list.len} primes under {lim} whose {pos} neighboring pair are tetraprimes{c}"
if display:
for i, p in list:
stdout.write &"{p:5}"
stdout.write if i mod 10 == 9 or i == list.high: '\n' else: ' '
echo()
echo &" Of which {count} have a neighboring pair one of whose factors is 7.\n"
var gaps = collect(for i in 1..list.high: list[i] - list[i - 1])
gaps.sort()
echo &" Minimum gap between those {list.len} primes: {gaps[0]}"
echo &" Median gap between those {list.len} primes: {gaps.median}"
echo &" Maximum gap between those {list.len} primes: {gaps[^1]}"
echo()
const Steps = [int32 100_000, 1_000_000, 10_000_000]
var list1: seq[int32] # Prime whose preceding neighboring pair are tetraprimes.
var list2: seq[int32] # Prime whose following neighboring pair are tetraprimes.
var count1 = 0 # Number of primes from "list1" with one value of the pairs multiple of 7.
var count2 = 0 # Number of primes from "list2" with one value of the pairs multiple of 7.
let primes = initPrimes(Steps[^1])
var limit = Steps[0]
var iLimit = 0
var display = true # True to display the primes.
var last = primes[^1]
for p in primes:
if p >= limit or p == last:
printResult(list1, count1, limit, Preceding, display)
printResult(list2, count2, limit, Following, display)
if iLimit == Steps.high: break
inc iLimit
limit = Steps[iLimit]
display = false # Don't display next primes.
if isTetraPrime(p - 2) and isTetraPrime(p - 1):
list1.add p
if (p - 2) mod 7 in [0, 6]:
inc count1
if isTetraPrime(p + 1) and isTetraPrime(p + 2):
list2.add p
if (p + 1) mod 7 in [0, 6]:
inc count2
- Output:
Found 49 primes under 100_000 whose preceding neighboring pair are tetraprimes: 8647 15107 20407 20771 21491 23003 23531 24767 24971 27967 29147 33287 34847 36779 42187 42407 42667 43331 43991 46807 46867 51431 52691 52747 53891 54167 58567 63247 63367 69379 71711 73607 73867 74167 76507 76631 76847 80447 83591 84247 86243 87187 87803 89387 93887 97547 97847 98347 99431 Of which 31 have a neighboring pair one of whose factors is 7. Minimum gap between those 49 primes: 56 Median gap between those 49 primes: 1208 Maximum gap between those 49 primes: 6460 Found 46 primes under 100_000 whose following neighboring pair are tetraprimes: 8293 16553 17389 18289 22153 26893 29209 33409 35509 36293 39233 39829 40493 41809 45589 48109 58393 59629 59753 59981 60493 60913 64013 64921 65713 66169 69221 71329 74093 75577 75853 77689 77933 79393 79609 82913 84533 85853 87589 87701 88681 91153 93889 96017 97381 98453 Of which 36 have a neighboring pair one of whose factors is 7. Minimum gap between those 46 primes: 112 Median gap between those 46 primes: 1460 Maximum gap between those 46 primes: 10284 Found 885 primes under 1_000_000 whose preceding neighboring pair are tetraprimes. Of which 503 have a neighboring pair one of whose factors is 7. Minimum gap between those 885 primes: 4 Median gap between those 885 primes: 756 Maximum gap between those 885 primes: 7712 Found 866 primes under 1_000_000 whose following neighboring pair are tetraprimes. Of which 492 have a neighboring pair one of whose factors is 7. Minimum gap between those 866 primes: 4 Median gap between those 866 primes: 832 Maximum gap between those 866 primes: 10284 Found 10815 primes under 10_000_000 whose preceding neighboring pair are tetraprimes. Of which 5176 have a neighboring pair one of whose factors is 7. Minimum gap between those 10815 primes: 4 Median gap between those 10815 primes: 648 Maximum gap between those 10815 primes: 9352 Found 10551 primes under 10_000_000 whose following neighboring pair are tetraprimes. Of which 5069 have a neighboring pair one of whose factors is 7. Minimum gap between those 10551 primes: 4 Median gap between those 10551 primes: 660 Maximum gap between those 10551 primes: 10284
J
For this task we could use a couple tools -- one to enumerate primes less than some limit, and one to determine if a number is a tetraprime:
primeslt=: i.&.(p:inv)
tetrap=: 0:`(4=#@~.)@.(4=#)@q: ::0:"0
Thus:
NB. (1) primes less than 1e5 preceeded by two tetraprimes
{{y#~*/tetrap 1 2-~/y}} primeslt 1e5
8647 15107 20407 20771 21491 23003 23531 24767 24971 27967 29147 33287 34847 36779 42187 42407 42667 43331 43991 46807 46867 51431 52691 52747 53891 54167 58567 63247 63367 69379 71711 73607 73867 74167 76507 76631 76847 80447 83591 84247 86243 87187 87803...
NB. (2) primes less than 1e5 followed by two tetraprimes
{{y#~*/tetrap 1 2+/y}} primeslt 1e5
8293 16553 17389 18289 22153 26893 29209 33409 35509 36293 39233 39829 40493 41809 45589 48109 58393 59629 59753 59981 60493 60913 64013 64921 65713 66169 69221 71329 74093 75577 75853 77689 77933 79393 79609 82913 84533 85853 87589 87701 88681 91153 93889...
NB. (3a) how many primes from (1) have 7 in a factor of a number in the preceeding pair?
+/0+./ .=7|1 2-~/{{y#~*/tetrap 1 2-~/y}} primeslt 1e5
31
NB. (3b) how many primes from (2) have 7 in a factor of a number in the following pair?
+/0+./ .=7|1 2+/{{y#~*/tetrap 1 2+/y}} primeslt 1e5
36
NB. (4a) minimum, maximum gap between primes in (1)
(<./,>./)2 -~/\{{y#~*/tetrap 1 2-~/y}} primeslt 1e5
56 6460
NB. (4b) minimum, maximum gap between primes in (2)
(<./,>./)2 -~/\{{y#~*/tetrap 1 2+/y}} primeslt 1e5
112 10284
NB. number of type (1) primes but for primes less than 1e6
#{{y#~*/tetrap 1 2-~/y}} primeslt 1e6
885
NB. number of type (2) primes but for primes less than 1e6
#{{y#~*/tetrap 1 2+/y}} primeslt 1e5
46
NB. count of type (3a) for primes less than 1e6
+/0+./ .=7|1 2-~/{{y#~*/tetrap 1 2-~/y}} primeslt 1e6
503
NB. count of type (3b) for primes less than 1e6
+/0+./ .=7|1 2+/{{y#~*/tetrap 1 2+/y}} primeslt 1e6
492
NB. gaps of type (4a) for primes less than 1e6
(<./,>./)2 -~/\{{y#~*/tetrap 1 2-~/y}} primeslt 1e6
4 7712
NB. gaps of type (4b) for primes less than 1e6
(<./,>./)2 -~/\{{y#~*/tetrap 1 2+/y}} primeslt 1e6
4 10284
Julia
Yet another "output an OEIS sequence as produced by a function which takes the prime number sequence as its input" task.
""" rosettacode.org/wiki/Prime_numbers_whose_neighboring_pairs_are_tetraprimes """
using Statistics
using Primes
istetraprime(n) = (a = map(last, factor(n).pe); length(a) == 4 && all(==(1), a))
are_following_tetraprimes(n, cnt = 2) = all(istetraprime, n+1:n+cnt)
are_preceding_tetraprimes(n, cnt = 2) = all(istetraprime, n-cnt:n-1)
let
primes1M = primes(10^7)
pre1M = filter(are_preceding_tetraprimes, primes1M)
fol1M = filter(are_following_tetraprimes, primes1M)
pre100k = filter(<(100_000), pre1M)
fol100k = filter(<(100_000), fol1M)
pre1M_with7 = filter(i -> any(k -> (i - k) % 7 == 0, 1:2), pre1M)
fol1M_with7 = filter(i -> any(k -> (i + k) % 7 == 0, 1:2), fol1M)
pre100k_with7 = filter(<(100_000), pre1M_with7)
fol100k_with7 = filter(<(100_000), fol1M_with7)
p_gaps1M = [pre1M[i] - pre1M[i - 1] for i in 2:lastindex(pre1M)]
f_gaps1M = [fol1M[i] - fol1M[i - 1] for i in 2:lastindex(fol1M)]
p_gaps100k = [pre1M[i] - pre1M[i - 1] for i in 2:lastindex(pre1M) if pre1M[i] < 100_000]
f_gaps100k = [fol1M[i] - fol1M[i - 1] for i in 2:lastindex(fol1M) if fol1M[i] < 100_000]
pmin1M, pmedian1M, pmax1M = minimum(p_gaps1M), median(p_gaps1M), maximum(p_gaps1M)
fmin1M, fmedian1M, fmax1M = minimum(f_gaps1M), median(f_gaps1M), maximum(f_gaps1M)
pmin100k, pmedian100k, pmax100k = minimum(p_gaps100k), median(p_gaps100k), maximum(p_gaps100k)
fmin100k, fmedian100k, fmax100k = minimum(f_gaps100k), median(f_gaps100k), maximum(f_gaps100k)
for (tet, s, s2, tmin, tmed, tmax, t7) in [
(pre100k, "100,000", "preceding", pmin100k, pmedian100k, pmax100k, pre100k_with7),
(fol100k, "100,000", "following", fmin100k, fmedian100k, fmax100k, fol100k_with7),
(pre1M, "1,000,000", "preceding", pmin1M, pmedian1M, pmax1M, pre1M_with7),
(fol1M, "1,000,000", "following", fmin1M, fmedian1M, fmax1M, fol1M_with7),
]
print("Found $(length(tet)) primes under $s whose $s2 neighboring pair are tetraprimes")
if s == "100,000"
println(":")
foreach(p -> print(rpad(p[2], 6), p[1] % 10 == 0 ? "\n" : ""), enumerate(tet))
println()
else
println(".")
end
println("Minimum, median, and maximum gaps between those primes: $tmin $tmed $tmax")
println("Of those primes, $(length(t7)) have a neighboring pair one of whose factors is 7.\n")
end
end- Output:
Found 49 primes under 100,000 whose preceding neighboring pair are tetraprimes: 8647 15107 20407 20771 21491 23003 23531 24767 24971 27967 29147 33287 34847 36779 42187 42407 42667 43331 43991 46807 46867 51431 52691 52747 53891 54167 58567 63247 63367 69379 71711 73607 73867 74167 76507 76631 76847 80447 83591 84247 86243 87187 87803 89387 93887 97547 97847 98347 99431 Minimum, median, and maximum gaps between those primes: 56 1208.0 6460 Of those primes, 31 have a neighboring pair one of whose factors is 7. Found 46 primes under 100,000 whose following neighboring pair are tetraprimes: 8293 16553 17389 18289 22153 26893 29209 33409 35509 36293 39233 39829 40493 41809 45589 48109 58393 59629 59753 59981 60493 60913 64013 64921 65713 66169 69221 71329 74093 75577 75853 77689 77933 79393 79609 82913 84533 85853 87589 87701 88681 91153 93889 96017 97381 98453 Minimum, median, and maximum gaps between those primes: 112 1460.0 10284 Of those primes, 36 have a neighboring pair one of whose factors is 7. Found 10815 primes under 1,000,000 whose preceding neighboring pair are tetraprimes. Minimum, median, and maximum gaps between those primes: 4 648.0 9352 Of those primes, 5176 have a neighboring pair one of whose factors is 7. Found 10551 primes under 1,000,000 whose following neighboring pair are tetraprimes. Minimum, median, and maximum gaps between those primes: 4 660.0 10284 Of those primes, 5069 have a neighboring pair one of whose factors is 7.
Phix
constant primes = get_primes_le(1e7) sequence tetras = {{},{}}, sevens = {0,0}, highs = {1e5,1e6,1e7}, highdx = apply(true,binary_search,{highs,{primes}}), highest = extract(primes,sq_sub(sq_abs(highdx),1)) integer hdx = 1 for p in primes from 2 do -- for all odd primes, both p-1 and p+1 are divisible by 2. -- one of them will be divisible by 4 and hence not a tetraprime. integer d = odd((p-1)/2), dx = iff(d?-1:+1) sequence f3 = prime_powers((p+dx)/2) if length(f3)=3 and vslice(f3,2)={1,1,1} then sequence f4 = prime_powers(p+2*dx) if length(f4)=4 and vslice(f4,2)={1,1,1,1} then tetras[2-d] &= p if find(7,vslice(f3,1)) or find(7,vslice(f4,1)) then sevens[2-d] += 1 end if end if end if if p=highest[hdx] then for t,ti in tetras do integer c = length(ti) printf(1,"Found %,d primes under %,d whose %sing neighboring pair are tetraprimes%s\n", {c, highs[hdx], {"preced","follow"}[t],iff(hdx=1?":":"")}) if hdx=1 then printf(1,"%s\n",{join_by(ti,1,10,fmt:="%5d")}) end if printf(1,"of which %,d have a neighboring pair one of whose factors is 7.\n\n",sevens[t]) sequence gaps = sort(sq_sub(ti[2..-1],ti[1..-2])) printf(1,"Minimum gap between those %,d primes : %,d\n",{c,gaps[1]}) -- printf(1,"Average gap between those %,d primes : %,d\n",{c,average(gaps)}) printf(1,"Median gap between those %,d primes : %,d\n",{c,median(gaps)}) printf(1,"Maximum gap between those %,d primes : %,d\n\n",{c,gaps[$]}) end for hdx += 1 end if end for
- Output:
Same as Wren
Wren
import "./math" for Int, Nums
import "./sort" for Find
import "./seq" for Seq
import "./fmt" for Fmt
var primes = Int.primeSieve(1e7)
var highest5 = primes[Find.nearest(primes, 1e5) - 1]
var highest6 = primes[Find.nearest(primes, 1e6) - 1]
var highest7 = primes[-1]
var tetras1 = []
var tetras2 = []
var sevens1 = 0
var sevens2 = 0
var j = 1e5
for (p in primes) {
var pf1 = Int.primeFactors(p-2)
var cond1 = pf1.count == 4 && !Seq.hasAdjDup(pf1)
var pf2 = Int.primeFactors(p-1)
var cond2 = pf2.count == 4 && !Seq.hasAdjDup(pf2)
var pf3 = Int.primeFactors(p+1)
var cond3 = pf3.count == 4 && !Seq.hasAdjDup(pf3)
var pf4 = Int.primeFactors(p+2)
var cond4 = pf4.count == 4 && !Seq.hasAdjDup(pf4)
if (cond1 && cond2) {
tetras1.add(p)
if (pf1.contains(7) || pf2.contains(7)) sevens1 = sevens1 + 1
}
if (cond3 && cond4) {
tetras2.add(p)
if (pf3.contains(7) || pf4.contains(7)) sevens2 = sevens2 + 1
}
if (p == highest5 || p == highest6 || p == highest7) {
for (i in 0..1) {
var tetras = (i == 0) ? tetras1 : tetras2
var sevens = (i == 0) ? sevens1 : sevens2
var c = tetras.count
var t = (i == 0) ? "preceding" : "following"
Fmt.write("Found $,d primes under $,d whose $s neighboring pair are tetraprimes", c, j, t)
if (p == highest5) {
Fmt.print(":")
Fmt.tprint("$5d ", tetras, 10)
}
Fmt.print("\nof which $,d have a neighboring pair one of whose factors is 7.\n", sevens)
var gaps = List.filled(c-1, 0)
for (k in 0...c-1) gaps[k] = tetras[k+1] - tetras[k]
gaps.sort()
var min = gaps[0]
var max = gaps[-1]
var med = Nums.median(gaps)
Fmt.print("Minimum gap between those $,d primes : $,d", c, min)
Fmt.print("Median gap between those $,d primes : $,d", c, med)
Fmt.print("Maximum gap between those $,d primes : $,d", c, max)
Fmt.print()
}
j = j * 10
}
}
- Output:
Found 49 primes under 100,000 whose preceding neighboring pair are tetraprimes: 8647 15107 20407 20771 21491 23003 23531 24767 24971 27967 29147 33287 34847 36779 42187 42407 42667 43331 43991 46807 46867 51431 52691 52747 53891 54167 58567 63247 63367 69379 71711 73607 73867 74167 76507 76631 76847 80447 83591 84247 86243 87187 87803 89387 93887 97547 97847 98347 99431 of which 31 have a neighboring pair one of whose factors is 7. Minimum gap between those 49 primes : 56 Median gap between those 49 primes : 1,208 Maximum gap between those 49 primes : 6,460 Found 46 primes under 100,000 whose following neighboring pair are tetraprimes: 8293 16553 17389 18289 22153 26893 29209 33409 35509 36293 39233 39829 40493 41809 45589 48109 58393 59629 59753 59981 60493 60913 64013 64921 65713 66169 69221 71329 74093 75577 75853 77689 77933 79393 79609 82913 84533 85853 87589 87701 88681 91153 93889 96017 97381 98453 of which 36 have a neighboring pair one of whose factors is 7. Minimum gap between those 46 primes : 112 Median gap between those 46 primes : 1,460 Maximum gap between those 46 primes : 10,284 Found 885 primes under 1,000,000 whose preceding neighboring pair are tetraprimes of which 503 have a neighboring pair one of whose factors is 7. Minimum gap between those 885 primes : 4 Median gap between those 885 primes : 756 Maximum gap between those 885 primes : 7,712 Found 866 primes under 1,000,000 whose following neighboring pair are tetraprimes of which 492 have a neighboring pair one of whose factors is 7. Minimum gap between those 866 primes : 4 Median gap between those 866 primes : 832 Maximum gap between those 866 primes : 10,284 Found 10,815 primes under 10,000,000 whose preceding neighboring pair are tetraprimes of which 5,176 have a neighboring pair one of whose factors is 7. Minimum gap between those 10,815 primes : 4 Median gap between those 10,815 primes : 648 Maximum gap between those 10,815 primes : 9,352 Found 10,551 primes under 10,000,000 whose following neighboring pair are tetraprimes of which 5,069 have a neighboring pair one of whose factors is 7. Minimum gap between those 10,551 primes : 4 Median gap between those 10,551 primes : 660 Maximum gap between those 10,551 primes : 10,284
XPL0
include xpllib; \for Print
int Have7; \A tetraprime factor is 7
proc IsTetraprime(N); \Return 'true' if N is a tetraprime
int N;
int Div, Count, Distinct;
[Div:= 2; Count:= 0;
while N >= Div*Div do
[Distinct:= true;
while rem(N/Div) = 0 do
[if not Distinct then return false;
Distinct:= false;
Count:= Count+1;
if Div = 7 then Have7:= true;
N:= N/Div;
];
Div:= Div+1;
];
if N > 1 then Count:= Count+1;
return Count = 4;
];
int Sign, TenPower, TP, Case, N, N0, Count, Count7, Gap, GapMin, GapMax, GapSum;
[Sign:= -1; TenPower:= 100_000;
for TP:= 5 to 7 do
[for Case:= 1 to 2 do \preceding or following neighboring pairs
[Count:= 0; Count7:= 0; N0:= 0; GapMin:= -1>>1; GapMax:= 0; GapSum:= 0;
if TP = 5 then CrLf(0); \100_000
for N:= 3 to TenPower-1 do
[if IsPrime(N) then
[Have7:= false;
if IsTetraprime(N+1*Sign) then
if IsTetraprime(N+2*Sign) then
[Count:= Count+1;
if TP = 5 then
[Print("%7d", N);
if rem(Count/10) = 0 then CrLf(0);
];
if Have7 then Count7:= Count7+1;
if N0 # 0 then
[Gap:= N - N0;
if Gap < GapMin then GapMin:= Gap;
if Gap > GapMax then GapMax:= Gap;
GapSum:= GapSum + Gap;
];
N0:= N;
];
];
N:= N+1;
];
Print("\nFound %,d primes under %,d whose neighboring pair are tetraprimes\n",
Count, TenPower);
Print("of which %,d have a neighboring pair, one of whose factors is 7.\n\n",
Count7);
Print("Minimum gap between %d primes : %,d\n", Count, GapMin);
Print("Average gap between %d primes : %,d\n", Count,
fix(float(GapSum)/float(Count-1)));
Print("Maximum gap between %d primes : %,d\n", Count, GapMax);
Sign:= Sign * -1;
];
TenPower:= TenPower * 10;
];
]- Output:
8647 15107 20407 20771 21491 23003 23531 24767 24971 27967 29147 33287 34847 36779 42187 42407 42667 43331 43991 46807 46867 51431 52691 52747 53891 54167 58567 63247 63367 69379 71711 73607 73867 74167 76507 76631 76847 80447 83591 84247 86243 87187 87803 89387 93887 97547 97847 98347 99431 Found 49 primes under 100,000 whose neighboring pair are tetraprimes of which 31 have a neighboring pair, one of whose factors is 7. Minimum gap between 49 primes : 56 Average gap between 49 primes : 1,891 Maximum gap between 49 primes : 6,460 8293 16553 17389 18289 22153 26893 29209 33409 35509 36293 39233 39829 40493 41809 45589 48109 58393 59629 59753 59981 60493 60913 64013 64921 65713 66169 69221 71329 74093 75577 75853 77689 77933 79393 79609 82913 84533 85853 87589 87701 88681 91153 93889 96017 97381 98453 Found 46 primes under 100,000 whose neighboring pair are tetraprimes of which 36 have a neighboring pair, one of whose factors is 7. Minimum gap between 46 primes : 112 Average gap between 46 primes : 2,004 Maximum gap between 46 primes : 10,284 Found 885 primes under 1,000,000 whose neighboring pair are tetraprimes of which 503 have a neighboring pair, one of whose factors is 7. Minimum gap between 885 primes : 4 Average gap between 885 primes : 1,119 Maximum gap between 885 primes : 7,712 Found 866 primes under 1,000,000 whose neighboring pair are tetraprimes of which 492 have a neighboring pair, one of whose factors is 7. Minimum gap between 866 primes : 4 Average gap between 866 primes : 1,146 Maximum gap between 866 primes : 10,284 Found 10,815 primes under 10,000,000 whose neighboring pair are tetraprimes of which 5,176 have a neighboring pair, one of whose factors is 7. Minimum gap between 10815 primes : 4 Average gap between 10815 primes : 924 Maximum gap between 10815 primes : 9,352 Found 10,551 primes under 10,000,000 whose neighboring pair are tetraprimes of which 5,069 have a neighboring pair, one of whose factors is 7. Minimum gap between 10551 primes : 4 Average gap between 10551 primes : 947 Maximum gap between 10551 primes : 10,284