Achilles numbers: Difference between revisions
Content added Content deleted
(→Version 2 (Much faster): Another crazy speed-up by pre-computing perfect powers in advance.) |
SqrtNegInf (talk | contribs) (Added Perl) |
||
Line 294: | Line 294: | ||
100000:999999 664 |
100000:999999 664 |
||
</pre> |
</pre> |
||
=={{header|Perl}}== |
|||
Borrowed, and lightly modified, code from [[Powerful_numbers]] |
|||
{{libheader|ntheory}} |
|||
<lang perl>use strict; |
|||
use warnings; |
|||
use feature <say current_sub>; |
|||
use experimental 'signatures'; |
|||
use List::AllUtils <max head uniqint>; |
|||
use ntheory <is_square_free is_power euler_phi>; |
|||
use Math::AnyNum <:overload idiv iroot ipow is_coprime>; |
|||
sub table { my $t = shift() * (my $c = 1 + length max @_); ( sprintf( ('%'.$c.'d')x@_, @_) ) =~ s/.{1,$t}\K/\n/gr } |
|||
sub powerful_numbers ($n, $k = 2) { |
|||
my @powerful; |
|||
sub ($m, $r) { |
|||
$r < $k and push @powerful, $m and return; |
|||
for my $v (1 .. iroot(idiv($n, $m), $r)) { |
|||
if ($r > $k) { next unless is_square_free($v) and is_coprime($m, $v) } |
|||
__SUB__->($m * ipow($v, $r), $r - 1); |
|||
} |
|||
}->(1, 2*$k - 1); |
|||
sort { $a <=> $b } @powerful; |
|||
} |
|||
my(@P, @achilles, %Ahash, @strong); |
|||
@P = uniqint @P, powerful_numbers(10**9, $_) for 2..9; shift @P; |
|||
!is_power($_) and push @achilles, $_ and $Ahash{$_}++ for @P; |
|||
$Ahash{euler_phi $_} and push @strong, $_ for @achilles; |
|||
say "First 50 Achilles numbers:\n" . table 10, head 50, @achilles; |
|||
say "First 30 strong Achilles numbers:\n" . table 10, head 30, @strong; |
|||
say "Number of Achilles numbers with:\n"; |
|||
for my $l (2..9) { |
|||
my $c; $l == length and $c++ for @achilles; |
|||
say "$l digits: $c"; |
|||
}</lang> |
|||
{{out}} |
|||
<pre>First 50 Achilles numbers: |
|||
72 108 200 288 392 432 500 648 675 800 |
|||
864 968 972 1125 1152 1323 1352 1372 1568 1800 |
|||
1944 2000 2312 2592 2700 2888 3087 3200 3267 3456 |
|||
3528 3872 3888 4000 4232 4500 4563 4608 5000 5292 |
|||
5324 5400 5408 5488 6075 6125 6272 6728 6912 7200 |
|||
First 30 strong Achilles numbers: |
|||
500 864 1944 2000 2592 3456 5000 10125 10368 12348 |
|||
12500 16875 19652 19773 30375 31104 32000 33275 37044 40500 |
|||
49392 50000 52488 55296 61731 64827 67500 69984 78608 80000 |
|||
Number of Achilles numbers with: |
|||
2 digits: 1 |
|||
3 digits: 12 |
|||
4 digits: 47 |
|||
5 digits: 192 |
|||
6 digits: 664 |
|||
7 digits: 2242 |
|||
8 digits: 7395 |
|||
9 digits: 24008</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |