Skip to content

Latest commit

 

History

History
347 lines (312 loc) · 10.3 KB

README.md

File metadata and controls

347 lines (312 loc) · 10.3 KB
Raw

primesum

Build Status Github Releases

primesum is a command-line program that computes the sum of the primes below an integer x ≤ 1031 as quickly as possible using a modified version of the combinatorial prime counting function algorithm [1]. primesum has already been used to compute many new prime sum world records!

primesum is a modified version of the author's primecount program.

Binaries

Below are the latest precompiled binaries for Windows, Linux and macOS. These binaries are statically linked and require a CPU which supports the POPCNT instruction (2010 or later).

Build instructions

You need to have installed a C++ compiler, cmake and make. Ideally primesum should be compiled using a C++ compiler that supports both OpenMP and 128-bit integers (e.g. GCC, Clang, Intel C++ Compiler).

cmake .
make -j
sudo make install

Usage examples

Open a terminal and run primesum using e.g.:

# Sum the primes below 10^14
./primesum 1e14

# Print progress and status information during computation
./primesum 1e18 --status

# Use 4 threads
./primesum 1e14 --threads=4 --time

Command-line options

Usage: primesum x [OPTION]...
Sum the primes below x <= 10^31 using fast implementations of the
combinatorial prime summing function.

Options:

  -d,    --deleglise_rivat  Sum primes using Deleglise-Rivat algorithm
  -l,    --lmo              Sum primes using Lagarias-Miller-Odlyzko
  -s[N], --status[=N]       Show computation progress 1%, 2%, 3%, ...
                            [N] digits after decimal point e.g. N=1, 99.9%
         --test             Run various correctness tests and exit
         --time             Print the time elapsed in seconds
  -t<N>, --threads=<N>      Set the number of threads, 1 <= N <= CPU cores
  -v,    --version          Print version and license information
  -h,    --help             Print this help menu

Advanced Deleglise-Rivat options:

  -a<N>, --alpha=<N>        Tuning factor, 1 <= alpha <= x^(1/6)
         --P2               Only compute the 2nd partial sieve function
         --S1               Only compute the ordinary leaves
         --S2_trivial       Only compute the trivial special leaves
         --S2_easy          Only compute the easy special leaves
         --S2_hard          Only compute the hard special leaves

Performance tips

primesum scales nicely up until 10^23 on current CPUs. For larger values primesum's large memory usage causes many TLB (translation lookaside buffer) cache misses that severely deteriorate primesum's performance. Fortunately the Linux kernel allows to enable transparent huge pages so that large memory allocations will automatically be done using huge pages instead of ordinary pages which dramatically reduces the number of TLB cache misses.

sudo su

# Enable transparent huge pages until next reboot
echo always > /sys/kernel/mm/transparent_hugepage/enabled
echo always > /sys/kernel/mm/transparent_hugepage/defrag

Benchmark

x Sum of the primes below x Time elapsed
1010 2,220,822,432,581,729,238 0.01s
1011 201,467,077,743,744,681,014 0.02s
1012 18,435,588,552,550,705,911,377 0.04s
1013 1,699,246,443,377,779,418,889,494 0.11s
1014 157,589,260,710,736,940,541,561,021 0.36s
1015 14,692,398,516,908,006,398,225,702,366 1.16s
1016 1,376,110,854,313,351,899,159,632,866,552 3.66s
1017 129,408,626,276,669,278,966,252,031,311,350 14.60s
1018 12,212,914,292,949,226,570,880,576,733,896,687 66.66s
1019 1,156,251,260,549,368,082,781,614,413,945,980,126 330.01s
1020 109,778,913,483,063,648,128,485,839,045,703,833,541 1486.87s

The benchmarks above were run on an Intel Core i7-6700 CPU (4 x 3.4 GHz) from 2015 using a Linux x64 operating system and primesum was compiled using GCC 6.4.

A046731 world records

x Sum of the primes below x Date Computed by
1021 10449550362130704786220283253063405651965 June 6, 2016 Kim Walisch
1022 996973504763259668279213971353794878368213 June 6, 2016 Kim Walisch
1023 95320530117168404458544684912403185555509650 June 11, 2016 Kim Walisch
1024 9131187511156941634384410084928380134453142199 June 17, 2016 David Baugh
1025 876268031750623105684911815303505535704119354853 Oct. 16, 2016 David Baugh
1026 84227651431208862537105979544170116745778105437780 May. 25, 2022 Kim Walisch

Note that the sum of the primes below 10^21 was already correctly computed by Marc Deléglise in 2009 but when he verified the result using his program he found a different result (off by 1) so he withdrew his result in 2011.

A099824 world records

n Sum of the first n primes Date Computed by
1018 21849887810843912935127758942358047227 June 5, 2016 Kim Walisch
1019 2302808849326957165657230565155878163277 June 5, 2016 Kim Walisch
1020 242048824942159504049568772767666927073373 June 5, 2016 Kim Walisch
1021 25380411223557757489768734384174904646137001 June 11, 2016 Kim Walisch
1022 2655479563137417712148525630666125075397977159 June 22, 2016 David Baugh
1023 277281399946560013844427926899019949823102890613 Sep. 26, 2016 David Baugh
1024 28900534863094599803598612528087047372125211931087 June 17, 2022 Kim Walisch

A130739 world records

n Sum of the primes < 2^n Date Computed by
271 57230460176857192458791870659870195302414 Dec. 26, 2017 Kim Walisch
272 225709510085333603256262210540764048485810 Dec. 26, 2017 Kim Walisch
273 890344379866902468590503993853978913148982 Dec. 26, 2017 Kim Walisch
274 3512767258692956754932236839569828523905141 Dec. 26, 2017 Kim Walisch
275 13861865005427848960138734445963535022604898 Dec. 26, 2017 Kim Walisch
276 54710756810055087402063527107893581408200826 Dec. 26, 2017 Kim Walisch
277 215973500680654121229780243886194476543303643 Dec. 26, 2017 Kim Walisch
278 852713035956963663153441533770552801919275705 Dec. 26, 2017 Kim Walisch
279 3367271267053300856599603567833163229921782198 Dec. 26, 2017 Kim Walisch
280 13299160452380363326976224185417674340116996121 Dec. 26, 2017 Kim Walisch

References

  1. M. Deléglise and Jean-Louis Nicolas, Maximal product of primes whose sum is bounded, 3 Jul 2012, https://arxiv.org/abs/1207.0603.