How to resolve the algorithm Earliest difference between prime gaps step by step in the Wren programming language

Published on 12 May 2024 09:40 PM
#Wren

How to resolve the algorithm Earliest difference between prime gaps step by step in the Wren programming language

Table of Contents

Problem Statement

When calculating prime numbers > 2, the difference between adjacent primes is always an even number. This difference, also referred to as the gap, varies in an random pattern; at least, no pattern has ever been discovered, and it is strongly conjectured that no pattern exists. However, it is also conjectured that between some two adjacent primes will be a gap corresponding to every positive even integer.

This task involves locating the minimal primes corresponding to those gaps. Though every gap value exists, they don't seem to come in any particular order. For example, this table shows the gaps and minimum starting value primes for 2 through 30:

For the purposes of this task, considering only primes greater than 2, consider prime gaps that differ by exactly two to be adjacent.

For each order of magnitude m from 10¹ through 10⁶:

For an m of 10¹; The start value of gap 2 is 3, the start value of gap 4 is 7, the difference is 7 - 3 or 4. 4 < 10¹ so keep going. The start value of gap 4 is 7, the start value of gap 6 is 23, the difference is 23 - 7, or 16. 16 > 10¹ so this the earliest adjacent gap difference > 10¹.

Note: the earliest value found for each order of magnitude may not be unique, in fact, is not unique; also, with the gaps in ascending order, the minimal starting values are not strictly ascending.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Earliest difference between prime gaps step by step in the Wren programming language

Source code in the wren programming language

import "./math" for Int
import "./fmt" for Fmt
 
var limit = 1e9
var gapStarts = {}
var primes = Int.segmentedSieve(limit * 5, 128 * 1024) // 128 KB cache
for (i in 1...primes.count) {
    var gap = primes[i] - primes[i-1]
    if (!gapStarts[gap]) gapStarts[gap] = primes[i-1]
}
var pm = 10
var gap1 = 2
while (true) {
    while (!gapStarts[gap1]) gap1 = gap1 + 2
    var start1 = gapStarts[gap1]
    var gap2 = gap1 + 2
    if (!gapStarts[gap2]) {
        gap1 = gap2 + 2
        continue
    }
    var start2 = gapStarts[gap2]
    var diff = (start2 - start1).abs
    if (diff > pm) {
        Fmt.print("Earliest difference > $,d between adjacent prime gap starting primes:", pm)
        Fmt.print("Gap $d starts at $,d, gap $d starts at $,d, difference is $,d.\n", gap1, start1, gap2, start2, diff)
        if (pm == limit) break
        pm = pm * 10
    } else {
        gap1 = gap2
    }
}


import "./psieve" for Primes
import "./math" for Int
import "./fmt" for Fmt

var limit = 1e10
var gapStarts = {}
var it = Primes.iter()
var pc = Primes.count(2, limit * 5)
var p1 = it.next
var p2 = it.next
for (i in 1...pc) {
    var gap = p2 - p1
    if (!gapStarts[gap]) gapStarts[gap] = p1
    p1 = p2
    p2 = it.next
}
var pm = 10
var gap1 = 2
while (true) {
    while (!gapStarts[gap1]) gap1 = gap1 + 2
    var start1 = gapStarts[gap1]
    var gap2 = gap1 + 2
    if (!gapStarts[gap2]) {
        gap1 = gap2 + 2
        continue
    }
    var start2 = gapStarts[gap2]
    var diff = (start2 - start1).abs
    if (diff > pm) {
        Fmt.print("Earliest difference > $,d between adjacent prime gap starting primes:", pm)
        Fmt.print("Gap $d starts at $,d, gap $d starts at $,d, difference is $,d.\n", gap1, start1, gap2, start2, diff)
        if (pm == limit) break
        pm = pm * 10
    } else {
        gap1 = gap2
    }
}

You may also check:How to resolve the algorithm Dijkstra's algorithm step by step in the Common Lisp programming language
You may also check:How to resolve the algorithm Loops/For step by step in the VBScript programming language
You may also check:How to resolve the algorithm Chinese remainder theorem step by step in the Maple programming language
You may also check:How to resolve the algorithm Classes step by step in the Logtalk programming language
You may also check:How to resolve the algorithm Sum digits of an integer step by step in the ML programming language