Skip to content

Instantly share code, notes, and snippets.

@Hermann-SW

Hermann-SW/subsetsuM.cpp

Created April 12, 2026 08:20
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Hermann-SW/12dd5d6a5d8b9f5665dfa08e3c3c61fd to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Hermann-SW/12dd5d6a5d8b9f5665dfa08e3c3c61fd to your computer and use it in GitHub Desktop.
Download ZIP
Determine the (only 5) Mersenne prime exponents that cannot be built as sum of previous Mersenne prime exponents
Raw
subsetsuM.cpp
/*
f=subsetsuM
g++ -O3 -Wall -pedantic -Wextra $f.cpp -o $f
cpplint --filter=-legal/copyright,-build/namespaces $f.cpp
cppcheck --enable=all --suppress=missingIncludeSystem $f.cpp --check-config
*/
#include <iostream>
#include <cassert>
#include <cinttypes>
int P[]={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};
int n = sizeof(P) / sizeof(P[0]);
int mx = P[n-1];
int main() {
uint8_t **M = new uint8_t*[1+n];
for (int i=0; i <= n; ++i) { M[i] = new uint8_t[1+mx]; assert(M[i]); }
M[0][0] = 1;
for (int i = 0; i < n; ++i) {
for (int j=0; j <= mx-P[i]; ++j) M[i+1][j] = M[i][j];
for (int j=0; j <= mx-P[i]; ++j) if (M[i][j]) { M[i+1][j + P[i]] = 1; }
}
for (int i = 0; i < n; ++i) {
if (!M[i][P[i]]) {
int j=P[i]-1; while (!M[i][j]) j-=1;
std::cout << P[i] << ": " << j-P[i] << std::endl;
}
}
}
@Hermann-SW
Copy link
Copy Markdown
Author

Hermann-SW commented Apr 12, 2026 •
edited
Loading

Requires less than 6GB RAM:

hermann@8840hs:~$ f=subsetsuM
g++ -O3 -Wall -pedantic -Wextra $f.cpp -o $f
cpplint --filter=-legal/copyright,-build/namespaces $f.cpp
cppcheck --enable=all --suppress=missingIncludeSystem $f.cpp --check-config
Done processing subsetsuM.cpp
Checking subsetsuM.cpp ...
nofile:0:0: information: Active checkers: 4/592 (use --checkers-report=<filename> to see details) [checkersReport]

hermann@8840hs:~$ time ./subsetsuM 
2: -2
3: -1
13: -1
521: -40
756839: -52501

real	0m7.124s
user	0m5.055s
sys	0m2.068s
hermann@8840hs:~$

@Hermann-SW
Copy link
Copy Markdown
Author

Hermann-SW commented Apr 12, 2026 •
edited
Loading

My new laptop 8C/16T AMD 8840HS CPU has -15.2% "Single threaded" rating compared to my 16C/32T AMD 7950X CPU:
https://www.cpubenchmark.net/compare/6016vs5033vs5031/AMD-Ryzen-7-8840HS-vs-AMD-Ryzen-5-7600X-vs-AMD-Ryzen-9-7950X

The -15.2% is quite close to -16.4% from measured "real" runtimes:

hermann@7950x:~$ time ./subsetsuM 
2: -2
3: -1
13: -1
521: -40
756839: -52501

real	0m5,957s
user	0m4,147s
sys	0m1,809s
hermann@7950x:~$

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment