Being physicist and unfortunately not so into math i watched this today (and the 20min more footage) about prime gaps and kinda liked it:
https://www.youtube.com/watch?v=vkMXdShDdtYSome questions:
Is there also world records for primes that have a gap of 2 ? Can gapcoin find them or because of sieves it may pass primes (I am not sure i understand how sieves work)?
I am kinda excited with primes lately. What should i read to understand how gapcoin finds gaps? Does it need really advanced mathematics?
The average length of a prime gap with the starting prime p, is log(p),
which means that the average prime gap size increases with lager primes.
Instead of the pure length, Gapcoin uses the merit of a prime gap,
which is the ratio of the gap's size to the average gap size.
Let p be the prime starting a prime gap, then m = gapsize/log(p) will be the merit of this prime gap.
Also a pseudo random number is calculated from p to provide finer difficulty adjustment.
Let rand(p) be a pseudo random function with 0 < rand(p) < 1
Then, for a prime gap starting at prime p with size s,
the difficulty will be s/log(p) + 2/log(p) ∗ rand(p),
where 2/log(p) is the average distance between a gap of size s and s + 2 (the next greater gap) in the proximity of p.
When it actually comes to mining, there are two additional fields added to the Blockheader, named “shift” and “adder”.
We will calculate the prime p as sha256(Blockheader) ∗ 2^shift + adder.
As an additional criterion the adder has to be smaller than 2^shift to avoid that the PoW could be reused.
Mining:For mining, PoWCore uses a basic prime sieve with some slightly improvements:
The sieving steps:Calculate the first n primes.
In the actual sieve we skip all even numbers,
because we want to only sieve the odd multiplies of each prime.
So, we create an additional set of primes and multiply each with two.
Make sure the start_index of the sieve is divisible by two.
Now calculate for each prime the first odd number in the sieve,
which is divisible by that prime (called pindex).
For each prime p: mark the pindex as composite,
add 2 ∗ p to pindex and mark it as composite,
redo till we reach the end of the sieve.
For each remaining prime candidate,
check primality with the Fermat-pseudo-prime-test as it is faster than the Miller-Rabin-test
(Fermat is not as accurate as the Miller-Rabin and maybe some valid sieve results will not be accepted, but this should be very rare)
Now scan the remaining (pseudo) primes for a big prime gap.
Additional notes:start–index can be hash ∗ 2^shift + [0, 2^shift)
max sieve size depends on start index, and is limited by (hash + 2^shift) - start_index.
shift can theoretically be in range [14, 2^16),
but nodes can choose to only accept shifts till a given amount (e.g. 512 for the main nodes)
dcct's improvementsWe do not check every remaining prime candidate with the fermat test.
Instead we look how large the gap has to be to fit the required difficulty (max_length).
Then we determine the first prime in the sieve (called pstart).
Now we scan the prime candidates in the range (pstart, pstart + max_length).
We start at the position (pstart + max_length) and scan every prime candidate in reverse order till we reach pstart.
If we find a prime within the range (pstart, pstart + max_length)
we can skip all other prime candidates within that range and set pstart to that prime.
We redo the above process till we reach the end of the sieve.
So, to sum it up:Gapcoin is researching into the opposite problem than the one of your video above,
but the max prime gap problem and the twin prime conjecture are closely related,
so, maybe Gapcoin's prime gaps could help somehow proving it.
Show Posts
, thanks to crz (donation address GdjcBC9vdDrx4bRZRzXaMdSMnuQrghPmC9)
