Powerful numbers: Difference between revisions
m (Phix/mpfr) |
(Added Wren) |
||
Line 815:
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]
</pre>
=={{header|Wren}}==
{{trans|Java}}
{{libheader|Wren-big}}
{{libheader|Wren-set}}
{{libheader|Wren-sort}}
{{libheader|Wren-fmt}}
<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>
{{out}}
<pre>
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]
</pre>
|
Revision as of 16:18, 23 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
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