Achilles numbers: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (Automated syntax highlighting fixup (second round - minor fixes)) |
(Nim solution.) |
||
Line 2,157: | Line 2,157: | ||
6 664 |
6 664 |
||
7 2242</pre> |
7 2242</pre> |
||
=={{header|Nim}}== |
|||
{{trans|Wren}} |
|||
<syntaxhighlight lang="Nim">import std/[algorithm, sets, math, sequtils, strformat, strutils] |
|||
const MaxDigits = 15 |
|||
func getPerfectPowers(maxExp: int): HashSet[int] = |
|||
let upper = 10^maxExp |
|||
for i in 2..int(sqrt(upper.toFloat)): |
|||
var p = i |
|||
while p < upper div i: |
|||
p *= i |
|||
result.incl p |
|||
let pps = getPerfectPowers(MaxDigits) |
|||
proc getAchilles(minExp, maxExp: int): HashSet[int] = |
|||
let lower = 10^minExp |
|||
let upper = 10^maxExp |
|||
for b in 1..int(cbrt(upper.toFloat)): |
|||
let b3 = b * b * b |
|||
for a in 1..int(sqrt(upper.toFloat)): |
|||
let p = b3 * a * a |
|||
if p >= upper: break |
|||
if p >= lower: |
|||
if p notin pps: result.incl p |
|||
### Part 1 ### |
|||
let achillesSet = getAchilles(1, 6) |
|||
let achilles = sorted(achillesSet.toSeq) |
|||
echo "First 50 Achilles numbers:" |
|||
for i in 0..49: |
|||
let n = achilles[i] |
|||
stdout.write &"{n:>4}" |
|||
stdout.write if i mod 10 == 9: '\n' else: ' ' |
|||
### Part 2 ### |
|||
func totient(n: int): int = |
|||
var n = n |
|||
result = n |
|||
var i = 2 |
|||
while i * i <= n: |
|||
if n mod i == 0: |
|||
while n mod i == 0: |
|||
n = int(n / i) |
|||
result -= int(result / i) |
|||
if i == 2: i = 1 |
|||
inc i, 2 |
|||
if n > 1: |
|||
result -= int(result / n) |
|||
echo "\nFirst 50 strong Achilles numbers:" |
|||
var strongAchilles: seq[int] |
|||
var count = 0 |
|||
for n in achilles: |
|||
let tot = totient(n) |
|||
if tot in achillesSet: |
|||
strongAchilles.add n |
|||
inc count |
|||
if count == 50: break |
|||
for i, n in strongAchilles: |
|||
stdout.write &"{n:>6}" |
|||
stdout.write if i mod 10 == 9: '\n' else: ' ' |
|||
### Part 3 ### |
|||
echo "\nNumber of Achilles numbers with:" |
|||
for d in 2..MaxDigits: |
|||
let ac = getAchilles(d - 1, d).len |
|||
echo &"{d:>2} digits: {ac}" |
|||
</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 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 |
|||
6 digits: 664 |
|||
7 digits: 2242 |
|||
8 digits: 7395 |
|||
9 digits: 24008 |
|||
10 digits: 77330 |
|||
11 digits: 247449 |
|||
12 digits: 788855 |
|||
13 digits: 2508051 |
|||
14 digits: 7960336 |
|||
15 digits: 25235383 |
|||
</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |