Powerful numbers: Difference between revisions

{{trans|Go}}

{{trans|Perl}}

#include <cmath>

#include <cstdint>

std::cout << '\n';

}

 

{{out}}

{{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!

 

import (

fmt.Printf("Count of %2d-powerful numbers <= 10^j, j in [0, %d): %v\n", k, j, counts)

}

 

{{out}}

 

=={{header|Java}}==

import java.math.BigInteger;

import java.util.ArrayList;

}

 

{{out}}

=={{header|Julia}}==

{{trans|Perl}}

 

is_kpowerful(n, k) = all(x -> x[2] >= k, factor(n)) # not used here

[kpowerfulcount(Int128(10)^j, k) for j in 0:(k+9)], "\n")

end

<pre>

The set of 2-powerful numbers between 1 and 10^2 has 14 members:

==={{header|Support}}===

Similar need for epsilon in <code>iroot</code> as with other double-precision examples.

table.head = function(t,n) local s=T{} n=n>#t and #t or n for i = 1,n do s[i]=t[i] end return s end

table.tail = function(t,n) local s=T{} n=n>#t and #t or n for i = 1,n do s[i]=t[#t-n+i] end return s end

end

return true

 

==={{header|Generation}}===

local powerful = T{}

local function inner(m, r)

local t = a:tail(5):concat(", ")

printf("For k=%-2d there are %d k-powerful numbers <= 10^k: [%s, ..., %s]\n", k, #a, h, t)

{{out}}

<pre>For k=2 there are 14 k-powerful numbers <= 10^k: [1, 4, 8, 9, 16, ..., 49, 64, 72, 81, 100]

 

==={{header|Counting}}===

local count = 0

local function inner(m, r)

end

printf("Number of %2d-powerful <= 10^j for 0 <= j < %d: {%s}\n", k, k+10, counts:concat(", "))

{{out}}

<pre>Number of 2-powerful <= 10^j for 0 <= j < 12: {1, 4, 14, 54, 185, 619, 2027, 6553, 21044, 67231, 214122, 680330}

=={{header|Nim}}==

{{trans|C++}}

 

func isSquareFree(n: uint64): bool =

counts.add powerfulcount(p, k)

p *= 10

 

{{out}}

=={{header|Perl}}==

===Generation===

use ntheory qw(is_square_free);

use experimental qw(signatures);

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);

{{out}}

<pre>

 

===Counting===

use ntheory qw(is_square_free);

use experimental qw(signatures);

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)));

{{out}}

<pre>

===priority queue===

Tried a slightly different approach, but it gets 7/10 at best on performance, and simply not worth attempting under pwa/p2js

<span style="color: #008080;">without</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Counts of %2d-powerful numbers &lt;= 10^(0..%d) : %v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">,</span><span style="color: #000000;">counts</span><span style="color: #0000FF;">})</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

{{out}}

<pre>

{{trans|Go}} {{trans|Sidef}}

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.

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>

{{out}}

<pre>

=={{header|Python}}==

Simple minded generation method.

import math

 

res = [kpowerful(k, 10**n) for n in range(k+10)]

print(f'{k}-powerful up to 10^{k+10}:',

{{out}}

<pre>14 2-powerfuls up to 10^2: 1 4 8 9 16 ... 49 64 72 81 100

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.

 

 

sub is-square-free (Int \n) {

printf "%2s-powerful numbers <= 10ⁿ (where 0 <= n <= %d): ", k, $top+k;

quietly say join ', ', [\+] powerfuls(10**($top + k), k);

{{out}}

<pre>Count and first and last five enumerated n-powerful numbers in 10ⁿ:

=={{header|Sidef}}==

===Generation===

 

var list = []

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)

{{out}}

<pre>

</pre>

===Counting===

 

var count = 0

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)

{{out}}

<pre>

{{libheader|Wren-sort}}

{{libheader|Wren-fmt}}

import "/set" for Set

import "/sort" for Sort

}

Fmt.print("Count of $2d-powerful numbers <= 10^j, j in [0, $d]: $n", k, k + 9, powCount)

 

{{out}}

=={{header|zkl}}==

{{trans|Go}}

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);

}(1,(2).pow(k)-1, n,k, powerful:=Dictionary());

powerful.keys.apply("toInt").sort();

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(" ")));

{{out}}

<pre>

{{trans|Perl}}

Overflows a 64 bit int at the very end, which results in a count of zero.

fcn(m,r, n,k,count){ // recursive closure

if(r<=k){ count.incN(iroot(n/m, r)); return() }

}(1,2*k - 1, n,k, count:=Ref(0));

count.value

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(" "));

{{out}}

<pre>