Sequence: nth number with exactly n divisors: Difference between revisions
Content added Content deleted
m (→{{header|REXX}}: moved a function.) |
|||
Line 801: | Line 801: | ||
33 : 12166144 |
33 : 12166144 |
||
</pre> |
</pre> |
||
=={{header|Nim}}== |
|||
{{trans|Go}} |
|||
{{libheader|bignum}} |
|||
This is a translation of the fast Go version. It runs in about 23s on our laptop. |
|||
<lang Nim>import math, strformat |
|||
import bignum |
|||
type Record = tuple[num, count: Natural] |
|||
template isOdd(n: Natural): bool = |
|||
(n and 1) != 0 |
|||
func isPrime(n: int): bool = |
|||
let bi = newInt(n) |
|||
result = bi.probablyPrime(25) != 0 |
|||
proc findPrimes(limit: Natural): seq[int] {.compileTime.} = |
|||
result = @[2] |
|||
var isComposite = newSeq[bool](limit + 1) |
|||
var p = 3 |
|||
while true: |
|||
let p2 = p * p |
|||
if p2 > limit: break |
|||
for i in countup(p2, limit, 2 * p): |
|||
isComposite[i] = true |
|||
while true: |
|||
inc p, 2 |
|||
if not isComposite[p]: break |
|||
for n in countup(3, limit, 2): |
|||
if not isComposite[n]: |
|||
result.add n |
|||
const Primes = findPrimes(22_000) |
|||
proc countDivisors(n: Natural): int = |
|||
result = 1 |
|||
var n = n |
|||
for i, p in Primes: |
|||
if p * p > n: break |
|||
if n mod p != 0: continue |
|||
n = n div p |
|||
var count = 1 |
|||
while n mod p == 0: |
|||
n = n div p |
|||
inc count |
|||
result *= count + 1 |
|||
if n == 1: return |
|||
if n != 1: result *= 2 |
|||
const Max = 45 |
|||
var records: array[0..Max, Record] |
|||
echo &"The first {Max} terms in the sequence are:" |
|||
for n in 1..Max: |
|||
if n.isPrime: |
|||
var z = newInt(Primes[n - 1]) |
|||
z = pow(z, culong(n - 1)) |
|||
echo &"{n:2}: {z}" |
|||
else: |
|||
var count = records[n].count |
|||
if count == n: |
|||
echo &"{n:2}: {records[n].num}" |
|||
continue |
|||
let odd = n.isOdd |
|||
let d = if odd or n == 2 or n == 10: 1 else: 2 |
|||
var k = records[n].num |
|||
while true: |
|||
inc k, d |
|||
if odd: |
|||
let sq = sqrt(k.toFloat).int |
|||
if sq * sq != k: continue |
|||
let cd = k.countDivisors() |
|||
if cd == n: |
|||
inc count |
|||
if count == n: |
|||
echo &"{n:2}: {k}" |
|||
break |
|||
elif cd in (n + 1)..Max and records[cd].count < cd and |
|||
k > records[cd].num and (d == 1 or d == 2 and not cd.isOdd): |
|||
records[cd].num = k |
|||
inc records[cd].count</lang> |
|||
{{out}} |
|||
<pre>The first 45 terms in the sequence are: |
|||
1: 1 |
|||
2: 3 |
|||
3: 25 |
|||
4: 14 |
|||
5: 14641 |
|||
6: 44 |
|||
7: 24137569 |
|||
8: 70 |
|||
9: 1089 |
|||
10: 405 |
|||
11: 819628286980801 |
|||
12: 160 |
|||
13: 22563490300366186081 |
|||
14: 2752 |
|||
15: 9801 |
|||
16: 462 |
|||
17: 21559177407076402401757871041 |
|||
18: 1044 |
|||
19: 740195513856780056217081017732809 |
|||
20: 1520 |
|||
21: 141376 |
|||
22: 84992 |
|||
23: 1658509762573818415340429240403156732495289 |
|||
24: 1170 |
|||
25: 52200625 |
|||
26: 421888 |
|||
27: 52900 |
|||
28: 9152 |
|||
29: 1116713952456127112240969687448211536647543601817400964721 |
|||
30: 6768 |
|||
31: 1300503809464370725741704158412711229899345159119325157292552449 |
|||
32: 3990 |
|||
33: 12166144 |
|||
34: 9764864 |
|||
35: 446265625 |
|||
36: 5472 |
|||
37: 11282036144040442334289838466416927162302790252609308623697164994458730076798801 |
|||
38: 43778048 |
|||
39: 90935296 |
|||
40: 10416 |
|||
41: 1300532588674810624476094551095787816112173600565095470117230812218524514342511947837104801 |
|||
42: 46400 |
|||
43: 635918448514386699807643535977466343285944704172890141356181792680152445568879925105775366910081 |
|||
44: 240640 |
|||
45: 327184</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |