Achilles numbers: Difference between revisions
Content added Content deleted
(→{{header|RPL}}: Faster version) |
(New post.) |
||
Line 2,181: | Line 2,181: | ||
<tt>(#~ predicate) list</tt> selects the elements of <tt>list</tt> where <tt>predicate</tt> is true. |
<tt>(#~ predicate) list</tt> selects the elements of <tt>list</tt> where <tt>predicate</tt> is true. |
||
=={{header|Java}}== |
|||
<syntaxhighlight lang="java"> |
|||
import java.util.ArrayList; |
|||
import java.util.List; |
|||
import java.util.Set; |
|||
import java.util.TreeSet; |
|||
import java.util.stream.Collectors; |
|||
import java.util.stream.IntStream; |
|||
public final class AchlllesNumbers { |
|||
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); |
|||
System.out.println("First 50 Achilles numbers:"); |
|||
for ( int i = 0; i < 50; i++ ) { |
|||
System.out.print(String.format("%4d%s", achilles.get(i), ( ( i + 1 ) % 10 == 0 ) ? "\n" : " ")); |
|||
} |
|||
System.out.println(); |
|||
System.out.println("First 50 strong Achilles numbers:"); |
|||
for ( int i = 0, count = 0; count < 50; i++ ) { |
|||
if ( achilles.contains(totients.get(achilles.get(i))) ) { |
|||
System.out.print(String.format("%6d%s", achilles.get(i), ( ++count % 10 == 0 ) ? "\n" : " ")); |
|||
} |
|||
} |
|||
System.out.println(); |
|||
System.out.println("Number of Achilles numbers with:"); |
|||
for ( int i = 100; i < 1_000_000; i *= 10 ) { |
|||
final int digits = String.valueOf(i).length() - 1; |
|||
System.out.println(" " + digits + " digits: " + achilles(i / 10, i - 1, perfectPowers).size()); |
|||
} |
|||
} |
|||
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; |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{ out }} |
|||
<pre> |
|||
irst 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 50 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 |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |