Prime numbers whose neighboring pairs are tetraprimes: Difference between revisions
Prime numbers whose neighboring pairs are tetraprimes (view source)
Revision as of 18:42, 25 June 2023
, 11 months agoCreated Nim solution.
m (→{{header|J}}) |
(Created Nim solution.) |
||
Line 584:
</pre>
=={{header|Nim}}==
To improve performance, we used <code>int32</code> instead of <code>int</code> 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.
<syntaxhighlight lang="Nim">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
</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|J}}==
| |||