Powerful numbers: Difference between revisions
("Powerful numbers" - draft task, with "Perl" and "Sidef" entries) |
(Added Go) |
||
Line 42: | Line 42: | ||
<br><br> |
<br><br> |
||
=={{header|Go}}== |
|||
{{trans|Perl}} |
|||
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> |
|||
{{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, 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] |
|||
</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
===Generation=== |
===Generation=== |
Revision as of 18:56, 21 February 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]
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}
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]