Merseene Primes (Mp) are primes of form: Mp = 2^p - 1, for p prime.
The newest one was found on October 12, 2024, and announced on October 21, 2024 (also largest known prime), for p = 136,279,841. This is an integer of 136,279,841 consecutive binary ‘1’ bits, which is over 41M decimal digits long. The previous Mp was found December 7, 2018 and announced December 21, 2018, almost a full 6 years between new primes. It the longest computer age dry spell.
Some articles:
Videos:
Here is the current list of all 52 Mp primes.
2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457,32582657, 37156667, 42643801, 43112609, 57885161, 74207281, 77232917, 82589933, 136279841
Its finder, Lucas Durant, was formerly employed by Nvidia. He strung together a bunch of cloud servers to do his computing, and said he spent around $2M in total over two years to do it.
Well I ain’t got $2M, but I do have a better algorithm for finding them.
Below is Crystal code to generate all the odd prime Mp (code to perform prime? not shone). It’s based on math I’ve developed I call Prime Generator Theory (PGT).
PGT is based on the use of modular groups to find and characterize everything you want to know about primes, their gaps, and distribution. All the (odd) primes exist as the congruent residue values of modular groups. The Mp are congruent residue values for just one residue value for optimally crafted modular group sizes.
Read this paper for the basics of PGT’s mathematical foundation. It’s very simple, and requires only basic arithmetic and logic (no higher order math needed).
This paper (pgs 7-8) provides the math structure for an optimed Mp search.
From PGT, Mp values have the form:
Mp = 2^p – 1 = (2^n · 3)·k + (2^n – 1), n odd (1, 3, 5, 7…)
However to find the Mp, k has this special optimum form:
k0 = 0, ki+1 = 4·ki + 1 = (ki << 2) + 1
1, 5, 21, 85, 341, 1365, 5461, 21845, 87381, 349525, 1398101, 5592405…
The code for mpgen uses a known Mp p value to generate the next Mp p value.
This is the single thread version.
def mpgen(p)
puts "Starting Mp prime = #{p}"
k, steps = 1.to_big_i, 1u64
r = (1.to_big_i << p) - 1
modpn = 3.to_big_i << p
loop do
mp = modpn*k + r
(p = mp.bit_length; break) if mp.prime?
k = (k << 2) + 1
steps += 1
print "\rsteps = #{steps}" if steps.divisible_by? 10
end
print "\rsteps = #{steps}\n"
puts "Next Mp prime = #{p}"
p
end
def tm; t = Time.monotonic; yield; Time.monotonic - t end
def mpgens (p)
p = p.to_big_i
loop { puts tm {p = mpgen(p)}; puts }
end
mpgens 3
Here is output for generating the first few Mp primes.
The number of steps and times get larger as the primes increase.
➜ crystal-projects ./MPgenerate
Starting Mp prime = 3
steps = 1
Next Mp prime = 5
00:00:00.000053029
Starting Mp prime = 5
steps = 1
Next Mp prime = 7
00:00:00.000008866
Starting Mp prime = 7
steps = 3
Next Mp prime = 13
00:00:00.000016440
Starting Mp prime = 13
steps = 2
Next Mp prime = 17
00:00:00.000020148
Starting Mp prime = 17
steps = 1
Next Mp prime = 19
00:00:00.000011262
Starting Mp prime = 19
steps = 6
Next Mp prime = 31
00:00:00.000027081
Starting Mp prime = 31
steps = 15
Next Mp prime = 61
00:00:00.000056636
Starting Mp prime = 61
steps = 14
Next Mp prime = 89
00:00:00.000098844
So here’s the mission for those interested.
Using this optimized algorithm we can find the next Mp (and others after it).
My current laptop is:
Linux, Lenovo Legion 5, AMD Ryzen 7 8845HS, 3.8-5.1 GHz, 8C|16T. 16MB,
There are at least two things needed to do to make this practical.
-
Optimize the arithmetic computations.
Literally all the math is done withBigInts, so need to optimize the math done with them. -
Create an optimized parallel system.There’s two ways I see doing this.
a) Create optimized parallel code that can run locally on multi-core cpus.
b) Like GIMPS, create a distributed network that can compute values for each k step.The simple(st) way is to distribute the step(s) value(s) to parallel compute engines, who then numerate the k value progressions for its value, then use it to compute that mp value and check it, and send back its results.
It’s an extremely good project to advertise|market the power|benefits of Crystal!
I’ve almost done the paper to publish to explain all the math, the code, and results. I don’t want to release it until the next Mp is found, to prove that it works (and for PR!).
But I’ll provide the paper to anyone who’s a part of the project, to see all the math.
So that’s it.
I’d love to hear what the devs think, and anyone else with hardware|resources to apply to the project.
Jabari Zakiya
