Sequence: nth number with exactly n divisors: Difference between revisions
Sequence: nth number with exactly n divisors (view source)
Revision as of 11:36, 4 February 2024
, 3 months ago→{{header|Wren}}: Minor tidy
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
m (→{{header|Wren}}: Minor tidy) |
||
| (2 intermediate revisions by one other user not shown) | |||
Line 14:
:*[[Sequence: smallest number greater than previous term with exactly n divisors]]
:*[[Sequence: smallest number with exactly n divisors]]
<br/><br/>
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
Uses Algol 68G's LONG LONG INT (with default precision) to handle the large numbers.<br/>
Builds a table of proper divisor counts for testing non-prime n (As with other samples uses the fact that for prime n, the required number is the nth prime to the power n - 1.<br/>
Using a table is practical for smallish n, (a table of 500 000 elements is used here, big enough for up to n = 24. For n = 25, a table of over 52 000 000 would be required.<br/>
For non-prime n, the divisors are also shown.
<syntaxhighlight lang="algol68">
BEGIN
INT max number = 500 000; # maximum number we will count the divisors of #
# form a table of proper divisor counts #
[ 1 : max number ]INT pdc; FOR i TO UPB pdc DO pdc[ i ] := 1 OD;
pdc[ 1 ] := 0;
FOR i FROM 2 TO UPB pdc DO
FOR j FROM i + i BY i TO UPB pdc DO pdc[ j ] +:= 1 OD
OD;
# find the first few primes #
[ 1 : 30 ]INT prime;
INT p count := 0;
FOR i WHILE p count < UPB prime DO
IF pdc[ i ] = 1 THEN prime[ p count +:= 1 ] := i FI
OD;
# show the nth number with n divisors #
INT w = -43; # width to print the numbers (negative means no leading +) #
print( ( " 1: ", whole( 1, w ), " | 1", newline ) );
FOR i FROM 2 TO 23 DO
print( ( whole( i, -2 ), ": " ) );
IF pdc( i ) = 1 THEN
print( ( whole( LENG LENG prime[ i ] ^ ( i - 1 ), w ), newline ) )
ELSE
INT c := 0;
FOR j TO UPB pdc WHILE c < i DO
IF pdc[ j ] = i - 1 THEN
c +:= 1;
IF c = i THEN
print( ( whole( j, w ), " | 1" ) );
FOR d FROM 2 TO j OVER 2 DO
IF j MOD d = 0 THEN print( ( " ", whole( d, 0 ) ) ) FI
OD;
print( ( " ", whole( j, 0 ), newline ) )
FI
FI
OD
FI
OD
END
</syntaxhighlight>
{{out}}
<pre style="font-size: 12px">
1: 1 | 1
2: 3
3: 25
4: 14 | 1 2 7 14
5: 14641
6: 44 | 1 2 4 11 22 44
7: 24137569
8: 70 | 1 2 5 7 10 14 35 70
9: 1089 | 1 3 9 11 33 99 121 363 1089
10: 405 | 1 3 5 9 15 27 45 81 135 405
11: 819628286980801
12: 160 | 1 2 4 5 8 10 16 20 32 40 80 160
13: 22563490300366186081
14: 2752 | 1 2 4 8 16 32 43 64 86 172 344 688 1376 2752
15: 9801 | 1 3 9 11 27 33 81 99 121 297 363 891 1089 3267 9801
16: 462 | 1 2 3 6 7 11 14 21 22 33 42 66 77 154 231 462
17: 21559177407076402401757871041
18: 1044 | 1 2 3 4 6 9 12 18 29 36 58 87 116 174 261 348 522 1044
19: 740195513856780056217081017732809
20: 1520 | 1 2 4 5 8 10 16 19 20 38 40 76 80 95 152 190 304 380 760 1520
21: 141376 | 1 2 4 8 16 32 47 64 94 188 376 752 1504 2209 3008 4418 8836 17672 35344 70688 141376
22: 84992 | 1 2 4 8 16 32 64 83 128 166 256 332 512 664 1024 1328 2656 5312 10624 21248 42496 84992
23: 1658509762573818415340429240403156732495289</pre>
=={{header|C}}==
Line 2,284 ⟶ 2,359:
{{libheader|Wren-big}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./big" for BigInt
import "./fmt" for Fmt
var MAX = 33
| |||