Rosetta Code

Achilles numbers: Difference between revisions

Page Discussion

Achilles numbers (view source)

Revision as of 19:53, 19 April 2024

8,031 bytes added ,  27 days ago
→‎{{header|jq}}
(Added Quackery.)
 
(9 intermediate revisions by 5 users not shown)
Line 1,563:
Numbers with 6 digits : 664
</pre>
 
=={{header|BASIC256}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang="vb">function GCD(n, d)
if(d = 0) then return n else return GCD(d, n % d)
end function
 
function Totient(n)
tot = 0
for m = 1 to n
if GCD(m, n) = 1 then tot += 1
next m
return tot
end function
 
function isPowerful(m)
n = m
f = 2
l = sqr(m)
 
if m <= 1 then return false
while true
q = n/f
if (n % f) = 0 then
if (m %(f*f)) then return false
n = q
if f > n then exit while
else
f += 1
if f > l then
if (m % (n*n)) then return false
exit while
end if
end if
end while
return true
end function
 
function isAchilles(n)
if not isPowerful(n) then return false
m = 2
a = m*m
do
do
if a = n then return false
a *= m
until a > n
m += 1
a = m*m
until a > n
return true
end function
 
print "First 50 Achilles numbers:"
num = 0
n = 1
do
if isAchilles(n) then
print rjust(n, 5);
num += 1
if (num % 10) <> 0 then print " "; else print
end if
n += 1
until num >= 50
 
print : print
print "First 20 strong Achilles numbers:"
num = 0
n = 1
do
if isAchilles(n) and isAchilles(Totient(n)) then
print rjust(n, 5);
num += 1
if (num % 10) <> 0 then print " "; else print
end if
n += 1
until num >= 20
 
print : print
print "Number of Achilles numbers with:"
for i = 2 to 6
inicio = fix(10.0 ^ (i-1))
num = 0
for n = inicio to inicio*10-1
if isAchilles(n) then num += 1
next n
print i; " digits:"; num
next i</syntaxhighlight>
 
 
 
[[https://dotnetfiddle.net/TCD2WC You may run it online!]]
 
=={{header|C++}}==
{{trans|Wren}}
Line 1,829 ⟶ 1,922:
</pre>
 
 
=={{header|EasyLang}}==
{{trans|BASIC256}}
<syntaxhighlight>
func gcd n d .
if d = 0
return n
.
return gcd d (n mod d)
.
func totient n .
for m = 1 to n
if gcd m n = 1
tot += 1
.
.
return tot
.
func isPowerful m .
n = m
f = 2
l = sqrt m
if m <= 1
return 0
.
while 1 = 1
q = n div f
if n mod f = 0
if m mod (f * f) <> 0
return 0
.
n = q
if f > n
return 1
.
else
f += 1
if f > l
if m mod (n * n) <> 0
return 0
.
return 1
.
.
.
.
func isAchilles n .
if isPowerful n = 0
return 0
.
m = 2
a = m * m
repeat
repeat
if a = n
return 0
.
a *= m
until a > n
.
m += 1
a = m * m
until a > n
.
return 1
.
print "First 50 Achilles numbers:"
n = 1
repeat
if isAchilles n = 1
write n & " "
num += 1
.
n += 1
until num >= 50
.
print ""
print ""
print "First 20 strong Achilles numbers:"
num = 0
n = 1
repeat
if isAchilles n = 1 and isAchilles totient n = 1
write n & " "
num += 1
.
n += 1
until num >= 20
.
print ""
print ""
print "Number of Achilles numbers with 2 to 5 digits:"
a = 10
b = 100
for i = 2 to 5
num = 0
for n = a to b - 1
if isAchilles n = 1
num += 1
.
.
write num & " "
a = b
b *= 10
.
</syntaxhighlight>
 
{{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 20 strong Achilles numbers:
500 864 1944 2000 2592 3456 5000 10125 10368 12348 12500 16875 19652 19773 30375 31104 32000 33275 37044 40500
 
Number of Achilles numbers with 2 to 5 digits:
1 12 47 192
</pre>
 
=={{header|Factor}}==
Line 2,184 ⟶ 2,395:
=={{header|Java}}==
<syntaxhighlight lang="java">
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.SetMap;
import java.util.TreeSet;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
 
public final class AchlllesNumbersAchillesNumbers {
 
private Map<Integer, Boolean> pps = new HashMap<>();
public static void main(String[] aArgs) {
Set<Integer> perfectPowers = perfectPowers(500_000);
List<Integer> achilles = achilles(1, 250_000, perfectPowers);
List<Integer> totients = totients(250_000);
 
public int totient(int n) {
System.out.println("First 50 Achilles numbers:");
for ( int itot = 0n; i < 50; i++ ) {
int i = 2;
System.out.print(String.format("%4d%s", achilles.get(i), ( ( i + 1 ) % 10 == 0 ) ? "\n" : " "));
while (i * i <= n) {
}
if (n % i == 0) {
System.out.println();
while (n % i == 0) {
n /= i;
System.out.println("First 50 strong Achilles numbers:");
for ( int i = 0, count = 0; count < 50; i++ ) {}
tot -= tot / i;
if ( achilles.contains(totients.get(achilles.get(i))) ) {
}
System.out.print(String.format("%6d%s", achilles.get(i), ( ++count % 10 == 0 ) ? "\n" : " "));
if (i == 2) {
}
i = 1;
}
}
System.out.println();
i += 2;
}
System.out.println("Number of Achilles numbers with:");
for ( int i =if 100; i < 1_000_000; i *=(n 10> 1) {
tot -= tot / n;
final int digits = String.valueOf(i).length() - 1;
}
System.out.println(" " + digits + " digits: " + achilles(i / 10, i - 1, perfectPowers).size());
return tot;
}
}
}
private static List<Integer> achilles(int aFrom, int aTo, Set<Integer> aPerfectPowers) {
Set<Integer> result = new TreeSet<Integer>();
final int cubeRoot = (int) Math.cbrt(aTo / 4);
final int squareRoot = (int) Math.sqrt(aTo / 8);
for ( int b = 2; b <= cubeRoot; b++ ) {
final int bCubed = b * b * b;
for ( int a = 2; a <= squareRoot; a++ ) {
int achilles = bCubed * a * a;
if ( achilles >= aTo ) {
break;
}
if ( achilles >= aFrom && ! aPerfectPowers.contains(achilles) ) {
result.add(achilles);
}
}
}
return new ArrayList<Integer>(result);
}
private static Set<Integer> perfectPowers(int aN) {
Set<Integer> result = new TreeSet<Integer>();
for ( int i = 2, root = (int) Math.sqrt(aN); i <= root; i++ ) {
for ( int perfect = i * i; perfect < aN; perfect *= i ) {
result.add(perfect);
}
}
return result;
}
private static List<Integer> totients(int aN) {
List<Integer> result = IntStream.rangeClosed(0, aN).boxed().collect(Collectors.toList());;
for ( int i = 2; i <= aN; i++ ) {
if ( result.get(i) == i ) {
result.set(i, i - 1);
for ( int j = i * 2; j <= aN; j = j + i ) {
result.set(j, ( result.get(j) / i ) * ( i - 1 ));
}
}
}
return result;
}
 
public void getPerfectPowers(int maxExp) {
double upper = Math.pow(10, maxExp);
for (int i = 2; i <= Math.sqrt(upper); i++) {
double fi = i;
double p = fi;
while (true) {
p *= fi;
if (p >= upper) {
break;
}
pps.put((int) p, true);
}
}
}
 
public Map<Integer, Boolean> getAchilles(int minExp, int maxExp) {
double lower = Math.pow(10, minExp);
double upper = Math.pow(10, maxExp);
Map<Integer, Boolean> achilles = new HashMap<>();
for (int b = 1; b <= (int) Math.cbrt(upper); b++) {
int b3 = b * b * b;
for (int a = 1; a <= (int) Math.sqrt(upper); a++) {
int p = b3 * a * a;
if (p >= (int) upper) {
break;
}
if (p >= (int) lower) {
if (!pps.containsKey(p)) {
achilles.put(p, true);
}
}
}
}
return achilles;
}
 
public static void main(String[] args) {
AchillesNumbers an = new AchillesNumbers();
 
int maxDigits = 8;
an.getPerfectPowers(maxDigits);
Map<Integer, Boolean> achillesSet = an.getAchilles(1, 5);
List<Integer> achilles = new ArrayList<>(achillesSet.keySet());
Collections.sort(achilles);
 
System.out.println("First 50 Achilles numbers:");
for (int i = 0; i < 50; i++) {
System.out.printf("%4d ", achilles.get(i));
if ((i + 1) % 10 == 0) {
System.out.println();
}
}
 
System.out.println("\nFirst 30 strong Achilles numbers:");
List<Integer> strongAchilles = new ArrayList<>();
int count = 0;
for (int n = 0; count < 30; n++) {
int tot = an.totient(achilles.get(n));
if (achillesSet.containsKey(tot)) {
strongAchilles.add(achilles.get(n));
count++;
}
}
for (int i = 0; i < 30; i++) {
System.out.printf("%5d ", strongAchilles.get(i));
if ((i + 1) % 10 == 0) {
System.out.println();
}
}
 
System.out.println("\nNumber of Achilles numbers with:");
for (int d = 2; d <= maxDigits; d++) {
int ac = an.getAchilles(d - 1, d).size();
System.out.printf("%2d digits: %d\n", d, ac);
}
}
}
</syntaxhighlight>
Line 2,267 ⟶ 2,507:
<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 5030 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
81000 83349 84375 93312 108000 111132 124416 128000 135000 148176
151875 158184 162000 165888 172872 177957 197568 200000 202612 209952
 
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
 
</pre>
 
=={{header|jq}}==
'''Adapted from the "fast" [[#Wren|Wren]] entry'''
 
'''Works with jq, the C implementation of jq'''
 
'''Works with gojq, the Go implementation of jq'''
 
`nwise` is included below because, as of this writing, gojq does not include `_nwise`.
<syntaxhighlight lang="jq">
# Require $n > 0
def nwise($n):
def _n: if length <= $n then . else .[:$n] , (.[$n:] | _n) end;
if $n <= 0 then "nwise: argument should be non-negative" else _n end;
 
### Part 1 - generic functions
 
# Ensure $x is in the input sorted array
def ensure($x):
bsearch($x) as $i
| if $i >= 0 then .
else (-1-$i) as $i
| .[:$i] + [$x] + .[$i:]
end ;
 
def lpad($len): tostring | ($len - length) as $l | (" " * $l) + .;
 
def table($wide; $pad):
nwise($wide) | map(lpad($pad)) | join(" ");
 
def count(s): reduce s as $x (0; .+1);
 
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in);
 
# jq optimizes the recursive call of _gcd in the following:
def gcd($a;$b):
def _gcd:
if .[1] != 0 then [.[1], .[0] % .[1]] | _gcd else .[0] end;
[$a,$b] | _gcd ;
 
def totient:
. as $n
| count( range(0; .) | select( gcd($n; .) == 1) );
 
# Emit a sorted array
def getPerfectPowers( $maxExp ):
(10 | power($maxExp)) as $upper
| reduce range( 2; 1 + ($upper|sqrt|floor)) as $i ({pps: []};
.p = $i * $i
| until (.p >= $upper;
.pps += [ .p ]
| .p *= $i) )
| .pps
| sort;
 
# Input: a sufficiently long array of perfect powers in order
def getAchilles($minExp; $maxExp):
def cbrt: pow(.; 1/3);
. as $pps
| (10 | power($minExp)) as $lower
| (10 | power($maxExp)) as $upper
| ($upper | sqrt | floor) as $sqrtupper
| reduce range(1; 1 + ($upper|cbrt|floor)) as $b ({achilles: []};
($b | .*.*.) as $b3
| .done = false
| .a = 1
| until(.done or (.a > $sqrtupper);
($b3 * .a * .a) as $p
| if $p >= $upper then .done = true
elif $p >= $lower and ($pps | bsearch($p) < 0)
then .achilles |= ensure($p)
end
| .a += 1 ) )
| .achilles;
 
def task($maxDigits):
getPerfectPowers($maxDigits)
| . as $perfectPowers
| getAchilles(1; 5)
| . as $achilles
| "First 50 Achilles numbers:",
(.[:50] | table(10;5)),
"\nFirst 30 strong Achilles numbers:",
({ strongAchilles:[], count:0, n:0 }
| until (.count >= 30;
$achilles[.n] as $a
| ($a | totient) as $tot
| if ($achilles | bsearch($tot)) >= 0
then .strongAchilles |= ensure($a)
| .count += 1
end
| .n += 1 )
| (.strongAchilles | table(10;5) ),
"\nNumber of Achilles numbers with:",
( range(2; 1+$maxDigits) as $d
| ($perfectPowers|getAchilles($d-1; $d)|length) as $ac
| "\($d) digits: \($ac)" ) )
;
 
task(10)
</syntaxhighlight>
{{output}}
<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
10 digits: 77330
</pre>
 
Line 2,515 ⟶ 2,883:
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 is_power 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) {
Line 2,529 ⟶ 2,897:
__SUB__->($m * ipow($v, $r), $r - 1);
}
}->(1, 2 * $k - 1);
sort { $a <=> $b } @powerful;
}
 
my(@P, (@achilles, %Ahash, @strong);
my @P = uniqint @P, powerful_numbers(10**9, $_2) 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, . 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) {
for my $c; $l ==(2 length.. and $c++ for9) @achilles;{
my $c;
$l == length and $c++ for @achilles;
say "$l digits: $c";
}</syntaxhighlight>
Line 3,184 ⟶ 3,554:
 
Elapsed time: 12608 milliseconds
</pre>
 
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">var P = 2.powerful(1e9)
var achilles = Set(P.grep{ !.is_power }...)
var strong_achilles = achilles.grep { achilles.has(.phi) }
 
say "First 50 Achilles numbers:"
achilles.sort.first(50).slices(10).each { .map{'%4s'%_}.join(' ').say }
 
say "\nFirst 30 strong Achilles numbers:"
strong_achilles.sort.first(30).slices(10).each { .map{'%5s'%_}.join(' ').say }
 
say "\nNumber of Achilles numbers with:"
achilles.to_a.group_by{.len}.sort_by{|k| k.to_i }.each_2d{|a,b|
say "#{a} digits: #{b.len}"
}</syntaxhighlight>
 
{{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>
 
Line 3,192 ⟶ 3,603:
===Version 1 (Brute force)===
This finds the number of 6 digit Achilles numbers in 2.5 seconds, 7 digits in 51 seconds but 8 digits needs a whopping 21 minutes!
<syntaxhighlight lang="ecmascriptwren">import "./math" for Int
import "./seq" for Lst
import "./fmt" for Fmt
Line 3,199 ⟶ 3,610:
var limit = 10.pow(maxDigits)
var c = Int.primeSieve(limit-1, false)
 
var totient = Fn.new { |n|
var tot = n
var i = 2
while (i*i <= n) {
if (n%i == 0) {
while(n%i == 0) n = (n/i).floor
tot = tot - (tot/i).floor
}
if (i == 2) i = 1
i = i + 2
}
if (n > 1) tot = tot - (tot/n).floor
return tot
}
 
var isPerfectPower = Fn.new { |n|
Line 3,257 ⟶ 3,653:
var isStrongAchilles = Fn.new { |n|
if (!isAchilles.call(n)) return false
var tot = totientInt.calltotient(n)
return isAchilles.call(tot)
}
Line 3,272 ⟶ 3,668:
n = n + 1
}
Fmt.tprint("$4d", achilles, 10)
for (chunk in Lst.chunks(achilles, 10)) Fmt.print("$4d", chunk)
 
System.print("\nFirst 30 strong Achilles numbers:")
Line 3,285 ⟶ 3,681:
n = n + 1
}
Fmt.tprint("$5d", strongAchilles, 10)
for (chunk in Lst.chunks(strongAchilles, 10)) Fmt.print("$5d", chunk)
 
System.print("\nNumber of Achilles numbers with:")
Line 3,326 ⟶ 3,722:
 
Ridiculously fast compared to the previous method: 12 digits can now be reached in 1.03 seconds, 13 digits in 3.7 seconds, 14 digits in 12.2 seconds and 15 digits in 69 seconds.
<syntaxhighlight lang="ecmascriptwren">import "./set" for Set
import "./seq" for Lst
import "./math" for Int
import "./fmt" for Fmt
 
var totient = Fn.new { |n|
var tot = n
var i = 2
while (i*i <= n) {
if (n%i == 0) {
while(n%i == 0) n = (n/i).floor
tot = tot - (tot/i).floor
}
if (i == 2) i = 1
i = i + 2
}
if (n > 1) tot = tot - (tot/n).floor
return tot
}
 
var pps = Set.new()
Line 3,380 ⟶ 3,762:
 
System.print("First 50 Achilles numbers:")
Fmt.tprint("$4d", achilles.take(50), 10)
for (chunk in Lst.chunks(achilles[0..49], 10)) Fmt.print("$4d", chunk)
 
System.print("\nFirst 30 strong Achilles numbers:")
Line 3,387 ⟶ 3,769:
var n = 0
while (count < 30) {
var tot = totientInt.calltotient(achilles[n])
if (achillesSet.contains(tot)) {
strongAchilles.add(achilles[n])
Line 3,394 ⟶ 3,776:
n = n + 1
}
Fmt.tprint("$5d", strongAchilles, 10)
for (chunk in Lst.chunks(strongAchilles, 10)) Fmt.print("$5d", chunk)
 
System.print("\nNumber of Achilles numbers with:")
Peak
2,442

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/355503...363802"