4 ms·
The link for #A011260 is https://oeis.org/A011260 https://oeis.org/A011260 There is now a github repository for the software: https://github.com/hayguen/mlpoly
by fjfaase 5y ago
The link for #A011260 is https://oeis.org/A011260 https://oeis.org/A011260
There is now a github repository for the software: https://github.com/hayguen/mlpolygen https://github.com/hayguen/mlpolygen
It is not that simple for larger numbers. The brute force method would require one to check 2^n different values and for each about 2^n steps. That makes 2^2n steps. For n=32 this is about 10^18 steps.
- hvenev 5y agoEvaluating 2^k steps takes O(k) multiplications when done using a fast exponentiation algorithm. Even assuming O(n^2) multiplication and O(n) prime divisors, checking a single candidate shouldn't take more than O(n^4). I'm sure that in reality you can do much better, probably significantly under O(n^3), e.g. because there are fewer prime factors, using a faster multiplication algorithm, and by reusing intermediate results during the exponentiations. Factoring 2^n-1 can be done once for a given n in O(2^(n/4)), so it is not the bottleneck. There are also probably quite a lot of checks that can quickly rule out lots of values without having to give them to the heavy machinery. In the end I expect the total running time to be O(2^n * n^2) or so.