Powerful numbers: Difference between revisions
Added C++ solution
(Added Wren) |
(Added C++ solution) |
||
Line 42:
<br><br>
=={{header|C++}}==
{{trans|Go}}
{{trans|Perl}}
<lang cpp>#include <algorithm>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <vector>
bool is_square_free(uint64_t n) {
static constexpr uint64_t primes[] {
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
}; // seems to be enough
for (auto p : primes) {
auto p2 = p * p;
if (p2 > n)
break;
if (n % p2 == 0)
return false;
}
return true;
}
uint64_t iroot(uint64_t n, uint64_t r) {
// adjustment to ensure f/p square root exact for perfect integer squares
static constexpr double adj = 1e-6;
return static_cast<uint64_t>(std::pow(n, 1.0/r) + adj);
}
uint64_t ipow(uint64_t n, uint64_t p) {
uint64_t prod = 1;
for (; p > 0; p >>= 1) {
if (p & 1)
prod *= n;
n *= n;
}
return prod;
}
std::vector<uint64_t> powerful(uint64_t n, uint64_t k) {
std::vector<uint64_t> result;
std::function<void(uint64_t, uint64_t)> f = [&](uint64_t m, uint64_t r) {
if (r < k) {
result.push_back(m);
return;
}
uint64_t root = iroot(n/m, r);
for (uint64_t v = 1; v <= root; ++v) {
if (r > k && (!is_square_free(v) || std::gcd(m, v) != 1))
continue;
f(m * ipow(v, r), r - 1);
}
};
f(1, 2*k - 1);
std::sort(result.begin(), result.end());
return result;
}
uint64_t powerful_count(uint64_t n, uint64_t k) {
uint64_t count = 0;
std::function<void(uint64_t, uint64_t)> f = [&](uint64_t m, uint64_t r) {
if (r <= k) {
count += iroot(n/m, r);
return;
}
uint64_t root = iroot(n/m, r);
for (uint64_t v = 1; v <= root; ++v) {
if (is_square_free(v) && std::gcd(m, v) == 1)
f(m * ipow(v, r), r - 1);
}
};
f(1, 2*k - 1);
return count;
}
int main() {
const size_t max = 5;
for (uint64_t k = 2, p = 100; k <= 10; ++k, p *= 10) {
auto result = powerful(p, k);
std::cout << result.size() << " " << k
<< "-powerful numbers <= 10^" << k << ":";
for (size_t i = 0; i < result.size(); ++i) {
if (i == max)
std::cout << " ...";
else if (i < max || i + max >= result.size())
std::cout << ' ' << result[i];
}
std::cout << '\n';
}
std::cout << '\n';
for (uint64_t k = 2; k <= 10; ++k) {
std::cout << "Count of " << k << "-powerful numbers <= 10^j for 0 <= j < "
<< k + 10 << ":";
for (uint64_t j = 0, p = 1; j < k + 10; ++j, p *= 10)
std::cout << ' ' << powerful_count(p, k);
std::cout << '\n';
}
}</lang>
{{out}}
<pre>
14 2-powerful numbers <= 10^2: 1 4 8 9 16 ... 49 64 72 81 100
20 3-powerful numbers <= 10^3: 1 8 16 27 32 ... 625 648 729 864 1000
25 4-powerful numbers <= 10^4: 1 16 32 64 81 ... 5184 6561 7776 8192 10000
32 5-powerful numbers <= 10^5: 1 32 64 128 243 ... 65536 69984 78125 93312 100000
38 6-powerful numbers <= 10^6: 1 64 128 256 512 ... 559872 746496 823543 839808 1000000
46 7-powerful numbers <= 10^7: 1 128 256 512 1024 ... 7558272 8388608 8957952 9765625 10000000
52 8-powerful numbers <= 10^8: 1 256 512 1024 2048 ... 60466176 67108864 80621568 90699264 100000000
59 9-powerful numbers <= 10^9: 1 512 1024 2048 4096 ... 644972544 725594112 816293376 967458816 1000000000
68 10-powerful numbers <= 10^10: 1 1024 2048 4096 8192 ... 7739670528 8589934592 8707129344 9795520512 10000000000
Count of 2-powerful numbers <= 10^j for 0 <= j < 12: 1 4 14 54 185 619 2027 6553 21044 67231 214122 680330
Count of 3-powerful numbers <= 10^j for 0 <= j < 13: 1 2 7 20 51 129 307 713 1645 3721 8348 18589 41136
Count of 4-powerful numbers <= 10^j for 0 <= j < 14: 1 1 5 11 25 57 117 235 464 906 1741 3312 6236 11654
Count of 5-powerful numbers <= 10^j for 0 <= j < 15: 1 1 3 8 16 32 63 117 211 375 659 1153 2000 3402 5770
Count of 6-powerful numbers <= 10^j for 0 <= j < 16: 1 1 2 6 12 21 38 70 121 206 335 551 900 1451 2326 3706
Count of 7-powerful numbers <= 10^j for 0 <= j < 17: 1 1 1 4 10 16 26 46 77 129 204 318 495 761 1172 1799 2740
Count of 8-powerful numbers <= 10^j for 0 <= j < 18: 1 1 1 3 8 13 19 32 52 85 135 211 315 467 689 1016 1496 2191
Count of 9-powerful numbers <= 10^j for 0 <= j < 19: 1 1 1 2 6 11 16 24 38 59 94 145 217 317 453 644 919 1308 1868
Count of 10-powerful numbers <= 10^j for 0 <= j < 20: 1 1 1 1 5 9 14 21 28 43 68 104 155 227 322 447 621 858 1192 1651
</pre>
=={{header|Go}}==
| |||