Anonymous user
Sequence: nth number with exactly n divisors: Difference between revisions
Sequence: nth number with exactly n divisors (view source)
Revision as of 22:36, 5 April 2021
, 3 years ago→{{header|Nim}}
m (→{{header|REXX}}: moved a function.) |
|||
Line 801:
33 : 12166144
</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}}==
| |||