There are infinitely many primes with a neighbor not further apart than 70 million. This was the first such finite bound to be proven, and therefore a major breakthrough.

This implies that for at least one value (or more) below 70 million there are infinitely many repetitions, but we don't know which e.g. we could have infinitely many:

k, k + 2

(1)

or infinitely many:

k, k + 4

(2)

or infinitely many:

k, k + 6, 999, 999

(3)

or infinitely many:

k, k + 2 a n d k, k + 4

(4)

but we don't know which of those.

The Prime k-tuple conjecture conjectures that it is all of them.

Also, if 70 million could be reduced down to 2, we would have a proof of the Twin prime conjecture, but this method would only work for (k, k + 2).

Twin prime

 1  0 

Twin prime conjecture

 0  0 

Let's show them how it's done with primes + awk. Edit. They have a -d option which also shows gaps!!! Too strong:

sudo apt install bsdgames
primes -d 1 100 | awk '/\(2\)/{print $1 - 2, $1 }'

gives us the list of all twin primes up to 100:

Tested on Ubuntu 22.10.

The

n / l n (n)

approximation converges really slowly, and we can't easy go far enough to see that the ration converges to 1 with only awk and primes:

sudo apt intsall bsdgames
cd prime-number-theorem
./main.py 100000000

Runs in 30 minutes tested on Ubuntu 22.10 and P51, producing:

Figure 1.
Linear $π (n)$ vs $n / l n (n)$ approximation plot
. $f (n) = n$ and $f (n) = l o g (n)$ are added to give a better sense of scale. $l o g (n)$ is too close to 0 and not visible, and the approximation almost overlaps entirely with $p i$ .

Figure 2.
$π (n) - n / l n (n)$
. It is clear that the difference diverges, albeit very slowly.

Figure 3.
$π (n) / (n / l n (n))$
. We just don't have enough points to clearly see that it is converging to 1.0, the convergence truly is very slow. The logarithm integral approximation is much much better, but we can't calculate it in awk, sadface.

But looking at: en.wikipedia.org/wiki/File:Prime_number_theorem_ratio_convergence.svg we see that it takes way longer to get closer to 1, even at

1 0^{2} 4

it is still not super close. Inspecting the code there we see:

(* Supplement with larger known PrimePi values that are too large for \
Mathematica to compute *)
LargePiPrime = {{10^13, 346065536839}, {10^14, 3204941750802}, {10^15,
     29844570422669}, {10^16, 279238341033925}, {10^17,
    2623557157654233}, {10^18, 24739954287740860}, {10^19,
    234057667276344607}, {10^20, 2220819602560918840}, {10^21,
    21127269486018731928}, {10^22, 201467286689315906290}, {10^23,
    1925320391606803968923}, {10^24, 18435599767349200867866}};

so OK, it is not something doable on a personal computer just like that.

Prime power

 1  0 

They come up a lot in many contexts, e.g.:

classification of finite fields

Primality test

 0  0 

Elliptic curve primality

 0  0 

Polynomial time for most inputs, but not for some very rare ones. TODO can they be determined?

But it is better in practice than the AKS primality test, which is always polynomial time.

AKS primality test (2002, First polynomial time primality test discovered)

 0  0 

Greatest common divisor (GCD)

 0  0 

The "greatest common divisor" of two integers

x

and

y

, denoted

gdc (x, y)

is the largest natural number that divides both of the integers.

For example,

gdc (8, 12)

is 4, because:

4 divides both 8 and 12
and this is not the case for any number larger than 4. E.g.:
- 5 divides neither one
- 6 divides 12
- 7 divides neither
- 8 divides only 8
and so on.