Zsigmondy numbers: Difference between revisions

=={{header|C++}}==

<syntaxhighlight lang="cpp">#include <algorithm>

#include <cstdint>

#include <iostream>

#include <numeric>

#include <vector>

std::vector<uint64_t> divisors(uint64_t n) {

std::vector<uint64_t> result{1};

uint64_t power = 2;

for (; (n & 1) == 0; power <<= 1, n >>= 1)

result.push_back(power);

for (uint64_t p = 3; p * p <= n; p += 2) {

size_t size = result.size();

for (power = p; n % p == 0; power *= p, n /= p)

for (size_t i = 0; i != size; ++i)

result.push_back(power * result[i]);

}

if (n > 1) {

size_t size = result.size();

for (size_t i = 0; i != size; ++i)

result.push_back(n * result[i]);

}

sort(result.begin(), result.end());

return result;

}

uint64_t ipow(uint64_t base, uint64_t exp) {

if (exp == 0)

return 1;

if ((exp & 1) == 0)

return ipow(base * base, exp >> 1);

return base * ipow(base * base, (exp - 1) >> 1);

}

uint64_t zsigmondy(uint64_t n, uint64_t a, uint64_t b) {

auto p = ipow(a, n) - ipow(b, n);

auto d = divisors(p);

if (d.size() == 2)

return p;

std::vector<uint64_t> dms(n - 1);

for (uint64_t m = 1; m < n; ++m)

dms[m - 1] = ipow(a, m) - ipow(b, m);

for (auto i = d.rbegin(); i != d.rend(); ++i) {

uint64_t z = *i;

if (all_of(dms.begin(), dms.end(),

[z](uint64_t x) { return std::gcd(x, z) == 1; }))

return z;

}

return 1;

}

void test(uint64_t a, uint64_t b) {

std::cout << "Zsigmondy(n, " << a << ", " << b << "):\n";

for (uint64_t n = 1; n <= 20; ++n) {

std::cout << zsigmondy(n, a, b) << ' ';

}

std::cout << "\n\n";

}

int main() {

test(2, 1);

test(3, 1);

test(4, 1);

test(5, 1);

test(6, 1);

test(7, 1);

test(3, 2);

test(5, 3);

test(7, 3);

test(7, 5);

}</syntaxhighlight>

{{out}}

<pre>Zsigmondy(n, 2, 1):

1 3 7 5 31 1 127 17 73 11 2047 13 8191 43 151 257 131071 19 524287 41

Zsigmondy(n, 3, 1):

2 1 13 5 121 7 1093 41 757 61 88573 73 797161 547 4561 3281 64570081 703 581130733 1181

Zsigmondy(n, 4, 1):

3 5 7 17 341 13 5461 257 1387 41 1398101 241 22369621 3277 49981 65537 5726623061 4033 91625968981 61681

Zsigmondy(n, 5, 1):

4 3 31 13 781 7 19531 313 15751 521 12207031 601 305175781 13021 315121 195313 190734863281 5167 4768371582031 375601

Zsigmondy(n, 6, 1):

5 7 43 37 311 31 55987 1297 46873 1111 72559411 1261 2612138803 5713 1406371 1679617 3385331888947 46441 121871948002099 1634221

Zsigmondy(n, 7, 1):

6 1 19 25 2801 43 137257 1201 39331 2101 329554457 2353 16148168401 102943 4956001 2882401 38771752331201 117307 1899815864228857 1129901

Zsigmondy(n, 3, 2):

1 5 19 13 211 7 2059 97 1009 11 175099 61 1586131 463 3571 6817 129009091 577 1161737179 4621

Zsigmondy(n, 5, 3):

2 1 49 17 1441 19 37969 353 19729 421 24325489 481 609554401 10039 216001 198593 381405156481 12979 9536162033329 288961

Zsigmondy(n, 7, 3):

4 5 79 29 4141 37 205339 1241 127639 341 494287399 2041 24221854021 82573 3628081 2885681 58157596211761 109117 2849723505777919 4871281

Zsigmondy(n, 7, 5):

2 3 109 37 6841 13 372709 1513 176149 1661 964249309 1801 47834153641 75139 3162961 3077713 115933787267041 30133 5689910849522509 3949201

</pre>