Powerful numbers: Difference between revisions
(Added Wren) |
(Added C++ solution) |
||
Line 42: | Line 42: | ||
<br><br> |
<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}}== |
=={{header|Go}}== |
Revision as of 14:02, 30 December 2020
A k-powerful (or k-full) number is a positive integer n such that for every prime number p dividing n, p^k also divides n.
These are numbers of the form:
2-powerful = a^2 * b^3, for a,b >= 1 3-powerful = a^3 * b^4 * c^5, for a,b,c >= 1 4-powerful = a^4 * b^5 * c^6 * d^7, for a,b,c,d >= 1 ... k-powerful = a^k * b^(k+1) * c^(k+2) *...* ω^(2*k-1), for a,b,c,...,ω >= 1
- Task
Write a function that generates all the k-powerful numbers less than or equal to n.
- For k = 2..10, generate the set of k-powerful numbers <= 10^k and show the first 5 and the last 5 terms, along with the length of the set.
Write a function that counts the number of k-powerful numbers less than or equal to n. (optional)
- For k = 2..10, show the number of k-powerful numbers less than or equal to 10^j, for 0 <= j < k+10.
- See also
C++
<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>
- Output:
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
Go
Curiously, the 'powerful' function is producing duplicates which the other existing solutions don't seem to suffer from. It's easily dealt with by using a set (rather than a slice) but means that we're unable to take advantage of the counting shortcut - not that it matters as the whole thing still runs in less than 0.4 seconds! <lang go>package main
import (
"fmt" "math" "sort"
)
const adj = 0.0001 // adjustment to ensure f/p square root exact for perfect integer squares
var primes = []uint64{
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
func gcd(x, y uint64) uint64 {
for y != 0 { x, y = y, x%y } return x
}
func isSquareFree(x uint64) bool {
for _, p := range primes { p2 := p * p if p2 > x { break } if x%p2 == 0 { return false } } return true
}
func iroot(x, p uint64) uint64 {
return uint64(math.Pow(float64(x), 1.0/float64(p)) + adj)
}
func ipow(x, p uint64) uint64 {
prod := uint64(1) for p > 0 { if p&1 != 0 { prod *= x } p >>= 1 x *= x } return prod
}
func powerful(n, k uint64) []uint64 {
set := make(map[uint64]bool) var f func(m, r uint64) // recursive closure f = func(m, r uint64) { if r < k { set[m] = true return } for v := uint64(1); v <= iroot(n/m, r); v++ { if r > k { if !isSquareFree(v) || gcd(m, v) != 1 { continue } } f(m*ipow(v, r), r-1) } } f(1, (1<<k)-1) list := make([]uint64, 0, len(set)) for key := range set { list = append(list, key) } sort.Slice(list, func(i, j int) bool { return list[i] < list[j] }) return list
}
func main() {
power := uint64(10) for k := uint64(2); k <= 10; k++ { power *= 10 a := powerful(power, k) le := len(a) h, t := a[0:5], a[le-5:] fmt.Printf("%d %2d-powerful numbers <= 10^%-2d: %v ... %v\n", le, k, k, h, t) } fmt.Println() for k := uint64(2); k <= 10; k++ { power := uint64(1) var counts []int for j := uint64(0); j < k+10; j++ { a := powerful(power, k) counts = append(counts, len(a)) power *= 10 } j := k + 10 fmt.Printf("Count of %2d-powerful numbers <= 10^j, j in [0, %d): %v\n", k, j, counts) }
}</lang>
- Output:
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, j in [0, 12): [1 4 14 54 185 619 2027 6553 21044 67231 214122 680330] Count of 3-powerful numbers <= 10^j, j in [0, 13): [1 2 7 20 51 129 307 713 1645 3721 8348 18589 41136] Count of 4-powerful numbers <= 10^j, j in [0, 14): [1 1 5 11 25 57 117 235 464 906 1741 3312 6236 11654] Count of 5-powerful numbers <= 10^j, j in [0, 15): [1 1 3 8 16 32 63 117 211 375 659 1153 2000 3402 5770] Count of 6-powerful numbers <= 10^j, j in [0, 16): [1 1 2 6 12 21 38 70 121 206 335 551 900 1451 2326 3706] Count of 7-powerful numbers <= 10^j, j in [0, 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, j in [0, 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, j in [0, 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, j in [0, 20): [1 1 1 1 5 9 14 21 28 43 68 104 155 227 322 447 621 858 1192 1651]
Java
<lang Java> import java.math.BigInteger; import java.util.ArrayList; import java.util.Collections; import java.util.HashSet; import java.util.List; import java.util.Set;
public class PowerfulNumbers {
public static void main(String[] args) { System.out.printf("Task: For k = 2..10, generate the set of k-powerful numbers <= 10^k and show the first 5 and the last 5 terms, along with the length of the set%n"); for ( int k = 2 ; k <= 10 ; k++ ) { BigInteger max = BigInteger.valueOf(10).pow(k); List<BigInteger> powerfulNumbers = getPowerFulNumbers(max, k); System.out.printf("There are %d %d-powerful numbers between 1 and %d. %nList: %s%n", powerfulNumbers.size(), k, max, getList(powerfulNumbers)); } System.out.printf("%nTask: For k = 2..10, show the number of k-powerful numbers less than or equal to 10^j, for 0 <= j < k+10%n"); for ( int k = 2 ; k <= 10 ; k++ ) { List<Integer> powCount = new ArrayList<>(); for ( int j = 0 ; j < k+10 ; j++ ) { BigInteger max = BigInteger.valueOf(10).pow(j); powCount.add(countPowerFulNumbers(max, k)); } System.out.printf("Count of %2d-powerful numbers <= 10^j, j in [0, %d]: %s%n", k, k+9, powCount); } } private static String getList(List<BigInteger> list) { StringBuilder sb = new StringBuilder(); sb.append(list.subList(0, 5).toString().replace("]", "")); sb.append(" ... "); sb.append(list.subList(list.size()-5, list.size()).toString().replace("[", "")); return sb.toString(); }
private static int countPowerFulNumbers(BigInteger max, int k) { return potentialPowerful(max, k).size(); }
private static List<BigInteger> getPowerFulNumbers(BigInteger max, int k) { List<BigInteger> powerfulNumbers = new ArrayList<>(potentialPowerful(max, k)); Collections.sort(powerfulNumbers); return powerfulNumbers; }
private static Set<BigInteger> potentialPowerful(BigInteger max, int k) { // Setup int[] indexes = new int[k]; for ( int i = 0 ; i < k ; i++ ) { indexes[i] = 1; }
Set<BigInteger> powerful = new HashSet<>(); boolean foundPower = true; while ( foundPower ) { boolean genPowerful = false; for ( int index = 0 ; index < k ; index++ ) { BigInteger power = BigInteger.ONE; for ( int i = 0 ; i < k ; i++ ) { power = power.multiply(BigInteger.valueOf(indexes[i]).pow(k+i)); } if ( power.compareTo(max) <= 0 ) { powerful.add(power); indexes[0] += 1; genPowerful = true; break; } else { indexes[index] = 1; if ( index < k-1 ) { indexes[index+1] += 1; } } } if ( ! genPowerful ) { foundPower = false; } }
return powerful; }
} </lang>
- Output:
Task: For k = 2..10, generate the set of k-powerful numbers <= 10^k and show the first 5 and the last 5 terms, along with the length of the set There are 14 2-powerful numbers between 1 and 100. List: [1, 4, 8, 9, 16 ... 49, 64, 72, 81, 100] There are 20 3-powerful numbers between 1 and 1000. List: [1, 8, 16, 27, 32 ... 625, 648, 729, 864, 1000] There are 25 4-powerful numbers between 1 and 10000. List: [1, 16, 32, 64, 81 ... 5184, 6561, 7776, 8192, 10000] There are 32 5-powerful numbers between 1 and 100000. List: [1, 32, 64, 128, 243 ... 65536, 69984, 78125, 93312, 100000] There are 38 6-powerful numbers between 1 and 1000000. List: [1, 64, 128, 256, 512 ... 559872, 746496, 823543, 839808, 1000000] There are 46 7-powerful numbers between 1 and 10000000. List: [1, 128, 256, 512, 1024 ... 7558272, 8388608, 8957952, 9765625, 10000000] There are 52 8-powerful numbers between 1 and 100000000. List: [1, 256, 512, 1024, 2048 ... 60466176, 67108864, 80621568, 90699264, 100000000] There are 59 9-powerful numbers between 1 and 1000000000. List: [1, 512, 1024, 2048, 4096 ... 644972544, 725594112, 816293376, 967458816, 1000000000] There are 68 10-powerful numbers between 1 and 10000000000. List: [1, 1024, 2048, 4096, 8192 ... 7739670528, 8589934592, 8707129344, 9795520512, 10000000000] Task: For k = 2..10, show the number of k-powerful numbers less than or equal to 10^j, for 0 <= j < k+10 Count of 2-powerful numbers <= 10^j, j in [0, 11]: [1, 4, 14, 54, 185, 619, 2027, 6553, 21044, 67231, 214122, 680330] Count of 3-powerful numbers <= 10^j, j in [0, 12]: [1, 2, 7, 20, 51, 129, 307, 713, 1645, 3721, 8348, 18589, 41136] Count of 4-powerful numbers <= 10^j, j in [0, 13]: [1, 1, 5, 11, 25, 57, 117, 235, 464, 906, 1741, 3312, 6236, 11654] Count of 5-powerful numbers <= 10^j, j in [0, 14]: [1, 1, 3, 8, 16, 32, 63, 117, 211, 375, 659, 1153, 2000, 3402, 5770] Count of 6-powerful numbers <= 10^j, j in [0, 15]: [1, 1, 2, 6, 12, 21, 38, 70, 121, 206, 335, 551, 900, 1451, 2326, 3706] Count of 7-powerful numbers <= 10^j, j in [0, 16]: [1, 1, 1, 4, 10, 16, 26, 46, 77, 129, 204, 318, 495, 761, 1172, 1799, 2740] Count of 8-powerful numbers <= 10^j, j in [0, 17]: [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, j in [0, 18]: [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, j in [0, 19]: [1, 1, 1, 1, 5, 9, 14, 21, 28, 43, 68, 104, 155, 227, 322, 447, 621, 858, 1192, 1651]
Julia
<lang julia>using Primes
is_kpowerful(n, k) = all(x -> x[2] >= k, factor(n)) # not used here
is_squarefree(n) = all(x -> x[2] == 1, factor(n)) rootdiv(n, m, r) = Int128(floor(div(n, m)^(1/r) + 0.0000001))
function genkpowerful(n, k)
ret = Int128[] function inner(m, r) if r < k push!(ret, m) else for a in 1:rootdiv(n, m, r) if r <= k || (gcd(a, m) == 1 && is_squarefree(a)) inner(m * Int128(a)^r, r - 1) end end end end inner(1, 2 * k - 1) return unique(sort(Int.(ret)))
end
function kpowerfulcount(n, k)
count = Int128(0) function inner(m, r) if r <= k count += rootdiv(n, m, r) else for a in 1:rootdiv(n, m, r) if gcd(a, m) == 1 && is_squarefree(a) inner(m * a^r, r - 1) end end end end inner(1, 2*k - 1) return Int(count)
end
for k in 2:10
a = genkpowerful(10^k, k) len = length(a) print("The set of $k-powerful numbers between 1 and 10^$k has $len members:\n[") for i in [1:5 ; len-5:len] print(a[i], i == 5 ? " ... " : i == len ? "]\n" : ", ") end
end for k in 2:10
print("The count of $k-powerful numbers from 1 to 10^j for j in 0:$(k+9) is: ", [kpowerfulcount(Int128(10)^j, k) for j in 0:(k+9)], "\n")
end
</lang>
- Output:
The set of 2-powerful numbers between 1 and 10^2 has 14 members: [1, 4, 8, 9, 16 ... 36, 49, 64, 72, 81, 100] The set of 3-powerful numbers between 1 and 10^3 has 20 members: [1, 8, 16, 27, 32 ... 512, 625, 648, 729, 864, 1000] The set of 4-powerful numbers between 1 and 10^4 has 25 members: [1, 16, 32, 64, 81 ... 4096, 5184, 6561, 7776, 8192, 10000] The set of 5-powerful numbers between 1 and 10^5 has 32 members: [1, 32, 64, 128, 243 ... 62208, 65536, 69984, 78125, 93312, 100000] The set of 6-powerful numbers between 1 and 10^6 has 38 members: [1, 64, 128, 256, 512 ... 531441, 559872, 746496, 823543, 839808, 1000000] The set of 7-powerful numbers between 1 and 10^7 has 46 members: [1, 128, 256, 512, 1024 ... 6718464, 7558272, 8388608, 8957952, 9765625, 10000000] The set of 8-powerful numbers between 1 and 10^8 has 52 members: [1, 256, 512, 1024, 2048 ... 53747712, 60466176, 67108864, 80621568, 90699264, 100000000] The set of 9-powerful numbers between 1 and 10^9 has 59 members: [1, 512, 1024, 2048, 4096 ... 544195584, 644972544, 725594112, 816293376, 967458816, 1000000000] The set of 10-powerful numbers between 1 and 10^10 has 68 members: [1, 1024, 2048, 4096, 8192 ... 6530347008, 7739670528, 8589934592, 8707129344, 9795520512, 10000000000] The count of 2-powerful numbers from 1 to 10^j for j in 0:11 is: [1, 4, 14, 54, 185, 619, 2027, 6553, 21044, 67231, 214122, 680330] The count of 3-powerful numbers from 1 to 10^j for j in 0:12 is: [1, 2, 7, 20, 51, 129, 307, 713, 1645, 3721, 8348, 18589, 41136] The count of 4-powerful numbers from 1 to 10^j for j in 0:13 is: [1, 1, 5, 11, 25, 57, 117, 235, 464, 906, 1741, 3312, 6236, 11654] The count of 5-powerful numbers from 1 to 10^j for j in 0:14 is: [1, 1, 3, 8, 16, 32, 63, 117, 211, 375, 659, 1153, 2000, 3402, 5770] The count of 6-powerful numbers from 1 to 10^j for j in 0:15 is: [1, 1, 2, 6, 12, 21, 38, 70, 121, 206, 335, 551, 900, 1451, 2326, 3706] The count of 7-powerful numbers from 1 to 10^j for j in 0:16 is: [1, 1, 1, 4, 10, 16, 26, 46, 77, 129, 204, 318, 495, 761, 1172, 1799, 2740] The count of 8-powerful numbers from 1 to 10^j for j in 0:17 is: [1, 1, 1, 3, 8, 13, 19, 32, 52, 85, 135, 211, 315, 467, 689, 1016, 1496, 2191] The count of 9-powerful numbers from 1 to 10^j for j in 0:18 is: [1, 1, 1, 2, 6, 11, 16, 24, 38, 59, 94, 145, 217, 317, 453, 644, 919, 1308, 1868] The count of 10-powerful numbers from 1 to 10^j for j in 0:19 is: [1, 1, 1, 1, 5, 9, 14, 21, 28, 43, 68, 104, 155, 227, 322, 447, 621, 858, 1192, 1651]
Perl
Generation
<lang perl>use 5.020; use ntheory qw(is_square_free); use experimental qw(signatures); use Math::AnyNum qw(:overload idiv iroot ipow is_coprime);
sub powerful_numbers ($n, $k = 2) {
my @powerful;
sub ($m, $r) { if ($r < $k) { push @powerful, $m; return; } for my $v (1 .. iroot(idiv($n, $m), $r)) { if ($r > $k) { is_square_free($v) || next; is_coprime($m, $v) || next; } __SUB__->($m * ipow($v, $r), $r - 1); } }->(1, 2*$k - 1);
sort { $a <=> $b } @powerful;
}
foreach my $k (2 .. 10) {
my @a = powerful_numbers(10**$k, $k); my $h = join(', ', @a[0..4]); my $t = join(', ', @a[$#a-4..$#a]); printf("For k=%-2d there are %d k-powerful numbers <= 10^k: [%s, ..., %s]\n", $k, scalar(@a), $h, $t);
}</lang>
- Output:
For k=2 there are 14 k-powerful numbers <= 10^k: [1, 4, 8, 9, 16, ..., 49, 64, 72, 81, 100] For k=3 there are 20 k-powerful numbers <= 10^k: [1, 8, 16, 27, 32, ..., 625, 648, 729, 864, 1000] For k=4 there are 25 k-powerful numbers <= 10^k: [1, 16, 32, 64, 81, ..., 5184, 6561, 7776, 8192, 10000] For k=5 there are 32 k-powerful numbers <= 10^k: [1, 32, 64, 128, 243, ..., 65536, 69984, 78125, 93312, 100000] For k=6 there are 38 k-powerful numbers <= 10^k: [1, 64, 128, 256, 512, ..., 559872, 746496, 823543, 839808, 1000000] For k=7 there are 46 k-powerful numbers <= 10^k: [1, 128, 256, 512, 1024, ..., 7558272, 8388608, 8957952, 9765625, 10000000] For k=8 there are 52 k-powerful numbers <= 10^k: [1, 256, 512, 1024, 2048, ..., 60466176, 67108864, 80621568, 90699264, 100000000] For k=9 there are 59 k-powerful numbers <= 10^k: [1, 512, 1024, 2048, 4096, ..., 644972544, 725594112, 816293376, 967458816, 1000000000] For k=10 there are 68 k-powerful numbers <= 10^k: [1, 1024, 2048, 4096, 8192, ..., 7739670528, 8589934592, 8707129344, 9795520512, 10000000000]
Counting
<lang perl>use 5.020; use ntheory qw(is_square_free); use experimental qw(signatures); use Math::AnyNum qw(:overload idiv iroot ipow is_coprime);
sub powerful_count ($n, $k = 2) {
my $count = 0;
sub ($m, $r) { if ($r <= $k) { $count += iroot(idiv($n, $m), $r); return; } for my $v (1 .. iroot(idiv($n, $m), $r)) { is_square_free($v) || next; is_coprime($m, $v) || next; __SUB__->($m * ipow($v, $r), $r - 1); } }->(1, 2*$k - 1);
return $count;
}
foreach my $k (2 .. 10) {
printf("Number of %2d-powerful <= 10^j for 0 <= j < %d: {%s}\n", $k, $k+10, join(', ', map { powerful_count(ipow(10, $_), $k) } 0..($k+10-1)));
}</lang>
- Output:
Number of 2-powerful <= 10^j for 0 <= j < 12: {1, 4, 14, 54, 185, 619, 2027, 6553, 21044, 67231, 214122, 680330} Number of 3-powerful <= 10^j for 0 <= j < 13: {1, 2, 7, 20, 51, 129, 307, 713, 1645, 3721, 8348, 18589, 41136} Number of 4-powerful <= 10^j for 0 <= j < 14: {1, 1, 5, 11, 25, 57, 117, 235, 464, 906, 1741, 3312, 6236, 11654} Number of 5-powerful <= 10^j for 0 <= j < 15: {1, 1, 3, 8, 16, 32, 63, 117, 211, 375, 659, 1153, 2000, 3402, 5770} Number of 6-powerful <= 10^j for 0 <= j < 16: {1, 1, 2, 6, 12, 21, 38, 70, 121, 206, 335, 551, 900, 1451, 2326, 3706} Number of 7-powerful <= 10^j for 0 <= j < 17: {1, 1, 1, 4, 10, 16, 26, 46, 77, 129, 204, 318, 495, 761, 1172, 1799, 2740} Number of 8-powerful <= 10^j for 0 <= j < 18: {1, 1, 1, 3, 8, 13, 19, 32, 52, 85, 135, 211, 315, 467, 689, 1016, 1496, 2191} Number of 9-powerful <= 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} Number of 10-powerful <= 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}
Phix
priority queue
Tried a slightly different approach, but it gets 7/10 at best on performance. <lang Phix>include mpfr.e
integer pq = NULL -- data is the prime powers, eg {2,2} for 2^2*3^2
-- priority is the mpz of that, eg/ie 36
procedure padd(mpz n, np, sequence s)
if pq=NULL then pq = pq_new(MIN_HEAP,routine_id("mpz_cmp")) end if if mpz_cmp(np,n)<=0 then pq_add({s,mpz_init_set(np)},pq) end if
end procedure
procedure add_next(integer k, mpz n, p, sequence s)
mpz np = mpz_init() integer l = length(s) for i=1 to l do integer ki = iff(s[i]=0?k:1) mpz_ui_pow_ui(np,get_prime(i),ki) mpz_mul(np,np,p) s[i] += ki padd(n,np,s) s[i] -= ki end for mpz_ui_pow_ui(np,get_prime(l+1),k) if l>0 and s[l]=k and s[1..l-1]==repeat(0,l-1) then padd(n,np,0&s) elsif s={} then mpz_mul(np,np,p) padd(n,np,s&k) end if
end procedure
function powerful(integer k, mpz n)
mpz prevp = mpz_init(1) sequence res = {prevp} add_next(k,n,prevp,{}) while pq_size(pq) do {sequence s, mpz p} = pq_pop(pq) if mpz_cmp(p,prevp)!=0 then res &= p add_next(k,n,p,s) prevp = p end if end while return res
end function
mpz p = mpz_init(10) for k=2 to 10 do
mpz_mul_si(p,p,10) sequence s = powerful(k,p) integer l = length(s) for i=1 to 5 do s[i] = mpz_get_str(s[i]) s[-i] = mpz_get_str(s[-i]) end for s[6..-6] = {"..."} s = join(s,",") printf(1,"%d %2d-powerful numbers <= 10^%-2d : %s\n",{l,k,k,s})
end for
puts(1,"\n") --Not really fast enough, so only doing to k+5..k+8 for the first 4, but k+9 for last 5 for k=2 to 10 do
sequence counts = {} integer lim = k+min(k+3,9) mpz_set_si(p,1) for j=0 to lim do printf(1,"counting (%d/%d)...\r",{j,lim}) counts &= length(powerful(k,p)) mpz_mul_si(p,p,10) end for printf(1,"Counts of %2d-powerful numbers <= 10^(0..%d) : %v\n",{k,lim,counts})
end for</lang>
- Output:
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 Counts of 2-powerful numbers <= 10^(0..7) : {1,4,14,54,185,619,2027,6553} Counts of 3-powerful numbers <= 10^(0..9) : {1,2,7,20,51,129,307,713,1645,3721} Counts of 4-powerful numbers <= 10^(0..11) : {1,1,5,11,25,57,117,235,464,906,1741,3312} Counts of 5-powerful numbers <= 10^(0..13) : {1,1,3,8,16,32,63,117,211,375,659,1153,2000,3402} Counts of 6-powerful numbers <= 10^(0..15) : {1,1,2,6,12,21,38,70,121,206,335,551,900,1451,2326,3706} Counts of 7-powerful numbers <= 10^(0..16) : {1,1,1,4,10,16,26,46,77,129,204,318,495,761,1172,1799,2740} Counts of 8-powerful numbers <= 10^(0..17) : {1,1,1,3,8,13,19,32,52,85,135,211,315,467,689,1016,1496,2191} Counts of 9-powerful numbers <= 10^(0..18) : {1,1,1,2,6,11,16,24,38,59,94,145,217,317,453,644,919,1308,1868} Counts of 10-powerful numbers <= 10^(0..19) : {1,1,1,1,5,9,14,21,28,43,68,104,155,227,322,447,621,858,1192,1651}
translation
Significantly faster. The last few counts were wrong when using native ints/atoms, so I went gmp, which means it also works on 32-bit. <lang Phix>include mpfr.e
function powerful(mpz n, integer k, sequence res={}, mpz m=NULL, integer r=0)
if m=NULL then m = mpz_init(1) r = 2*k-1 end if if r<k then res = append(res,iff(mpz_fits_atom(m)?mpz_get_atom(m):mpz_get_str(m))) else mpz t = mpz_init() mpz_fdiv_q(t, n, m) -- t := floor(n/m) {} = mpz_root(t,t,r) -- t = floor(rth root of t) if not mpz_fits_integer(t) then ?9/0 end if integer lim = mpz_get_integer(t) for v=1 to lim do if r<=k or (square_free(v) and mpz_gcd_ui(NULL,m,v)=1) then mpz_ui_pow_ui(t,v,r) -- t:= v^r mpz_mul(t,t,m) -- t*= m res = powerful(n, k, res, t, r-1) end if end for end if return res
end function
function powercount(mpz n, integer k, mpz m=NULL, integer r=0)
atom res = 0 if m=NULL then m = mpz_init(1) r = 2*k-1 end if mpz t = mpz_init() mpz_fdiv_q(t, n, m) -- t := floor(n/m) {} = mpz_root(t,t,r) -- t = floor(rth root of t) if not mpz_fits_integer(t) then ?9/0 end if integer lim = mpz_get_integer(t) if r<=k then res += lim else for v=1 to lim do if square_free(v) and mpz_gcd_ui(NULL,m,v)=1 then mpz_ui_pow_ui(t,v,r) -- t:= v^r mpz_mul(t,t,m) -- t*= m res += powercount(n, k, t, r-1) end if end for end if return res
end function
atom t0 = time() mpz p = mpz_init(10) for k=2 to 10 do
mpz_mul_si(p,p,10) sequence s = sort(powerful(p, k)) integer l = length(s) s[6..-6] = {"..."} s = ppf(s,{pp_FltFmt,"%d",pp_StrFmt,-1,pp_IntCh,false,pp_Maxlen,100}) printf(1,"%d %2d-powerful numbers <= 10^%-2d : %s\n",{l,k,k,s})
end for puts(1,"\n") for k=2 to 10 do
mpz_set_si(p,1) sequence counts = {} for j=0 to k+9 do counts = append(counts, powercount(p, k)) mpz_mul_si(p,p,10) end for printf(1,"Counts of %2d-powerful numbers <= 10^(0..%d) : %v\n",{k,k+9,counts})
end for ?elapsed(time()-t0)</lang>
- Output:
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} Counts of 2-powerful numbers <= 10^(0..11) : {1,4,14,54,185,619,2027,6553,21044,67231,214122,680330} Counts of 3-powerful numbers <= 10^(0..12) : {1,2,7,20,51,129,307,713,1645,3721,8348,18589,41136} Counts of 4-powerful numbers <= 10^(0..13) : {1,1,5,11,25,57,117,235,464,906,1741,3312,6236,11654} Counts of 5-powerful numbers <= 10^(0..14) : {1,1,3,8,16,32,63,117,211,375,659,1153,2000,3402,5770} Counts of 6-powerful numbers <= 10^(0..15) : {1,1,2,6,12,21,38,70,121,206,335,551,900,1451,2326,3706} Counts of 7-powerful numbers <= 10^(0..16) : {1,1,1,4,10,16,26,46,77,129,204,318,495,761,1172,1799,2740} Counts of 8-powerful numbers <= 10^(0..17) : {1,1,1,3,8,13,19,32,52,85,135,211,315,467,689,1016,1496,2191} Counts of 9-powerful numbers <= 10^(0..18) : {1,1,1,2,6,11,16,24,38,59,94,145,217,317,453,644,919,1308,1868} Counts of 10-powerful numbers <= 10^(0..19) : {1,1,1,1,5,9,14,21,28,43,68,104,155,227,322,447,621,858,1192,1651} "0.8s"
Raku
(formerly Perl 6)
Raku has no handy pre-made nth integer root routine so has the same problem as Go with needing a slight "fudge factor" in the nth root calculation.
<lang perl6>sub super (\x) { x.trans([<0123456789>.comb] => [<⁰¹²³⁴⁵⁶⁷⁸⁹>.comb]) }
sub is-square-free (Int \n) {
constant @p = ^100 .map: { next unless .is-prime; .² }; for @p -> \p { return False if n %% p } True
}
sub powerfuls (\n, \k, \enumerate = False) {
my @powerful; p(1, 2*k - 1); sub p (\m, \r) { if r < k { enumerate ?? @powerful.push(m) !! ++@powerful[m - 1 ?? (m - 1).chars !! 0]; return } for 1 .. ((n / m) ** (1/r) + .0001).Int -> \v { if r > k { next unless is-square-free(v); next unless m gcd v == 1; } p(m * v ** r, r - 1) } } @powerful;
}
put "Count and first and last five enumerated n-powerful numbers in 10ⁿ:"; for 2..10 -> \k {
my @powerful = sort powerfuls(10**k, k, True); printf "%2d %2s-powerful numbers <= 10%-2s: %s ... %s\n", +@powerful, k, super(k), @powerful.head(5).join(", "), @powerful.tail(5).join(", ");
}
put "\nCounts in each order of magnitude:"; my $top = 9; for 2..10 -> \k {
printf "%2s-powerful numbers <= 10ⁿ (where 0 <= n <= %d): ", k, $top+k; quietly say join ', ', [\+] powerfuls(10**($top + k), k);
}</lang>
- Output:
Count and first and last five enumerated n-powerful numbers in 10ⁿ: 14 2-powerful numbers <= 10² : 1, 4, 8, 9, 16 ... 49, 64, 72, 81, 100 20 3-powerful numbers <= 10³ : 1, 8, 16, 27, 32 ... 625, 648, 729, 864, 1000 25 4-powerful numbers <= 10⁴ : 1, 16, 32, 64, 81 ... 5184, 6561, 7776, 8192, 10000 32 5-powerful numbers <= 10⁵ : 1, 32, 64, 128, 243 ... 65536, 69984, 78125, 93312, 100000 38 6-powerful numbers <= 10⁶ : 1, 64, 128, 256, 512 ... 559872, 746496, 823543, 839808, 1000000 46 7-powerful numbers <= 10⁷ : 1, 128, 256, 512, 1024 ... 7558272, 8388608, 8957952, 9765625, 10000000 52 8-powerful numbers <= 10⁸ : 1, 256, 512, 1024, 2048 ... 60466176, 67108864, 80621568, 90699264, 100000000 59 9-powerful numbers <= 10⁹ : 1, 512, 1024, 2048, 4096 ... 644972544, 725594112, 816293376, 967458816, 1000000000 68 10-powerful numbers <= 10¹⁰: 1, 1024, 2048, 4096, 8192 ... 7739670528, 8589934592, 8707129344, 9795520512, 10000000000 Counts in each order of magnitude: 2-powerful numbers <= 10ⁿ (where 0 <= n <= 11): 1, 4, 14, 54, 185, 619, 2027, 6553, 21044, 67231, 214122, 680330 3-powerful numbers <= 10ⁿ (where 0 <= n <= 12): 1, 2, 7, 20, 51, 129, 307, 713, 1645, 3721, 8348, 18589, 41136 4-powerful numbers <= 10ⁿ (where 0 <= n <= 13): 1, 1, 5, 11, 25, 57, 117, 235, 464, 906, 1741, 3312, 6236, 11654 5-powerful numbers <= 10ⁿ (where 0 <= n <= 14): 1, 1, 3, 8, 16, 32, 63, 117, 211, 375, 659, 1153, 2000, 3402, 5770 6-powerful numbers <= 10ⁿ (where 0 <= n <= 15): 1, 1, 2, 6, 12, 21, 38, 70, 121, 206, 335, 551, 900, 1451, 2326, 3706 7-powerful numbers <= 10ⁿ (where 0 <= n <= 16): 1, 1, 1, 4, 10, 16, 26, 46, 77, 129, 204, 318, 495, 761, 1172, 1799, 2740 8-powerful numbers <= 10ⁿ (where 0 <= n <= 17): 1, 1, 1, 3, 8, 13, 19, 32, 52, 85, 135, 211, 315, 467, 689, 1016, 1496, 2191 9-powerful numbers <= 10ⁿ (where 0 <= n <= 18): 1, 1, 1, 2, 6, 11, 16, 24, 38, 59, 94, 145, 217, 317, 453, 644, 919, 1308, 1868 10-powerful numbers <= 10ⁿ (where 0 <= n <= 19): 1, 1, 1, 1, 5, 9, 14, 21, 28, 43, 68, 104, 155, 227, 322, 447, 621, 858, 1192, 1651
Sidef
Generation
<lang ruby>func powerful(n, k=2) {
var list = []
func (m,r) { if (r < k) { list << m return nil } for a in (1 .. iroot(idiv(n,m), r)) { if (r > k) { a.is_coprime(m) || next a.is_squarefree || next } __FUNC__(m * a**r, r-1) } }(1, 2*k - 1)
return list.sort
}
for k in (2..10) {
var a = powerful(10**k, k) var h = a.head(5).join(', ') var t = a.tail(5).join(', ') printf("For k=%-2d there are %d k-powerful numbers <= 10^k: [%s, ..., %s]\n", k, a.len, h, t)
}</lang>
- Output:
For k=2 there are 14 k-powerful numbers <= 10^k: [1, 4, 8, 9, 16, ..., 49, 64, 72, 81, 100] For k=3 there are 20 k-powerful numbers <= 10^k: [1, 8, 16, 27, 32, ..., 625, 648, 729, 864, 1000] For k=4 there are 25 k-powerful numbers <= 10^k: [1, 16, 32, 64, 81, ..., 5184, 6561, 7776, 8192, 10000] For k=5 there are 32 k-powerful numbers <= 10^k: [1, 32, 64, 128, 243, ..., 65536, 69984, 78125, 93312, 100000] For k=6 there are 38 k-powerful numbers <= 10^k: [1, 64, 128, 256, 512, ..., 559872, 746496, 823543, 839808, 1000000] For k=7 there are 46 k-powerful numbers <= 10^k: [1, 128, 256, 512, 1024, ..., 7558272, 8388608, 8957952, 9765625, 10000000] For k=8 there are 52 k-powerful numbers <= 10^k: [1, 256, 512, 1024, 2048, ..., 60466176, 67108864, 80621568, 90699264, 100000000] For k=9 there are 59 k-powerful numbers <= 10^k: [1, 512, 1024, 2048, 4096, ..., 644972544, 725594112, 816293376, 967458816, 1000000000] For k=10 there are 68 k-powerful numbers <= 10^k: [1, 1024, 2048, 4096, 8192, ..., 7739670528, 8589934592, 8707129344, 9795520512, 10000000000]
Counting
<lang ruby>func powerful_count(n, k=2) {
var count = 0
func (m,r) { if (r <= k) { count += iroot(idiv(n,m), r) return nil } for a in (1 .. iroot(idiv(n,m), r)) { a.is_coprime(m) || next a.is_squarefree || next __FUNC__(m * a**r, r-1) } }(1, 2*k - 1)
return count
}
for k in (2..10) {
var a = (k+10).of {|j| powerful_count(10**j, k) } printf("Number of %2d-powerful numbers <= 10^j, for 0 <= j < #{k+10}: %s\n", k, a)
}</lang>
- Output:
Number of 2-powerful numbers <= 10^j, for 0 <= j < 12: [1, 4, 14, 54, 185, 619, 2027, 6553, 21044, 67231, 214122, 680330] Number of 3-powerful numbers <= 10^j, for 0 <= j < 13: [1, 2, 7, 20, 51, 129, 307, 713, 1645, 3721, 8348, 18589, 41136] Number of 4-powerful numbers <= 10^j, for 0 <= j < 14: [1, 1, 5, 11, 25, 57, 117, 235, 464, 906, 1741, 3312, 6236, 11654] Number 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] Number 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] Number 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] Number 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] Number 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] Number 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]
Wren
<lang ecmascript>import "/big" for BigInt import "/set" for Set import "/sort" for Sort import "/fmt" for Fmt
var potentialPowerful = Fn.new { |max, k|
var indexes = List.filled(k, 1) var powerful = Set.new() var foundPower = true while (foundPower) { var genPowerful = false for (index in 0...k) { var power = BigInt.one for (i in 0...k) power = power * BigInt.new(indexes[i]).pow(k+i) if (power <= max) { powerful.add(power.toString) // can't add BigInts directly as not value type indexes[0] = indexes[0] + 1 genPowerful = true break } indexes[index] = 1 if (index < k - 1) indexes[index+1] = indexes[index+1] + 1 } if (!genPowerful) foundPower = false } return powerful.map { |p| BigInt.new(p) }.toList
}
var countPowerfulNumbers = Fn.new{ |max, k| potentialPowerful.call(max, k).count }
var getPowerfulNumbers = Fn.new { |max, k|
var powerfulNumbers = potentialPowerful.call(max, k) Sort.quick(powerfulNumbers) return powerfulNumbers
}
for (k in 2..10) {
var max = BigInt.ten.pow(k) var powerfulNumbers = getPowerfulNumbers.call(max, k) var count = powerfulNumbers.count Fmt.print("There are $d $d-powerful numbers between 1 and $i", count, k, max) Fmt.print("List: [$i ... $i]", powerfulNumbers[0..4], powerfulNumbers[-5..-1])
} System.print() for (k in 2..10) {
var powCount = [] for (j in 0...k+10) { var max = BigInt.ten.pow(j) powCount.add(countPowerfulNumbers.call(max, k)) } Fmt.print("Count of $2d-powerful numbers <= 10^j, j in [0, $d]: $n", k, k + 9, powCount)
}</lang>
- Output:
There are 14 2-powerful numbers between 1 and 100 List: [1 4 8 9 16 ... 49 64 72 81 100] There are 20 3-powerful numbers between 1 and 1000 List: [1 8 16 27 32 ... 625 648 729 864 1000] There are 25 4-powerful numbers between 1 and 10000 List: [1 16 32 64 81 ... 5184 6561 7776 8192 10000] There are 32 5-powerful numbers between 1 and 100000 List: [1 32 64 128 243 ... 65536 69984 78125 93312 100000] There are 38 6-powerful numbers between 1 and 1000000 List: [1 64 128 256 512 ... 559872 746496 823543 839808 1000000] There are 46 7-powerful numbers between 1 and 10000000 List: [1 128 256 512 1024 ... 7558272 8388608 8957952 9765625 10000000] There are 52 8-powerful numbers between 1 and 100000000 List: [1 256 512 1024 2048 ... 60466176 67108864 80621568 90699264 100000000] There are 59 9-powerful numbers between 1 and 1000000000 List: [1 512 1024 2048 4096 ... 644972544 725594112 816293376 967458816 1000000000] There are 68 10-powerful numbers between 1 and 10000000000 List: [1 1024 2048 4096 8192 ... 7739670528 8589934592 8707129344 9795520512 10000000000] Count of 2-powerful numbers <= 10^j, j in [0, 11]: [1, 4, 14, 54, 185, 619, 2027, 6553, 21044, 67231, 214122, 680330] Count of 3-powerful numbers <= 10^j, j in [0, 12]: [1, 2, 7, 20, 51, 129, 307, 713, 1645, 3721, 8348, 18589, 41136] Count of 4-powerful numbers <= 10^j, j in [0, 13]: [1, 1, 5, 11, 25, 57, 117, 235, 464, 906, 1741, 3312, 6236, 11654] Count of 5-powerful numbers <= 10^j, j in [0, 14]: [1, 1, 3, 8, 16, 32, 63, 117, 211, 375, 659, 1153, 2000, 3402, 5770] Count of 6-powerful numbers <= 10^j, j in [0, 15]: [1, 1, 2, 6, 12, 21, 38, 70, 121, 206, 335, 551, 900, 1451, 2326, 3706] Count of 7-powerful numbers <= 10^j, j in [0, 16]: [1, 1, 1, 4, 10, 16, 26, 46, 77, 129, 204, 318, 495, 761, 1172, 1799, 2740] Count of 8-powerful numbers <= 10^j, j in [0, 17]: [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, j in [0, 18]: [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, j in [0, 19]: [1, 1, 1, 1, 5, 9, 14, 21, 28, 43, 68, 104, 155, 227, 322, 447, 621, 858, 1192, 1651]
zkl
<lang zkl>fcn isSquareFree(n){
var [const] primes2=T(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 .apply("pow",2); foreach p2 in (primes2){ if(p2>n) break; if(n%p2 == 0) return(False); } True
}
const adj=0.0001; // adjustment to ensure f/r square root exact for perfect integer squares fcn iroot(n,r){ (n.toFloat().pow(1.0/r) + adj).toInt() }
fcn powerfuls(n,k){
fcn(m,r, n,k,powerful){ // recursive closure if(r<k){ powerful[m]=True; return(); } foreach v in ([1..iroot(n/m, r)]){ if(r>k){ if(not isSquareFree(v) or m.gcd(v)!=1) continue; }
self.fcn(m*v.pow(r), r-1, n,k,powerful)
} }(1,(2).pow(k)-1, n,k, powerful:=Dictionary()); powerful.keys.apply("toInt").sort();
}</lang> <lang zkl>println("Count, first and last five enumerated n-powerful numbers in 10\u207f:"); foreach k in ([2..10]){
ps:=powerfuls((10).pow(k),k); println("%2d: %s ... %s".fmt(ps.len(),ps[0,5].concat(" "),ps.tail(5).concat(" ")));
}</lang>
- Output:
Count, first and last five enumerated n-powerful numbers in 10ⁿ: 14: 1 4 8 9 16 ... 49 64 72 81 100 20: 1 8 16 27 32 ... 625 648 729 864 1000 25: 1 16 32 64 81 ... 5184 6561 7776 8192 10000 32: 1 32 64 128 243 ... 65536 69984 78125 93312 100000 38: 1 64 128 256 512 ... 559872 746496 823543 839808 1000000 46: 1 128 256 512 1024 ... 7558272 8388608 8957952 9765625 10000000 52: 1 256 512 1024 2048 ... 60466176 67108864 80621568 90699264 100000000 59: 1 512 1024 2048 4096 ... 644972544 725594112 816293376 967458816 1000000000 68: 1 1024 2048 4096 8192 ... 7739670528 8589934592 8707129344 9795520512 10000000000
Overflows a 64 bit int at the very end, which results in a count of zero. <lang zkl>fcn powerfulsN(n,k){ // count
fcn(m,r, n,k,count){ // recursive closure if(r<=k){ count.incN(iroot(n/m, r)); return() } foreach v in ([1..iroot(n/m, r)]){ if(not isSquareFree(v) or m.gcd(v)!=1) continue;
self.fcn(m*v.pow(r), r-1, n,k,count)
} }(1,2*k - 1, n,k, count:=Ref(0)); count.value
}</lang> <lang zkl>println("Counts in each order of magnitude:"); foreach k in ([2..10]){
print("%2s-powerful numbers <= 10\u207f (n in [0..%d)): ".fmt(k, 10+k)); ps:=[0 .. k+10 -1].apply('wrap(n){ powerfulsN((10).pow(n), k) }); println(ps.concat(" "));
}</lang>
- Output:
Counts in each order of magnitude: 2-powerful numbers <= 10ⁿ (n in [0..12)): 1 4 14 54 185 619 2027 6553 21044 67231 214122 680330 3-powerful numbers <= 10ⁿ (n in [0..13)): 1 2 7 20 51 129 307 713 1645 3721 8348 18589 41136 4-powerful numbers <= 10ⁿ (n in [0..14)): 1 1 5 11 25 57 117 235 464 906 1741 3312 6236 11654 5-powerful numbers <= 10ⁿ (n in [0..15)): 1 1 3 8 16 32 63 117 211 375 659 1153 2000 3402 5770 6-powerful numbers <= 10ⁿ (n in [0..16)): 1 1 2 6 12 21 38 70 121 206 335 551 900 1451 2326 3706 7-powerful numbers <= 10ⁿ (n in [0..17)): 1 1 1 4 10 16 26 46 77 129 204 318 495 761 1172 1799 2740 8-powerful numbers <= 10ⁿ (n in [0..18)): 1 1 1 3 8 13 19 32 52 85 135 211 315 467 689 1016 1496 2191 9-powerful numbers <= 10ⁿ (n in [0..19)): 1 1 1 2 6 11 16 24 38 59 94 145 217 317 453 644 919 1308 1868 10-powerful numbers <= 10ⁿ (n in [0..20)): 1 1 1 1 5 9 14 21 28 43 68 104 155 227 322 447 621 858 1192 0