Ciro Santilli Definition: "easy" number theory learnt in primary school, notably the operations of addition, subtraction, multiplication and division.
Can be calculated efficiently with the Extended Euclidean algorithm.
math.stackexchange.com/questions/2382011/computational-complexity-of-modular-exponentiation-from-rosens-discrete-mathem mentions:
can be calculated in:
Remember that and are the lengths in bits of and , so in terms of the length in bits and we'd get:
There are infinitely many prime k-tuples for every admissible tuple.
Generalization of the Twin prime conjecture.
As of 2023, there was no specific admissible tuple for which it had been proven that there infinite of, only bounds of type:
there are infinitely 2-tuple instances with at most a finite boundBut these do not specify which specific tuple, e.g. Yitang Zhang's theorem.
There are infinitely many primes with a neighbour 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:
or infinitely many:
or infinitely many:
or infinitely many:
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).
Let's show them how it's done with primes + awk. Edit. They have a
gives us the list of all twin primes up to 100:
Tested on Ubuntu 22.10.
-d option which also shows gaps!!! Too strong:
sudo apt install bsdgames
primes -d 1 100 | awk '/\(2\)/{print $1 - 2, $1 }'0 2
3 5
5 7
11 13
17 19
29 31
41 43
59 61
71 73Consider this is a study in failed computational number theory.
The 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:
Runs in 30 minutes tested on Ubuntu 22.10 and P51, producing:
sudo apt intsall bsdgames
cd prime-number-theorem
./main.py 100000000
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 it is still not super close. Inspecting the code there we see:
so OK, it is not something doable on a personal computer just like that.
(* 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}};They come up a lot in many contexts, e.g.:
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.
Two numbers such that the greatest common divisor is 1.