Sequence: nth number with exactly n divisors: Difference between revisions
Content added Content deleted
Line 263: | Line 263: | ||
A073916(14) = 2752 |
A073916(14) = 2752 |
||
A073916(15) = 9801</pre> |
A073916(15) = 9801</pre> |
||
=={{header|D}}== |
|||
{{trans|Java}} |
|||
<lang d>import std.bigint; |
|||
import std.math; |
|||
import std.stdio; |
|||
bool isPrime(long test) { |
|||
if (test == 2) { |
|||
return true; |
|||
} |
|||
if (test % 2 == 0) { |
|||
return false; |
|||
} |
|||
for (long d = 3 ; d * d <= test; d += 2) { |
|||
if (test % d == 0) { |
|||
return false; |
|||
} |
|||
} |
|||
return true; |
|||
} |
|||
int[] calcSmallPrimes(int numPrimes) { |
|||
int[] smallPrimes; |
|||
smallPrimes ~= 2; |
|||
int count = 0; |
|||
int n = 3; |
|||
while (count < numPrimes) { |
|||
if (isPrime(n)) { |
|||
smallPrimes ~= n; |
|||
count++; |
|||
} |
|||
n += 2; |
|||
} |
|||
return smallPrimes; |
|||
} |
|||
immutable MAX = 45; |
|||
immutable smallPrimes = calcSmallPrimes(MAX); |
|||
int getDivisorCount(long n) { |
|||
int count = 1; |
|||
while (n % 2 == 0) { |
|||
n /= 2; |
|||
count += 1; |
|||
} |
|||
for (long d = 3; d * d <= n; d += 2) { |
|||
long q = n / d; |
|||
long r = n % d; |
|||
int dc = 0; |
|||
while (r == 0) { |
|||
dc += count; |
|||
n = q; |
|||
q = n / d; |
|||
r = n % d; |
|||
} |
|||
count += dc; |
|||
} |
|||
if (n != 1) { |
|||
count *= 2; |
|||
} |
|||
return count; |
|||
} |
|||
BigInt OEISA073916(int n) { |
|||
if (isPrime(n) ) { |
|||
return BigInt(smallPrimes[n-1]) ^^ (n - 1); |
|||
} |
|||
int count = 0; |
|||
int result = 0; |
|||
for (int i = 1; count < n; i++) { |
|||
if (n % 2 == 1) { |
|||
// The solution for an odd (non-prime) term is always a square number |
|||
int root = cast(int) sqrt(cast(real) i); |
|||
if (root * root != i) { |
|||
continue; |
|||
} |
|||
} |
|||
if (getDivisorCount(i) == n) { |
|||
count++; |
|||
result = i; |
|||
} |
|||
} |
|||
return BigInt(result); |
|||
} |
|||
void main() { |
|||
foreach (n; 1 .. MAX + 1) { |
|||
writeln("A073916(", n, ") = ", OEISA073916(n)); |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre>A073916(1) = 1 |
|||
A073916(2) = 3 |
|||
A073916(3) = 25 |
|||
A073916(4) = 14 |
|||
A073916(5) = 14641 |
|||
A073916(6) = 44 |
|||
A073916(7) = 24137569 |
|||
A073916(8) = 70 |
|||
A073916(9) = 1089 |
|||
A073916(10) = 405 |
|||
A073916(11) = 819628286980801 |
|||
A073916(12) = 160 |
|||
A073916(13) = 22563490300366186081 |
|||
A073916(14) = 2752 |
|||
A073916(15) = 9801 |
|||
A073916(16) = 462 |
|||
A073916(17) = 21559177407076402401757871041 |
|||
A073916(18) = 1044 |
|||
A073916(19) = 740195513856780056217081017732809 |
|||
A073916(20) = 1520 |
|||
A073916(21) = 141376 |
|||
A073916(22) = 84992 |
|||
A073916(23) = 1658509762573818415340429240403156732495289 |
|||
A073916(24) = 1170 |
|||
A073916(25) = 52200625 |
|||
A073916(26) = 421888 |
|||
A073916(27) = 52900 |
|||
A073916(28) = 9152 |
|||
A073916(29) = 1116713952456127112240969687448211536647543601817400964721 |
|||
A073916(30) = 6768 |
|||
A073916(31) = 1300503809464370725741704158412711229899345159119325157292552449 |
|||
A073916(32) = 3990 |
|||
A073916(33) = 12166144 |
|||
A073916(34) = 9764864 |
|||
A073916(35) = 446265625 |
|||
A073916(36) = 5472 |
|||
A073916(37) = 11282036144040442334289838466416927162302790252609308623697164994458730076798801 |
|||
A073916(38) = 43778048 |
|||
A073916(39) = 90935296 |
|||
A073916(40) = 10416 |
|||
A073916(41) = 1300532588674810624476094551095787816112173600565095470117230812218524514342511947837104801 |
|||
A073916(42) = 46400 |
|||
A073916(43) = 635918448514386699807643535977466343285944704172890141356181792680152445568879925105775366910081 |
|||
A073916(44) = 240640 |
|||
A073916(45) = 327184</pre> |
|||
=={{header|Factor}}== |
=={{header|Factor}}== |