Stirling numbers of the first kind: Difference between revisions
m (→{{header|REXX}}: used a smaller font size for an output section.) |
(→{{header|RPL}}: typo) |
||
(28 intermediate revisions by 15 users not shown) | |||
Line 48: | Line 48: | ||
<br><br> |
<br><br> |
||
=={{header|11l}}== |
|||
{{trans|Python}} |
|||
<syntaxhighlight lang="11l">[(Int, Int) = BigInt] computed |
|||
F sterling1(n, k) |
|||
V key = (n, k) |
|||
I key C :computed |
|||
R :computed[key] |
|||
I n == k == 0 |
|||
R BigInt(1) |
|||
I n > 0 & k == 0 |
|||
R BigInt(0) |
|||
I k > n |
|||
R BigInt(0) |
|||
V result = sterling1(n - 1, k - 1) + (n - 1) * sterling1(n - 1, k) |
|||
:computed[key] = result |
|||
R result |
|||
print(‘Unsigned Stirling numbers of the first kind:’) |
|||
V MAX = 12 |
|||
print(‘n/k’.ljust(10), end' ‘’) |
|||
L(n) 0 .. MAX |
|||
print(String(n).rjust(10), end' ‘’) |
|||
print() |
|||
L(n) 0 .. MAX |
|||
print(String(n).ljust(10), end' ‘’) |
|||
L(k) 0 .. n |
|||
print(String(sterling1(n, k)).rjust(10), end' ‘’) |
|||
print() |
|||
print(‘The maximum value of S1(100, k) = ’) |
|||
BigInt previous = 0 |
|||
L(k) 1 .. 100 |
|||
V current = sterling1(100, k) |
|||
I current > previous |
|||
previous = current |
|||
E |
|||
print("#.\n(#. digits, k = #.)\n".format(previous, String(previous).len, k - 1)) |
|||
L.break</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Unsigned Stirling numbers of the first kind: |
|||
n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 |
|||
0 1 |
|||
1 0 1 |
|||
2 0 1 1 |
|||
3 0 2 3 1 |
|||
4 0 6 11 6 1 |
|||
5 0 24 50 35 10 1 |
|||
6 0 120 274 225 85 15 1 |
|||
7 0 720 1764 1624 735 175 21 1 |
|||
8 0 5040 13068 13132 6769 1960 322 28 1 |
|||
9 0 40320 109584 118124 67284 22449 4536 546 36 1 |
|||
10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 |
|||
11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 |
|||
12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 |
|||
The maximum value of S1(100, k) = |
|||
19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 |
|||
(158 digits, k = 5) |
|||
</pre> |
|||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}} |
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}} |
||
Uses the Algol 68G LONG LONG INT mode which provides large-precision integers. As the default number of digits is insufficient for the task, the maximum nunber of digits is specified by a pragmatic comment. |
Uses the Algol 68G LONG LONG INT mode which provides large-precision integers. As the default number of digits is insufficient for the task, the maximum nunber of digits is specified by a pragmatic comment. |
||
< |
<syntaxhighlight lang="algol68"> |
||
BEGIN # show some (unsigned) Stirling numbers of the first kind # |
|||
# specify the precision of LONG LONG INT, we need about 160 digits # |
# specify the precision of LONG LONG INT, we need about 160 digits # |
||
Line 82: | Line 145: | ||
REF[,]SINT s1 = make s1( max stirling, FALSE ); |
REF[,]SINT s1 = make s1( max stirling, FALSE ); |
||
print( ( "Unsigned Stirling numbers of the first kind:", newline ) ); |
print( ( "Unsigned Stirling numbers of the first kind:", newline ) ); |
||
print( ( " k" ) ); |
print( ( " k 0" ) ); |
||
FOR k |
FOR k TO max stirling DO print( ( whole( k, IF k < 6 THEN -10 ELSE -9 FI ) ) ) OD; |
||
print( ( newline, " n", newline ) ); |
print( ( newline, " n", newline ) ); |
||
FOR n FROM 0 TO max stirling DO |
FOR n FROM 0 TO max stirling DO |
||
print( ( whole( n, -2 ) ) ); |
print( ( whole( n, -2 ), whole( s1[ n, 0 ], -3 ) ) ); |
||
FOR k |
FOR k TO n DO |
||
print( ( whole( s1[ n, k ], -10 ) ) ) |
print( ( whole( s1[ n, k ], IF k < 6 THEN -10 ELSE -9 FI ) ) ) |
||
OD; |
OD; |
||
print( ( newline ) ) |
print( ( newline ) ) |
||
Line 104: | Line 167: | ||
print( ( whole( max 100, 0 ), newline ) ) |
print( ( whole( max 100, 0 ), newline ) ) |
||
END |
END |
||
END |
END |
||
</syntaxhighlight> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Unsigned Stirling numbers of the first kind: |
Unsigned Stirling numbers of the first kind: |
||
k |
k 0 1 2 3 4 5 6 7 8 9 10 11 12 |
||
n |
n |
||
0 |
0 1 |
||
1 |
1 0 1 |
||
2 |
2 0 1 1 |
||
3 |
3 0 2 3 1 |
||
4 |
4 0 6 11 6 1 |
||
5 |
5 0 24 50 35 10 1 |
||
6 |
6 0 120 274 225 85 15 1 |
||
7 |
7 0 720 1764 1624 735 175 21 1 |
||
8 |
8 0 5040 13068 13132 6769 1960 322 28 1 |
||
9 |
9 0 40320 109584 118124 67284 22449 4536 546 36 1 |
||
10 |
10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 |
||
11 |
11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 |
||
12 |
12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 |
||
Maximum Stirling number of the first kind with n = 100: |
Maximum Stirling number of the first kind with n = 100: |
||
19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 |
19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 |
||
</pre> |
|||
=={{header|ALGOL W}}== |
|||
<syntaxhighlight lang="algolw"> |
|||
begin % show some (unsigned) Stirling numbers of the first kind % |
|||
integer MAX_STIRLING; |
|||
MAX_STIRLING := 12; |
|||
begin |
|||
% construct a matrix of Stirling numbers up to max n, max n % |
|||
integer array s1 ( 0 :: MAX_STIRLING, 0 :: MAX_STIRLING ); |
|||
for n := 0 until MAX_STIRLING do begin |
|||
for k := 0 until MAX_STIRLING do s1( n, k ) := 0 |
|||
end for_n ; |
|||
s1( 0, 0 ) := 1; |
|||
for n := 1 until MAX_STIRLING do s1( n, 0 ) := 0; |
|||
for n := 1 until MAX_STIRLING do begin |
|||
for k := 1 until n do begin |
|||
integer s1Term; |
|||
s1Term := ( ( n - 1 ) * s1( n - 1, k ) ); |
|||
s1( n, k ) := s1( n - 1, k - 1 ) + s1Term |
|||
end for_k |
|||
end for_n ; |
|||
% print the Stirling numbers up to n, k = 12 % |
|||
write( "Unsigned Stirling numbers of the first kind:" ); |
|||
write( " k 0" ); |
|||
for k := 1 until MAX_STIRLING do writeon( i_w := if k < 6 then 10 else 9, s_w := 0, k ); |
|||
write( " n" ); |
|||
for n := 0 until MAX_STIRLING do begin |
|||
write( i_w := 2, s_w := 0, n, i_w := 3, s1( n, 0 ) ); |
|||
for k := 1 until n do begin |
|||
writeon( i_w := if k < 6 then 10 else 9, s_w := 0, s1( n, k ) ) |
|||
end for_k |
|||
end for_n |
|||
end |
|||
end. |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Unsigned Stirling numbers of the first kind: |
|||
k 0 1 2 3 4 5 6 7 8 9 10 11 12 |
|||
n |
|||
0 1 |
|||
1 0 1 |
|||
2 0 1 1 |
|||
3 0 2 3 1 |
|||
4 0 6 11 6 1 |
|||
5 0 24 50 35 10 1 |
|||
6 0 120 274 225 85 15 1 |
|||
7 0 720 1764 1624 735 175 21 1 |
|||
8 0 5040 13068 13132 6769 1960 322 28 1 |
|||
9 0 40320 109584 118124 67284 22449 4536 546 36 1 |
|||
10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 |
|||
11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 |
|||
12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 |
|||
</pre> |
</pre> |
||
=={{header|C}}== |
=={{header|C}}== |
||
< |
<syntaxhighlight lang="c">#include <stdbool.h> |
||
#include <stdio.h> |
#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
Line 189: | Line 307: | ||
stirling_cache_destroy(&sc); |
stirling_cache_destroy(&sc); |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 212: | Line 330: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
{{libheader|GMP}} |
{{libheader|GMP}} |
||
< |
<syntaxhighlight lang="cpp">#include <algorithm> |
||
#include <iomanip> |
#include <iomanip> |
||
#include <iostream> |
#include <iostream> |
||
Line 264: | Line 382: | ||
std::cout << max << '\n'; |
std::cout << max << '\n'; |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 286: | Line 404: | ||
19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 |
19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 |
||
</pre> |
</pre> |
||
=={{header|D}}== |
|||
{{trans|Java}} |
|||
<syntaxhighlight lang="d">import std.bigint; |
|||
import std.functional; |
|||
import std.stdio; |
|||
alias sterling1 = memoize!sterling1Impl; |
|||
BigInt sterling1Impl(int n, int k) { |
|||
if (n == 0 && k == 0) { |
|||
return BigInt(1); |
|||
} |
|||
if (n > 0 && k == 0) { |
|||
return BigInt(0); |
|||
} |
|||
if (k > n) { |
|||
return BigInt(0); |
|||
} |
|||
return sterling1(n - 1, k - 1) + (n - 1) * sterling1(n - 1, k); |
|||
} |
|||
void main() { |
|||
writeln("Unsigned Stirling numbers of the first kind:"); |
|||
int max = 12; |
|||
write("n/k"); |
|||
foreach (n; 0 .. max + 1) { |
|||
writef("%10d", n); |
|||
} |
|||
writeln; |
|||
foreach (n; 0 .. max + 1) { |
|||
writef("%-3d", n); |
|||
foreach (k; 0 .. n + 1) { |
|||
writef("%10s", sterling1(n, k)); |
|||
} |
|||
writeln; |
|||
} |
|||
writeln("The maximum value of S1(100, k) = "); |
|||
auto previous = BigInt(0); |
|||
foreach (k; 1 .. 101) { |
|||
auto current = sterling1(100, k); |
|||
if (previous < current) { |
|||
previous = current; |
|||
} else { |
|||
import std.conv; |
|||
writeln(previous); |
|||
writefln("(%d digits, k = %d)", previous.to!string.length, k - 1); |
|||
break; |
|||
} |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Unsigned Stirling numbers of the first kind: |
|||
n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 |
|||
0 1 |
|||
1 0 1 |
|||
2 0 1 1 |
|||
3 0 2 3 1 |
|||
4 0 6 11 6 1 |
|||
5 0 24 50 35 10 1 |
|||
6 0 120 274 225 85 15 1 |
|||
7 0 720 1764 1624 735 175 21 1 |
|||
8 0 5040 13068 13132 6769 1960 322 28 1 |
|||
9 0 40320 109584 118124 67284 22449 4536 546 36 1 |
|||
10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 |
|||
11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 |
|||
12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 |
|||
The maximum value of S1(100, k) = |
|||
19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 |
|||
(158 digits, k = 5)</pre> |
|||
=={{header|EasyLang}}== |
|||
<syntaxhighlight lang="easylang"> |
|||
print "Unsigned Stirling numbers of the first kind:" |
|||
len a[] 13 ; arrbase a[] 0 |
|||
len b[] 13 ; arrbase b[] 0 |
|||
a[0] = 1 |
|||
print 1 |
|||
for n = 1 to 12 |
|||
b[0] = 0 |
|||
write 0 & " " |
|||
for k = 1 to n |
|||
b[k] = a[k - 1] + (n - 1) * a[k] |
|||
write b[k] & " " |
|||
. |
|||
print "" |
|||
swap a[] b[] |
|||
. |
|||
</syntaxhighlight> |
|||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
Line 292: | Line 499: | ||
For example, <tt>x(x-1)(x-2) = x<sup>3</sup> - 3x<sup>2</sup> + 2x</tt>. Taking the absolute values of the coefficients, the third row is <tt>(0) 2 3 1</tt>. |
For example, <tt>x(x-1)(x-2) = x<sup>3</sup> - 3x<sup>2</sup> + 2x</tt>. Taking the absolute values of the coefficients, the third row is <tt>(0) 2 3 1</tt>. |
||
{{works with|Factor|0.99 development version 2019-07-10}} |
{{works with|Factor|0.99 development version 2019-07-10}} |
||
< |
<syntaxhighlight lang="factor">USING: arrays assocs formatting io kernel math math.polynomials |
||
math.ranges prettyprint sequences ; |
math.ranges prettyprint sequences ; |
||
IN: rosetta-code.stirling-first |
IN: rosetta-code.stirling-first |
||
Line 309: | Line 516: | ||
"Maximum value from 100th stirling row:" print |
"Maximum value from 100th stirling row:" print |
||
100 stirling-row supremum .</ |
100 stirling-row supremum .</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 333: | Line 540: | ||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
< |
<syntaxhighlight lang="freebasic">dim as integer S1(0 to 12, 0 to 12) 'initially set with zeroes |
||
dim as ubyte n, k |
dim as ubyte n, k |
||
dim as string outstr |
dim as string outstr |
||
Line 363: | Line 570: | ||
next k |
next k |
||
print outstr |
print outstr |
||
next n</ |
next n</syntaxhighlight> |
||
<pre>Signed Stirling numbers of the first kind |
<pre>Signed Stirling numbers of the first kind |
||
Line 384: | Line 591: | ||
=={{header|Fōrmulæ}}== |
=={{header|Fōrmulæ}}== |
||
{{FormulaeEntry|page=https://formulae.org/?script=examples/Stirling_numbers_of_the_first_kind}} |
|||
'''Solution''' |
|||
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text ([http://wiki.formulae.org/Editing_F%C5%8Drmul%C3%A6_expressions more info]). Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for transportation effects more than visualization and edition. |
|||
A single solution for signed and unsigned versions is presented. Unsigned version uses 1 as factor, signed version used -1. |
|||
The option to show Fōrmulæ programs and their results is showing images. Unfortunately images cannot be uploaded in Rosetta Code. |
|||
'''Version 1. Recursive''' |
|||
[[File:Fōrmulæ - Stirling numbers of the first kind 01.png]] |
|||
'''Test case 1. Show the unsigned Stirling numbers of the first kind, S₁(n, k), up to S₁(12, 12)''' |
|||
[[File:Fōrmulæ - Stirling numbers of the first kind 02.png]] |
|||
[[File:Fōrmulæ - Stirling numbers of the first kind 03.png]] |
|||
'''Test case 2. Show the signed Stirling numbers of the first kind, S₁(n, k), up to S₁(12, 12)''' |
|||
[[File:Fōrmulæ - Stirling numbers of the first kind 04.png]] |
|||
[[File:Fōrmulæ - Stirling numbers of the first kind 05.png]] |
|||
'''Version 2. Non recursive''' |
|||
A faster, non recursive version is presented. This construct a matrix. |
|||
[[File:Fōrmulæ - Stirling numbers of the first kind 06.png]] |
|||
'''Test case 1. Show the unsigned Stirling numbers of the first kind, S₁(n, k), up to S₁(12, 12)''' |
|||
[[File:Fōrmulæ - Stirling numbers of the first kind 07.png]] |
|||
(the result is the same as recursive version) |
|||
'''Test case 2. Show the signed Stirling numbers of the first kind, S₁(n, k), up to S₁(12, 12)''' |
|||
[[File:Fōrmulæ - Stirling numbers of the first kind 08.png]] |
|||
(the result is the same as recursive version) |
|||
'''Test case 3. Find the maximum value of unsigned S₁(n, k) where n ≤ 100''' |
|||
[[File:Fōrmulæ - Stirling numbers of the first kind 09.png]] |
|||
[[File:Fōrmulæ - Stirling numbers of the first kind 10.png]] |
|||
(the result is the same as recursive version) |
|||
'''Test case 4. Find the maximum value of signed S₁(n, k) where n ≤ 100''' |
|||
[[File:Fōrmulæ - Stirling numbers of the first kind 11.png]] |
|||
[[File:Fōrmulæ - Stirling numbers of the first kind 12.png]] |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 448: | Line 703: | ||
fmt.Println(max) |
fmt.Println(max) |
||
fmt.Printf("which has %d digits.\n", len(max.String())) |
fmt.Printf("which has %d digits.\n", len(max.String())) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 475: | Line 730: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
Using library: data-memocombinators for memoization |
Using library: data-memocombinators for memoization |
||
< |
<syntaxhighlight lang="haskell">import Text.Printf (printf) |
||
import Data.List (groupBy) |
import Data.List (groupBy) |
||
import qualified Data.MemoCombinators as Memo |
import qualified Data.MemoCombinators as Memo |
||
Line 499: | Line 754: | ||
where |
where |
||
table :: [[(Int, Int)]] |
table :: [[(Int, Int)]] |
||
table = groupBy (\a b -> fst a == fst b) $ (,) <$> [0..12] <*> [0..12]</ |
table = groupBy (\a b -> fst a == fst b) $ (,) <$> [0..12] <*> [0..12]</syntaxhighlight> |
||
Or library: monad-memo for memoization. |
Or library: monad-memo for memoization. |
||
< |
<syntaxhighlight lang="haskell">{-# LANGUAGE FlexibleContexts #-} |
||
import Text.Printf (printf) |
import Text.Printf (printf) |
||
Line 530: | Line 785: | ||
where |
where |
||
table :: [[(Int, Int)]] |
table :: [[(Int, Int)]] |
||
table = groupBy (\a b -> fst a == fst b) $ (,) <$> [0..12] <*> [0..12]</ |
table = groupBy (\a b -> fst a == fst b) $ (,) <$> [0..12] <*> [0..12]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 |
<pre>n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 |
||
Line 593: | Line 848: | ||
=={{header|Java}}== |
=={{header|Java}}== |
||
< |
<syntaxhighlight lang="java"> |
||
import java.math.BigInteger; |
import java.math.BigInteger; |
||
import java.util.HashMap; |
import java.util.HashMap; |
||
Line 651: | Line 906: | ||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 674: | Line 929: | ||
(158 digits, k = 5) |
(158 digits, k = 5) |
||
</pre> |
</pre> |
||
=={{header|jq}}== |
|||
'''Adapted from [[#Wren|Wren]]''' |
|||
{{works with|jq}} |
|||
'''Works with gojq, the Go implementation of jq''' |
|||
The Go implementation of jq supports unbounded-precision integer arithmetic and so the results shown below for max(S(100,k)) are based on a run of gojq. |
|||
<syntaxhighlight lang="jq"># For efficiency, define the helper function for `stirling1/2` as a |
|||
# top-level function so we can use it directly for constructing the table: |
|||
# input: [m,j,cache] |
|||
# output: [s, cache] |
|||
def stirling1: |
|||
. as [$m, $j, $cache] |
|||
| "\($m),\($j)" as $key |
|||
| $cache |
|||
| if has($key) then [.[$key], .] |
|||
elif $m == 0 and $j == 0 then [1, .] |
|||
elif $m > 0 and $j == 0 then [0, .] |
|||
elif $j > $m then [0, .] |
|||
else ([$m-1, $j-1, .] | stirling1) as [$s1, $c1] |
|||
| ([$m-1, $j, $c1] | stirling1) as [$s2, $c2] |
|||
| (($s1 + ($m-1) * $s2)) as $result |
|||
| ($c2 | (.[$key] = $result)) as $c3 |
|||
| [$result, $c3] |
|||
end; |
|||
def stirling1($n; $k): |
|||
[$n, $k, {}] | stirling1 | .[0]; |
|||
# produce the table for 0 ... $n inclusive |
|||
def stirlings($n): |
|||
# state: [cache, array_of_results] |
|||
reduce range(0; $n+1) as $i ([{}, []]; |
|||
reduce range(0; $i+1) as $j (.; |
|||
. as [$cache, $a] |
|||
| ([$i, $j, $cache] | stirling1) as [$s, $c] |
|||
| [$c, ($a|setpath([$i,$j]; $s))] )); |
|||
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .; |
|||
def task($n): |
|||
"Unsigned Stirling numbers of the first kind:", |
|||
"n/k \( [range(0;$n+1)|lpad(10)] | join(" "))", |
|||
((stirlings($n) | .[1]) as $a |
|||
| range(0; $n+1) as $i |
|||
| "\($i|lpad(3)): \( [$a[$i][]| lpad(10)] | join(" ") )" ), |
|||
"\nThe maximum value of S1(100, k) is", |
|||
([stirling1(100; range(0;101)) ] | max) ; |
|||
task(12)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Unsigned Stirling numbers of the first kind: |
|||
n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 |
|||
0: 1 |
|||
1: 0 1 |
|||
2: 0 1 1 |
|||
3: 0 2 3 1 |
|||
4: 0 6 11 6 1 |
|||
5: 0 24 50 35 10 1 |
|||
6: 0 120 274 225 85 15 1 |
|||
7: 0 720 1764 1624 735 175 21 1 |
|||
8: 0 5040 13068 13132 6769 1960 322 28 1 |
|||
9: 0 40320 109584 118124 67284 22449 4536 546 36 1 |
|||
10: 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 |
|||
11: 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 |
|||
12: 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 |
|||
The maximum value of S1(100, k) is |
|||
19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">using Combinatorics |
||
const s1cache = Dict() |
const s1cache = Dict() |
||
Line 720: | Line 1,047: | ||
printstirling1table(12) |
printstirling1table(12) |
||
println("\nThe maximum for stirling1(100, _) is:\n", maximum(k-> stirlings1(BigInt(100), BigInt(k)), 1:100)) |
println("\nThe maximum for stirling1(100, _) is:\n", maximum(k-> stirlings1(BigInt(100), BigInt(k)), 1:100)) |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
0 1 2 3 4 5 6 7 8 9 10 11 12 |
0 1 2 3 4 5 6 7 8 9 10 11 12 |
||
Line 743: | Line 1,070: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="scala">import java.math.BigInteger |
||
fun main() { |
fun main() { |
||
Line 793: | Line 1,120: | ||
COMPUTED[key] = result |
COMPUTED[key] = result |
||
return result |
return result |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Unsigned Stirling numbers of the first kind: |
<pre>Unsigned Stirling numbers of the first kind: |
||
Line 813: | Line 1,140: | ||
19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 |
19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 |
||
(158 digits, k = 5)</pre> |
(158 digits, k = 5)</pre> |
||
=={{header|Lua}}== |
|||
<syntaxhighlight lang="lua"> |
|||
do -- show some (unsigned) Stirling numbers of the first kind |
|||
local MAX_STIRLING = 12 |
|||
-- construct a matrix of Stirling numbers up to max n, max n |
|||
local s1 = {} |
|||
for n = 0, MAX_STIRLING do |
|||
s1[ n ] = {} |
|||
for k = 0, MAX_STIRLING do s1[ n ][ k ] = 0 end |
|||
end |
|||
s1[ 0 ][ 0 ] = 1 |
|||
for n = 1, MAX_STIRLING do s1[ n ][ 0 ] = 0 end |
|||
for n = 1, MAX_STIRLING do |
|||
for k = 1, n do |
|||
local s1Term = ( ( n - 1 ) * s1[ n - 1 ][ k ] ) |
|||
s1[ n ][ k ] = s1[ n - 1 ][ k - 1 ] + s1Term |
|||
end |
|||
end |
|||
io.write( "Unsigned Stirling numbers of the first kind:\n" ) |
|||
io.write( " k 0" ) |
|||
for k = 1, MAX_STIRLING do |
|||
io.write( string.format( ( k < 6 and "%10d" or "%9d" ), k ) ) |
|||
end |
|||
io.write( "\n" ) |
|||
io.write( " n\n" ); |
|||
for n = 0, MAX_STIRLING do |
|||
io.write( string.format( "%2d", n ), string.format( "%3d", s1[ n ][ 0 ] ) ) |
|||
for k = 1, n do |
|||
io.write( string.format( ( k < 6 and "%10d" or "%9d" ), s1[ n ][ k ] ) ) |
|||
end |
|||
io.write( "\n" ) |
|||
end |
|||
end |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Unsigned Stirling numbers of the first kind: |
|||
k 0 1 2 3 4 5 6 7 8 9 10 11 12 |
|||
n |
|||
0 1 |
|||
1 0 1 |
|||
2 0 1 1 |
|||
3 0 2 3 1 |
|||
4 0 6 11 6 1 |
|||
5 0 24 50 35 10 1 |
|||
6 0 120 274 225 85 15 1 |
|||
7 0 720 1764 1624 735 175 21 1 |
|||
8 0 5040 13068 13132 6769 1960 322 28 1 |
|||
9 0 40320 109584 118124 67284 22449 4536 546 36 1 |
|||
10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 |
|||
11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 |
|||
12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 |
|||
</pre> |
|||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
|||
<syntaxhighlight lang="mathematica">TableForm[Array[StirlingS1, {n = 12, k = 12} + 1, {0, 0}], TableHeadings -> {"n=" <> ToString[#] & /@ Range[0, n], "k=" <> ToString[#] & /@ Range[0, k]}] |
|||
Max[Abs[StirlingS1[100, #]] & /@ Range[0, 100]]</syntaxhighlight> |
|||
{{out}} |
|||
<pre> k=0 k=1 k=2 k=3 k=4 k=5 k=6 k=7 k=8 k=9 k=10 k=11 k=12 |
|||
n=0 1 0 0 0 0 0 0 0 0 0 0 0 0 |
|||
n=1 0 1 0 0 0 0 0 0 0 0 0 0 0 |
|||
n=2 0 -1 1 0 0 0 0 0 0 0 0 0 0 |
|||
n=3 0 2 -3 1 0 0 0 0 0 0 0 0 0 |
|||
n=4 0 -6 11 -6 1 0 0 0 0 0 0 0 0 |
|||
n=5 0 24 -50 35 -10 1 0 0 0 0 0 0 0 |
|||
n=6 0 -120 274 -225 85 -15 1 0 0 0 0 0 0 |
|||
n=7 0 720 -1764 1624 -735 175 -21 1 0 0 0 0 0 |
|||
n=8 0 -5040 13068 -13132 6769 -1960 322 -28 1 0 0 0 0 |
|||
n=9 0 40320 -109584 118124 -67284 22449 -4536 546 -36 1 0 0 0 |
|||
n=10 0 -362880 1026576 -1172700 723680 -269325 63273 -9450 870 -45 1 0 0 |
|||
n=11 0 3628800 -10628640 12753576 -8409500 3416930 -902055 157773 -18150 1320 -55 1 0 |
|||
n=12 0 -39916800 120543840 -150917976 105258076 -45995730 13339535 -2637558 357423 -32670 1925 -66 1 |
|||
19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000</pre> |
|||
=={{header|Nim}}== |
|||
A simple implementation using the recursive definition is enough to complete the task. |
|||
<syntaxhighlight lang="nim">import sequtils, strutils |
|||
proc s1(n, k: Natural): Natural = |
|||
if k == 0: return ord(n == 0) |
|||
if k > n: return 0 |
|||
s1(n - 1, k - 1) + (n - 1) * s1(n - 1, k) |
|||
echo " k ", toSeq(0..12).mapIt(($it).align(2)).join(" ") |
|||
echo " n" |
|||
for n in 0..12: |
|||
stdout.write ($n).align(2) |
|||
for k in 0..n: |
|||
stdout.write ($s1(n, k)).align(10) |
|||
stdout.write '\n'</syntaxhighlight> |
|||
{{out}} |
|||
<pre>k 0 1 2 3 4 5 6 7 8 9 10 11 12 |
|||
n |
|||
0 1 |
|||
1 0 1 |
|||
2 0 1 1 |
|||
3 0 2 3 1 |
|||
4 0 6 11 6 1 |
|||
5 0 24 50 35 10 1 |
|||
6 0 120 274 225 85 15 1 |
|||
7 0 720 1764 1624 735 175 21 1 |
|||
8 0 5040 13068 13132 6769 1960 322 28 1 |
|||
9 0 40320 109584 118124 67284 22449 4536 546 36 1 |
|||
10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 |
|||
11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 |
|||
12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1</pre> |
|||
To find the maximum value of S1(n, k) for n = 100, we need to use a third party library such as “bignum”. But this is not enough. To avoid multiple computation of the same terms, we have to use a cache. Note also that this method has its limits as it depends on the allowed depth of recursion. Here, this is not a problem and the result is obtained almost instantaneously. |
|||
{{libheader|bignum}} |
|||
<syntaxhighlight lang="nim">import tables |
|||
import bignum |
|||
var cache: Table[(Natural, Natural), Int] |
|||
proc s1(n, k: Natural): Int = |
|||
if k == 0: return newInt(ord(n == 0)) |
|||
if k > n: return newInt(0) |
|||
if (n, k) in cache: return cache[(n, k)] |
|||
result = s1(n - 1, k - 1) + (n - 1) * s1(n - 1, k) |
|||
cache[(n, k)] = result |
|||
var max = newInt(-1) |
|||
for k in 0..100: |
|||
let s = s1(100, k) |
|||
if s > max: max = s |
|||
else: break |
|||
echo "Maximum Stirling number of the first kind with n = 100:" |
|||
echo max</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Maximum Stirling number of the first kind with n = 100: |
|||
19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
use bigint; |
use bigint; |
||
Line 846: | Line 1,313: | ||
say "\nMaximum value from the S1(100, *) row:"; |
say "\nMaximum value from the S1(100, *) row:"; |
||
say max map { Stirling1(100,$_) } 0..100;</ |
say max map { Stirling1(100,$_) } 0..100;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Unsigned Stirling1 numbers of the first kind: S1(n, k): |
<pre>Unsigned Stirling1 numbers of the first kind: S1(n, k): |
||
Line 870: | Line 1,337: | ||
{{libheader|Phix/mpfr}} |
{{libheader|Phix/mpfr}} |
||
{{trans|Go}} |
{{trans|Go}} |
||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<lang Phix>include mpfr.e |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
|||
constant lim = 100, |
|||
lim1 = lim+1, |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">lim</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">100</span><span style="color: #0000FF;">,</span> |
|||
last = 12 |
|||
<span style="color: #000000;">lim1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lim</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> |
|||
bool unsigned = true |
|||
<span style="color: #000000;">last</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">12</span> |
|||
sequence s1 = repeat(0,lim1) |
|||
<span style="color: #004080;">bool</span> <span style="color: #000000;">unsigned</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span> |
|||
for n=1 to lim1 do |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lim1</span><span style="color: #0000FF;">)</span> |
|||
s1[n] = mpz_inits(lim1) |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">lim1</span> <span style="color: #008080;">do</span> |
|||
end for |
|||
<span style="color: #000000;">s1</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_inits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lim1</span><span style="color: #0000FF;">)</span> |
|||
mpz_set_si(s1[1][1],1) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
mpz {t, m100} = mpz_inits(2) |
|||
<span style="color: #7060A8;">mpz_set_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s1</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
|||
for n=1 to lim do |
|||
<span style="color: #004080;">mpz</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">m100</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_inits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> |
|||
for k=1 to n do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">lim</span> <span style="color: #008080;">do</span> |
|||
mpz_set_si(t,n-1) |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span> |
|||
mpz_mul(t,t,s1[n][k+1]) |
|||
<span style="color: #7060A8;">mpz_set_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
|||
if unsigned then |
|||
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s1</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">k</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span> |
|||
mpz_add(s1[n+1][k+1],s1[n][k],t) |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">unsigned</span> <span style="color: #008080;">then</span> |
|||
else |
|||
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s1</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">k</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span><span style="color: #000000;">s1</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">k</span><span style="color: #0000FF;">],</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span> |
|||
mpz_sub(s1[n+1][k+1],s1[n][k],t) |
|||
<span style="color: #008080;">else</span> |
|||
end if |
|||
<span style="color: #7060A8;">mpz_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s1</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">k</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span><span style="color: #000000;">s1</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">k</span><span style="color: #0000FF;">],</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
string s = iff(unsigned?"Uns":"S") |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
printf(1,"%signed Stirling numbers of the first kind: S1(n, k):\n n k:",s) |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">unsigned</span><span style="color: #0000FF;">?</span><span style="color: #008000;">"Uns"</span><span style="color: #0000FF;">:</span><span style="color: #008000;">"S"</span><span style="color: #0000FF;">)</span> |
|||
for i=0 to last do |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%signed Stirling numbers of the first kind: S1(n, k):\n n k:"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
|||
printf(1,"%5d ", i) |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">last</span> <span style="color: #008080;">do</span> |
|||
end for |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%5d "</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">)</span> |
|||
printf(1,"\n--- %s\n",repeat('-',last*10+5)) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
for n=0 to last do |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n--- %s\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'-'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">last</span><span style="color: #0000FF;">*</span><span style="color: #000000;">10</span><span style="color: #0000FF;">+</span><span style="color: #000000;">5</span><span style="color: #0000FF;">))</span> |
|||
printf(1,"%2d ", n) |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">last</span> <span style="color: #008080;">do</span> |
|||
for k=1 to n+1 do |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%2d "</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
mpfr_printf(1,"%9Zd ", s1[n+1][k]) |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
end for |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%9s "</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s1</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">k</span><span style="color: #0000FF;">])})</span> |
|||
printf(1,"\n") |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end for |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span> |
|||
for k=1 to lim1 do |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
mpz s100k = s1[lim1][k] |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">lim1</span> <span style="color: #008080;">do</span> |
|||
if mpz_cmp(s100k,m100) > 0 then |
|||
<span style="color: #004080;">mpz</span> <span style="color: #000000;">s100k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s1</span><span style="color: #0000FF;">[</span><span style="color: #000000;">lim1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> |
|||
mpz_set(m100,s100k) |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_cmp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s100k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m100</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">></span> <span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
end if |
|||
<span style="color: #7060A8;">mpz_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m100</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s100k</span><span style="color: #0000FF;">)</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
printf(1,"\nThe maximum S1(100,k): %s\n",shorten(mpz_get_str(m100)))</lang> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nThe maximum S1(100,k): %s\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m100</span><span style="color: #0000FF;">)))</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 937: | Line 1,407: | ||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
||
{{works with|SWI Prolog}} |
{{works with|SWI Prolog}} |
||
< |
<syntaxhighlight lang="prolog">:- dynamic stirling1_cache/3. |
||
stirling1(N, N, 1):-!. |
stirling1(N, N, 1):-!. |
||
Line 978: | Line 1,448: | ||
writeln('Maximum value of S1(n,k) where n = 100:'), |
writeln('Maximum value of S1(n,k) where n = 100:'), |
||
max_stirling1(100, M), |
max_stirling1(100, M), |
||
writeln(M).</ |
writeln(M).</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 997: | Line 1,467: | ||
Maximum value of S1(n,k) where n = 100: |
Maximum value of S1(n,k) where n = 100: |
||
19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 |
19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 |
||
</pre> |
|||
=={{header|PureBasic}}== |
|||
{{trans|FreeBasic}} |
|||
<syntaxhighlight lang="purebasic">EnableExplicit |
|||
#MAX=12 |
|||
#LZ=10 |
|||
#SP$=" " |
|||
Dim s1.i(#MAX,#MAX) |
|||
Define n.i,k.i,x.i,s$,esc$ |
|||
s1(0,0)=1 |
|||
esc$=#ESC$+"[8;24;170t" ; Enlarges the console window |
|||
For n=0 To #MAX |
|||
For k=1 To n |
|||
s1(n,k)=s1(n-1,k-1)-(n-1)*s1(n-1,k) |
|||
Next |
|||
Next |
|||
If OpenConsole() |
|||
Print(esc$) |
|||
PrintN(~"Signed Stirling numbers of the first kind\n") |
|||
Print(#SP$+"k") |
|||
For x=0 To #MAX : Print(#SP$+RSet(Str(x),#LZ)) : Next |
|||
PrintN(~"\n n"+LSet("-",13*12,"-")) |
|||
For n=0 To #MAX |
|||
Print(RSet(Str(n),3)) |
|||
For k=0 To #MAX : Print(#SP$+RSet(Str(s1(n,k)),#LZ)) : Next |
|||
PrintN("") |
|||
Next |
|||
Input() |
|||
EndIf</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Signed Stirling numbers of the first kind |
|||
k 0 1 2 3 4 5 6 7 8 9 10 11 12 |
|||
n------------------------------------------------------------------------------------------------------------------------------------------------------------ |
|||
0 1 0 0 0 0 0 0 0 0 0 0 0 0 |
|||
1 0 1 0 0 0 0 0 0 0 0 0 0 0 |
|||
2 0 -1 1 0 0 0 0 0 0 0 0 0 0 |
|||
3 0 2 -3 1 0 0 0 0 0 0 0 0 0 |
|||
4 0 -6 11 -6 1 0 0 0 0 0 0 0 0 |
|||
5 0 24 -50 35 -10 1 0 0 0 0 0 0 0 |
|||
6 0 -120 274 -225 85 -15 1 0 0 0 0 0 0 |
|||
7 0 720 -1764 1624 -735 175 -21 1 0 0 0 0 0 |
|||
8 0 -5040 13068 -13132 6769 -1960 322 -28 1 0 0 0 0 |
|||
9 0 40320 -109584 118124 -67284 22449 -4536 546 -36 1 0 0 0 |
|||
10 0 -362880 1026576 -1172700 723680 -269325 63273 -9450 870 -45 1 0 0 |
|||
11 0 3628800 -10628640 12753576 -8409500 3416930 -902055 157773 -18150 1320 -55 1 0 |
|||
12 0 -39916800 120543840 -150917976 105258076 -45995730 13339535 -2637558 357423 -32670 1925 -66 1 |
|||
</pre> |
</pre> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
<syntaxhighlight lang="python"> |
|||
<lang Python> |
|||
computed = {} |
computed = {} |
||
Line 1,039: | Line 1,560: | ||
print("{0}\n({1} digits, k = {2})\n".format(previous, len(str(previous)), k - 1)) |
print("{0}\n({1} digits, k = {2})\n".format(previous, len(str(previous)), k - 1)) |
||
break |
break |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,060: | Line 1,581: | ||
19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 |
19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 |
||
(158 digits, k = 5) |
(158 digits, k = 5) |
||
</pre> |
|||
=={{header|Quackery}}== |
|||
<syntaxhighlight lang="quackery"> [ dip number$ |
|||
over size - |
|||
space swap of |
|||
swap join echo$ ] is justify ( n n --> ) |
|||
[ table ] is s1table ( n --> n ) |
|||
[ swap 101 * + s1table ] is s1 ( n n --> n ) |
|||
101 times |
|||
[ i^ 101 times |
|||
[ dup i^ |
|||
[ over 0 = |
|||
over 0 = and iff |
|||
[ 2drop 1 ] done |
|||
over 0 > |
|||
over 0 = and iff |
|||
[ 2drop 0 ] done |
|||
2dup < iff |
|||
[ 2drop 0 ] done |
|||
2dup 1 - swap |
|||
1 - swap s1 unrot |
|||
dip [ 1 - dup ] |
|||
s1 * + ] |
|||
' s1table put ] |
|||
drop ] |
|||
say "Unsigned Stirling numbers of the first kind." |
|||
cr cr |
|||
13 times |
|||
[ i^ dup 1+ times |
|||
[ dup i^ s1 |
|||
10 justify ] |
|||
drop cr ] |
|||
cr |
|||
0 100 times |
|||
[ 100 i^ 1+ s1 max ] |
|||
echo cr</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Unsigned Stirling numbers of the first kind. |
|||
1 |
|||
0 1 |
|||
0 1 1 |
|||
0 2 3 1 |
|||
0 6 11 6 1 |
|||
0 24 50 35 10 1 |
|||
0 120 274 225 85 15 1 |
|||
0 720 1764 1624 735 175 21 1 |
|||
0 5040 13068 13132 6769 1960 322 28 1 |
|||
0 40320 109584 118124 67284 22449 4536 546 36 1 |
|||
0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 |
|||
0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 |
|||
0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 |
|||
19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 |
|||
</pre> |
</pre> |
||
Line 1,066: | Line 1,649: | ||
{{works with|Rakudo|2019.07.1}} |
{{works with|Rakudo|2019.07.1}} |
||
<lang |
<syntaxhighlight lang="raku" line>sub Stirling1 (Int \n, Int \k) { |
||
return 1 unless n || k; |
return 1 unless n || k; |
||
return 0 unless n && k; |
return 0 unless n && k; |
||
Line 1,087: | Line 1,670: | ||
say "\nMaximum value from the S1(100, *) row:"; |
say "\nMaximum value from the S1(100, *) row:"; |
||
say (^100).map( { Stirling1 100, $_ } ).max;</ |
say (^100).map( { Stirling1 100, $_ } ).max;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Unsigned Stirling numbers of the first kind: S1(n, k): |
<pre>Unsigned Stirling numbers of the first kind: S1(n, k): |
||
Line 1,110: | Line 1,693: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
Some extra code was added to minimize the displaying of the column widths. |
Some extra code was added to minimize the displaying of the column widths. |
||
< |
<syntaxhighlight lang="rexx">/*REXX program to compute and display (unsigned) Stirling numbers of the first kind.*/ |
||
parse arg lim . /*obtain optional argument from the CL.*/ |
parse arg lim . /*obtain optional argument from the CL.*/ |
||
if lim=='' | lim=="," then lim= 12 /*Not specified? Then use the default.*/ |
if lim=='' | lim=="," then lim= 12 /*Not specified? Then use the default.*/ |
||
Line 1,149: | Line 1,732: | ||
end /*c*/ |
end /*c*/ |
||
say right(r,wi) strip(substr($,2), 'T') /*display a single row of the grid. */ |
say right(r,wi) strip(substr($,2), 'T') /*display a single row of the grid. */ |
||
end /*r*/ /*stick a fork in it, we're all done. */</ |
end /*r*/ /*stick a fork in it, we're all done. */</syntaxhighlight> |
||
{{out|output|text= when using the default input:}} |
{{out|output|text= when using the default input:}} |
||
<pre> |
<pre> |
||
Line 1,175: | Line 1,758: | ||
19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 |
19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 |
||
</pre> |
</pre> |
||
=={{header|RPL}}== |
|||
« '''IF''' DUP2 AND NOT '''THEN''' == |
|||
'''ELSE''' |
|||
SWAP 1 - DUP ROT |
|||
DUP2 1 - <span style="color:blue">US1</span> 4 ROLLD <span style="color:blue">US1</span> * + |
|||
'''END''' |
|||
» '<span style="color:blue">US1</span>' STO <span style="color:grey">''@ ( n k → unsigned S1(n,k) )''</span> |
|||
« { 12 12 } 0 CON |
|||
1 12 '''FOR''' n |
|||
1 n '''FOR''' k |
|||
n k 2 →LIST DUP EVAL <span style="color:blue">US1</span> PUT |
|||
'''NEXT NEXT''' |
|||
» '<span style="color:blue">TASK</span>' STO |
|||
{{out}} |
|||
<pre> |
|||
1: [[ 1 0 0 0 0 0 0 0 0 0 0 0 ] |
|||
[ 1 1 0 0 0 0 0 0 0 0 0 0 ] |
|||
[ 2 3 1 0 0 0 0 0 0 0 0 0 ] |
|||
[ 6 11 6 1 0 0 0 0 0 0 0 0 ] |
|||
[ 24 50 35 10 1 0 0 0 0 0 0 0 ] |
|||
[ 120 274 225 85 15 1 0 0 0 0 0 0 ] |
|||
[ 720 1764 1624 735 175 21 1 0 0 0 0 0 ] |
|||
[ 5040 13068 13132 6769 1960 322 28 1 0 0 0 0 ] |
|||
[ 40320 109584 118124 67284 22449 4536 546 36 1 0 0 0 ] |
|||
[ 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 0 0 ] |
|||
[ 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 0 ] |
|||
[ 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 ]] |
|||
</pre> |
|||
=={{header|Ruby}}== |
|||
{{trans|D}} |
|||
<syntaxhighlight lang="ruby">$cache = {} |
|||
def sterling1(n, k) |
|||
if n == 0 and k == 0 then |
|||
return 1 |
|||
end |
|||
if n > 0 and k == 0 then |
|||
return 0 |
|||
end |
|||
if k > n then |
|||
return 0 |
|||
end |
|||
key = [n, k] |
|||
if $cache[key] then |
|||
return $cache[key] |
|||
end |
|||
value = sterling1(n - 1, k - 1) + (n - 1) * sterling1(n - 1, k) |
|||
$cache[key] = value |
|||
return value |
|||
end |
|||
MAX = 12 |
|||
def main |
|||
print "Unsigned Stirling numbers of the first kind:\n" |
|||
print "n/k" |
|||
for n in 0 .. MAX |
|||
print "%10d" % [n] |
|||
end |
|||
print "\n" |
|||
for n in 0 .. MAX |
|||
print "%-3d" % [n] |
|||
for k in 0 .. n |
|||
print "%10d" % [sterling1(n, k)] |
|||
end |
|||
print "\n" |
|||
end |
|||
print "The maximum value of S1(100, k) =\n" |
|||
previous = 0 |
|||
for k in 1 .. 100 |
|||
current = sterling1(100, k) |
|||
if previous < current then |
|||
previous = current |
|||
else |
|||
print previous, "\n" |
|||
print "(%d digits, k = %d)\n" % [previous.to_s.length, k - 1] |
|||
break |
|||
end |
|||
end |
|||
end |
|||
main()</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Unsigned Stirling numbers of the first kind: |
|||
n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 |
|||
0 1 |
|||
1 0 1 |
|||
2 0 1 1 |
|||
3 0 2 3 1 |
|||
4 0 6 11 6 1 |
|||
5 0 24 50 35 10 1 |
|||
6 0 120 274 225 85 15 1 |
|||
7 0 720 1764 1624 735 175 21 1 |
|||
8 0 5040 13068 13132 6769 1960 322 28 1 |
|||
9 0 40320 109584 118124 67284 22449 4536 546 36 1 |
|||
10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 |
|||
11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 |
|||
12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 |
|||
The maximum value of S1(100, k) = |
|||
19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 |
|||
(158 digits, k = 5)</pre> |
|||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby">func S1(n, k) { # unsigned Stirling numbers of the first kind |
||
stirling(n, k).abs |
stirling(n, k).abs |
||
} |
} |
||
Line 1,197: | Line 1,884: | ||
say "\nMaximum value from the S1(#{n}, *) row:" |
say "\nMaximum value from the S1(#{n}, *) row:" |
||
say { S1(n, _) }.map(^n).max |
say { S1(n, _) }.map(^n).max |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,220: | Line 1,907: | ||
Alternatively, the '''S1(n,k)''' function can be defined as: |
Alternatively, the '''S1(n,k)''' function can be defined as: |
||
< |
<syntaxhighlight lang="ruby">func S1((0), (0)) { 1 } |
||
func S1(_, (0)) { 0 } |
func S1(_, (0)) { 0 } |
||
func S1((0), _) { 0 } |
func S1((0), _) { 0 } |
||
func S1(n, k) is cached { S1(n-1, k-1) + (n-1)*S1(n-1, k) }</ |
func S1(n, k) is cached { S1(n-1, k-1) + (n-1)*S1(n-1, k) }</syntaxhighlight> |
||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
This computes the unsigned Stirling numbers of the first kind. |
This computes the unsigned Stirling numbers of the first kind. |
||
Inspired by [[Stirling_numbers_of_the_second_kind#Tcl]], hence similar to [[#Java]]. |
Inspired by [[Stirling_numbers_of_the_second_kind#Tcl]], hence similar to [[#Java]]. |
||
< |
<syntaxhighlight lang="tcl">proc US1 {n k} { |
||
if {$k == 0} { |
if {$k == 0} { |
||
return [expr {$n == 0}] |
return [expr {$n == 0}] |
||
Line 1,279: | Line 1,966: | ||
} |
} |
||
} |
} |
||
main</ |
main</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,300: | Line 1,987: | ||
19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 |
19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 |
||
(158 digits, k = 5)</pre> |
(158 digits, k = 5)</pre> |
||
=={{header|Wren}}== |
|||
{{trans|Java}}{{libheader|Wren-big}} |
|||
{{libheader|Wren-fmt}} |
|||
<syntaxhighlight lang="wren">import "./big" for BigInt |
|||
import "./fmt" for Fmt |
|||
var computed = {} |
|||
var stirling1 // recursive |
|||
stirling1 = Fn.new { |n, k| |
|||
var key = "%(n),%(k)" |
|||
if (computed.containsKey(key)) return computed[key] |
|||
if (n == 0 && k == 0) return BigInt.one |
|||
if (n > 0 && k == 0) return BigInt.zero |
|||
if (k > n) return BigInt.zero |
|||
var result = stirling1.call(n-1, k-1) + stirling1.call(n-1, k)*(n-1) |
|||
computed[key] = result |
|||
return result |
|||
} |
|||
System.print("Unsigned Stirling numbers of the first kind:") |
|||
var max = 12 |
|||
System.write("n/k") |
|||
for (n in 0..max) Fmt.write("$10d", n) |
|||
System.print() |
|||
for (n in 0..max) { |
|||
Fmt.write("$-3d", n) |
|||
for (k in 0..n) Fmt.write("$10i", stirling1.call(n, k)) |
|||
System.print() |
|||
} |
|||
System.print("The maximum value of S1(100, k) =") |
|||
var previous = BigInt.zero |
|||
for (k in 1..100) { |
|||
var current = stirling1.call(100, k) |
|||
if (current > previous) { |
|||
previous = current |
|||
} else { |
|||
Fmt.print("$i\n($d digits, k = $d)", previous, previous.toString.count, k - 1) |
|||
break |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Unsigned Stirling numbers of the first kind: |
|||
n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 |
|||
0 1 |
|||
1 0 1 |
|||
2 0 1 1 |
|||
3 0 2 3 1 |
|||
4 0 6 11 6 1 |
|||
5 0 24 50 35 10 1 |
|||
6 0 120 274 225 85 15 1 |
|||
7 0 720 1764 1624 735 175 21 1 |
|||
8 0 5040 13068 13132 6769 1960 322 28 1 |
|||
9 0 40320 109584 118124 67284 22449 4536 546 36 1 |
|||
10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 |
|||
11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 |
|||
12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 |
|||
The maximum value of S1(100, k) = |
|||
19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 |
|||
(158 digits, k = 5) |
|||
</pre> |
|||
=={{header|XPL0}}== |
|||
{{trans|ALGOL W}} |
|||
<syntaxhighlight lang "XPL0"> define MAX_STIRLING = 12; |
|||
integer S1 ( MAX_STIRLING+1, MAX_STIRLING+1 ); |
|||
integer N, K, S1Term; |
|||
begin |
|||
\Construct a matrix of Stirling numbers up to max N, max N |
|||
for N := 0 to MAX_STIRLING do begin |
|||
for K := 0 to MAX_STIRLING do S1( N, K ) := 0 |
|||
end; \for_N |
|||
S1( 0, 0 ) := 1; |
|||
for N := 1 to MAX_STIRLING do S1( N, 0 ) := 0; |
|||
for N := 1 to MAX_STIRLING do begin |
|||
for K := 1 to N do begin |
|||
S1Term := ( ( N - 1 ) * S1( N - 1, K ) ); |
|||
S1( N, K ) := S1( N - 1, K - 1 ) + S1Term |
|||
end \for_K |
|||
end; \for_N |
|||
\Print the Stirling numbers up to N, K = 12 |
|||
Text(0, "Unsigned Stirling numbers of the first kind:^m^j K" ); |
|||
Format(10, 0); |
|||
for K := 0 to MAX_STIRLING do RlOut(0, float(K) ); |
|||
CrLf(0); |
|||
Text(0, " N^m^j" ); |
|||
for N := 0 to MAX_STIRLING do begin |
|||
Format(2, 0); RlOut(0, float(N)); |
|||
Format(10, 0); |
|||
for K := 0 to N do begin |
|||
RlOut(0, float(S1( N, K )) ) |
|||
end; \for_K |
|||
CrLf(0); |
|||
end \for_N |
|||
end</syntaxhighlight> |
|||
{{out}} |
|||
<pre style="font-size:66%"> |
|||
Unsigned Stirling numbers of the first kind: |
|||
K 0 1 2 3 4 5 6 7 8 9 10 11 12 |
|||
N |
|||
0 1 |
|||
1 0 1 |
|||
2 0 1 1 |
|||
3 0 2 3 1 |
|||
4 0 6 11 6 1 |
|||
5 0 24 50 35 10 1 |
|||
6 0 120 274 225 85 15 1 |
|||
7 0 720 1764 1624 735 175 21 1 |
|||
8 0 5040 13068 13132 6769 1960 322 28 1 |
|||
9 0 40320 109584 118124 67284 22449 4536 546 36 1 |
|||
10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 |
|||
11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 |
|||
12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 |
|||
</pre> |
|||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang="zkl">fcn stirling1(n,k){ |
||
var seen=Dictionary(); // cache for recursion |
var seen=Dictionary(); // cache for recursion |
||
if(n==k==0) return(1); |
if(n==k==0) return(1); |
||
Line 1,312: | Line 2,116: | ||
if(Void==(s2 := seen.find(z2))){ s2 = seen[z2] = stirling1(n - 1, k) } |
if(Void==(s2 := seen.find(z2))){ s2 = seen[z2] = stirling1(n - 1, k) } |
||
(n - 1)*s2 + s1; // n is first to cast to BigInt (if using BigInts) |
(n - 1)*s2 + s1; // n is first to cast to BigInt (if using BigInts) |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">// calculate entire table (cached), find max, find num digits in max |
||
N,mx := 12, [1..N].apply(fcn(n){ [1..n].apply(stirling1.fp(n)) : (0).max(_) }) : (0).max(_); |
N,mx := 12, [1..N].apply(fcn(n){ [1..n].apply(stirling1.fp(n)) : (0).max(_) }) : (0).max(_); |
||
fmt:="%%%dd".fmt("%d".fmt(mx.numDigits + 1)).fmt; // "%9d".fmt |
fmt:="%%%dd".fmt("%d".fmt(mx.numDigits + 1)).fmt; // "%9d".fmt |
||
Line 1,320: | Line 2,124: | ||
foreach row in ([0..N]){ |
foreach row in ([0..N]){ |
||
println("%3d".fmt(row), [0..row].pump(String, stirling1.fp(row), fmt)); |
println("%3d".fmt(row), [0..row].pump(String, stirling1.fp(row), fmt)); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre style="font-size:83%"> |
<pre style="font-size:83%"> |
||
Line 1,340: | Line 2,144: | ||
</pre> |
</pre> |
||
{{libheader|GMP}} GNU Multiple Precision Arithmetic Library |
{{libheader|GMP}} GNU Multiple Precision Arithmetic Library |
||
< |
<syntaxhighlight lang="zkl">var [const] BI=Import("zklBigNum"); // libGMP |
||
N=100; |
N=100; |
||
println("Maximum value from the S1(%d, *) row:".fmt(N)); |
println("Maximum value from the S1(%d, *) row:".fmt(N)); |
||
[1..N].apply(stirling1.fp(BI(N))) |
[1..N].apply(stirling1.fp(BI(N))) |
||
.reduce(fcn(m,n){ m.max(n) }).println();</ |
.reduce(fcn(m,n){ m.max(n) }).println();</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre style="font-size:83%"> |
<pre style="font-size:83%"> |
Latest revision as of 09:57, 25 March 2024
You are encouraged to solve this task according to the task description, using any language you may know.
Stirling numbers of the first kind, or Stirling cycle numbers, count permutations according to their number of cycles (counting fixed points as cycles of length one).
They may be defined directly to be the number of permutations of n elements with k disjoint cycles.
Stirling numbers of the first kind express coefficients of polynomial expansions of falling or rising factorials.
Depending on the application, Stirling numbers of the first kind may be "signed" or "unsigned". Signed Stirling numbers of the first kind arise when the polynomial expansion is expressed in terms of falling factorials; unsigned when expressed in terms of rising factorials. The only substantial difference is that, for signed Stirling numbers of the first kind, values of S1(n, k) are negative when n + k is odd.
Stirling numbers of the first kind follow the simple identities:
S1(0, 0) = 1 S1(n, 0) = 0 if n > 0 S1(n, k) = 0 if k > n S1(n, k) = S1(n - 1, k - 1) + (n - 1) * S1(n - 1, k) # For unsigned or S1(n, k) = S1(n - 1, k - 1) - (n - 1) * S1(n - 1, k) # For signed
- Task
- Write a routine (function, procedure, whatever) to find Stirling numbers of the first kind. There are several methods to generate Stirling numbers of the first kind. You are free to choose the most appropriate for your language. If your language has a built-in, or easily, publicly available library implementation, it is acceptable to use that.
- Using the routine, generate and show here, on this page, a table (or triangle) showing the Stirling numbers of the first kind, S1(n, k), up to S1(12, 12). it is optional to show the row / column for n == 0 and k == 0. It is optional to show places where S1(n, k) == 0 (when k > n). You may choose to show signed or unsigned Stirling numbers of the first kind, just make a note of which was chosen.
- If your language supports large integers, find and show here, on this page, the maximum value of S1(n, k) where n == 100.
- See also
- Related Tasks
11l
[(Int, Int) = BigInt] computed
F sterling1(n, k)
V key = (n, k)
I key C :computed
R :computed[key]
I n == k == 0
R BigInt(1)
I n > 0 & k == 0
R BigInt(0)
I k > n
R BigInt(0)
V result = sterling1(n - 1, k - 1) + (n - 1) * sterling1(n - 1, k)
:computed[key] = result
R result
print(‘Unsigned Stirling numbers of the first kind:’)
V MAX = 12
print(‘n/k’.ljust(10), end' ‘’)
L(n) 0 .. MAX
print(String(n).rjust(10), end' ‘’)
print()
L(n) 0 .. MAX
print(String(n).ljust(10), end' ‘’)
L(k) 0 .. n
print(String(sterling1(n, k)).rjust(10), end' ‘’)
print()
print(‘The maximum value of S1(100, k) = ’)
BigInt previous = 0
L(k) 1 .. 100
V current = sterling1(100, k)
I current > previous
previous = current
E
print("#.\n(#. digits, k = #.)\n".format(previous, String(previous).len, k - 1))
L.break
- Output:
Unsigned Stirling numbers of the first kind: n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 2 3 1 4 0 6 11 6 1 5 0 24 50 35 10 1 6 0 120 274 225 85 15 1 7 0 720 1764 1624 735 175 21 1 8 0 5040 13068 13132 6769 1960 322 28 1 9 0 40320 109584 118124 67284 22449 4536 546 36 1 10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 The maximum value of S1(100, k) = 19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 (158 digits, k = 5)
ALGOL 68
Uses the Algol 68G LONG LONG INT mode which provides large-precision integers. As the default number of digits is insufficient for the task, the maximum nunber of digits is specified by a pragmatic comment.
BEGIN # show some (unsigned) Stirling numbers of the first kind #
# specify the precision of LONG LONG INT, we need about 160 digits #
# for Stirling numbers of the first kind with n, k = 100 #
PR precision 160 PR
MODE SINT = LONG LONG INT;
# returns a triangular matrix of Stirling numbers up to max n, max n #
# the numbers are signed if signed is TRUE, unsigned otherwise #
PROC make s1 = ( INT max n, BOOL signed )REF[,]SINT:
BEGIN
REF[,]SINT s1 := HEAP[ 0 : max n, 0 : max n ]SINT;
FOR n FROM 0 TO max n DO FOR k FROM 0 TO max n DO s1[ n, k ] := 0 OD OD;
s1[ 0, 0 ] := 1;
FOR n FROM 1 TO max n DO s1[ n, 0 ] := 0 OD;
FOR n FROM 1 TO max n DO
FOR k FROM 1 TO n DO
SINT s1 term = ( ( n - 1 ) * s1[ n - 1, k ] );
s1[ n, k ] := s1[ n - 1, k - 1 ] + IF signed THEN - s1 term ELSE s1 term FI
OD
OD;
s1
END # make s1 # ;
# task requirements: #
# print Stirling numbers up to n, k = 12 #
BEGIN
INT max stirling = 12;
REF[,]SINT s1 = make s1( max stirling, FALSE );
print( ( "Unsigned Stirling numbers of the first kind:", newline ) );
print( ( " k 0" ) );
FOR k TO max stirling DO print( ( whole( k, IF k < 6 THEN -10 ELSE -9 FI ) ) ) OD;
print( ( newline, " n", newline ) );
FOR n FROM 0 TO max stirling DO
print( ( whole( n, -2 ), whole( s1[ n, 0 ], -3 ) ) );
FOR k TO n DO
print( ( whole( s1[ n, k ], IF k < 6 THEN -10 ELSE -9 FI ) ) )
OD;
print( ( newline ) )
OD
END;
# find the maximum Stirling number with n = 100 #
BEGIN
INT max stirling = 100;
REF[,]SINT s1 = make s1( max stirling, FALSE );
SINT max 100 := 0;
FOR k FROM 0 TO max stirling DO
IF s1[ max stirling, k ] > max 100 THEN max 100 := s1[ max stirling, k ] FI
OD;
print( ( "Maximum Stirling number of the first kind with n = 100:", newline ) );
print( ( whole( max 100, 0 ), newline ) )
END
END
- Output:
Unsigned Stirling numbers of the first kind: k 0 1 2 3 4 5 6 7 8 9 10 11 12 n 0 1 1 0 1 2 0 1 1 3 0 2 3 1 4 0 6 11 6 1 5 0 24 50 35 10 1 6 0 120 274 225 85 15 1 7 0 720 1764 1624 735 175 21 1 8 0 5040 13068 13132 6769 1960 322 28 1 9 0 40320 109584 118124 67284 22449 4536 546 36 1 10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 Maximum Stirling number of the first kind with n = 100: 19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000
ALGOL W
begin % show some (unsigned) Stirling numbers of the first kind %
integer MAX_STIRLING;
MAX_STIRLING := 12;
begin
% construct a matrix of Stirling numbers up to max n, max n %
integer array s1 ( 0 :: MAX_STIRLING, 0 :: MAX_STIRLING );
for n := 0 until MAX_STIRLING do begin
for k := 0 until MAX_STIRLING do s1( n, k ) := 0
end for_n ;
s1( 0, 0 ) := 1;
for n := 1 until MAX_STIRLING do s1( n, 0 ) := 0;
for n := 1 until MAX_STIRLING do begin
for k := 1 until n do begin
integer s1Term;
s1Term := ( ( n - 1 ) * s1( n - 1, k ) );
s1( n, k ) := s1( n - 1, k - 1 ) + s1Term
end for_k
end for_n ;
% print the Stirling numbers up to n, k = 12 %
write( "Unsigned Stirling numbers of the first kind:" );
write( " k 0" );
for k := 1 until MAX_STIRLING do writeon( i_w := if k < 6 then 10 else 9, s_w := 0, k );
write( " n" );
for n := 0 until MAX_STIRLING do begin
write( i_w := 2, s_w := 0, n, i_w := 3, s1( n, 0 ) );
for k := 1 until n do begin
writeon( i_w := if k < 6 then 10 else 9, s_w := 0, s1( n, k ) )
end for_k
end for_n
end
end.
- Output:
Unsigned Stirling numbers of the first kind: k 0 1 2 3 4 5 6 7 8 9 10 11 12 n 0 1 1 0 1 2 0 1 1 3 0 2 3 1 4 0 6 11 6 1 5 0 24 50 35 10 1 6 0 120 274 225 85 15 1 7 0 720 1764 1624 735 175 21 1 8 0 5040 13068 13132 6769 1960 322 28 1 9 0 40320 109584 118124 67284 22449 4536 546 36 1 10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1
C
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct stirling_cache_tag {
int max;
int* values;
} stirling_cache;
int stirling_number1(stirling_cache* sc, int n, int k) {
if (k == 0)
return n == 0 ? 1 : 0;
if (n > sc->max || k > n)
return 0;
return sc->values[n*(n-1)/2 + k - 1];
}
bool stirling_cache_create(stirling_cache* sc, int max) {
int* values = calloc(max * (max + 1)/2, sizeof(int));
if (values == NULL)
return false;
sc->max = max;
sc->values = values;
for (int n = 1; n <= max; ++n) {
for (int k = 1; k <= n; ++k) {
int s1 = stirling_number1(sc, n - 1, k - 1);
int s2 = stirling_number1(sc, n - 1, k);
values[n*(n-1)/2 + k - 1] = s1 + s2 * (n - 1);
}
}
return true;
}
void stirling_cache_destroy(stirling_cache* sc) {
free(sc->values);
sc->values = NULL;
}
void print_stirling_numbers(stirling_cache* sc, int max) {
printf("Unsigned Stirling numbers of the first kind:\nn/k");
for (int k = 0; k <= max; ++k)
printf(k == 0 ? "%2d" : "%10d", k);
printf("\n");
for (int n = 0; n <= max; ++n) {
printf("%2d ", n);
for (int k = 0; k <= n; ++k)
printf(k == 0 ? "%2d" : "%10d", stirling_number1(sc, n, k));
printf("\n");
}
}
int main() {
stirling_cache sc = { 0 };
const int max = 12;
if (!stirling_cache_create(&sc, max)) {
fprintf(stderr, "Out of memory\n");
return 1;
}
print_stirling_numbers(&sc, max);
stirling_cache_destroy(&sc);
return 0;
}
- Output:
Unsigned Stirling numbers of the first kind: n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 2 3 1 4 0 6 11 6 1 5 0 24 50 35 10 1 6 0 120 274 225 85 15 1 7 0 720 1764 1624 735 175 21 1 8 0 5040 13068 13132 6769 1960 322 28 1 9 0 40320 109584 118124 67284 22449 4536 546 36 1 10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1
C++
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <gmpxx.h>
using integer = mpz_class;
class unsigned_stirling1 {
public:
integer get(int n, int k);
private:
std::map<std::pair<int, int>, integer> cache_;
};
integer unsigned_stirling1::get(int n, int k) {
if (k == 0)
return n == 0 ? 1 : 0;
if (k > n)
return 0;
auto p = std::make_pair(n, k);
auto i = cache_.find(p);
if (i != cache_.end())
return i->second;
integer s = get(n - 1, k - 1) + (n - 1) * get(n - 1, k);
cache_.emplace(p, s);
return s;
}
void print_stirling_numbers(unsigned_stirling1& s1, int n) {
std::cout << "Unsigned Stirling numbers of the first kind:\nn/k";
for (int j = 0; j <= n; ++j) {
std::cout << std::setw(j == 0 ? 2 : 10) << j;
}
std::cout << '\n';
for (int i = 0; i <= n; ++i) {
std::cout << std::setw(2) << i << ' ';
for (int j = 0; j <= i; ++j)
std::cout << std::setw(j == 0 ? 2 : 10) << s1.get(i, j);
std::cout << '\n';
}
}
int main() {
unsigned_stirling1 s1;
print_stirling_numbers(s1, 12);
std::cout << "Maximum value of S1(n,k) where n == 100:\n";
integer max = 0;
for (int k = 0; k <= 100; ++k)
max = std::max(max, s1.get(100, k));
std::cout << max << '\n';
return 0;
}
- Output:
Unsigned Stirling numbers of the first kind: n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 2 3 1 4 0 6 11 6 1 5 0 24 50 35 10 1 6 0 120 274 225 85 15 1 7 0 720 1764 1624 735 175 21 1 8 0 5040 13068 13132 6769 1960 322 28 1 9 0 40320 109584 118124 67284 22449 4536 546 36 1 10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 Maximum value of S1(n,k) where n == 100: 19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000
D
import std.bigint;
import std.functional;
import std.stdio;
alias sterling1 = memoize!sterling1Impl;
BigInt sterling1Impl(int n, int k) {
if (n == 0 && k == 0) {
return BigInt(1);
}
if (n > 0 && k == 0) {
return BigInt(0);
}
if (k > n) {
return BigInt(0);
}
return sterling1(n - 1, k - 1) + (n - 1) * sterling1(n - 1, k);
}
void main() {
writeln("Unsigned Stirling numbers of the first kind:");
int max = 12;
write("n/k");
foreach (n; 0 .. max + 1) {
writef("%10d", n);
}
writeln;
foreach (n; 0 .. max + 1) {
writef("%-3d", n);
foreach (k; 0 .. n + 1) {
writef("%10s", sterling1(n, k));
}
writeln;
}
writeln("The maximum value of S1(100, k) = ");
auto previous = BigInt(0);
foreach (k; 1 .. 101) {
auto current = sterling1(100, k);
if (previous < current) {
previous = current;
} else {
import std.conv;
writeln(previous);
writefln("(%d digits, k = %d)", previous.to!string.length, k - 1);
break;
}
}
}
- Output:
Unsigned Stirling numbers of the first kind: n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 2 3 1 4 0 6 11 6 1 5 0 24 50 35 10 1 6 0 120 274 225 85 15 1 7 0 720 1764 1624 735 175 21 1 8 0 5040 13068 13132 6769 1960 322 28 1 9 0 40320 109584 118124 67284 22449 4536 546 36 1 10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 The maximum value of S1(100, k) = 19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 (158 digits, k = 5)
EasyLang
print "Unsigned Stirling numbers of the first kind:"
len a[] 13 ; arrbase a[] 0
len b[] 13 ; arrbase b[] 0
a[0] = 1
print 1
for n = 1 to 12
b[0] = 0
write 0 & " "
for k = 1 to n
b[k] = a[k - 1] + (n - 1) * a[k]
write b[k] & " "
.
print ""
swap a[] b[]
.
Factor
Here we calculate a row at a time as the coefficients of the falling factorial x(x-1)(x-2)...(x-n+1) using Factor's built-in polynomial arithmetic.
For example, x(x-1)(x-2) = x3 - 3x2 + 2x. Taking the absolute values of the coefficients, the third row is (0) 2 3 1.
USING: arrays assocs formatting io kernel math math.polynomials
math.ranges prettyprint sequences ;
IN: rosetta-code.stirling-first
: stirling-row ( n -- seq )
[ { 1 } ] [
[ -1 ] dip neg [a,b) dup length 1 <array> zip
{ 0 1 } [ p* ] reduce [ abs ] map
] if-zero ;
"Unsigned Stirling numbers of the first kind:" print
"n\\k" write 13 dup [ "%10d" printf ] each-integer nl
[ dup "%-2d " printf stirling-row [ "%10d" printf ] each nl ]
each-integer nl
"Maximum value from 100th stirling row:" print
100 stirling-row supremum .
- Output:
Unsigned Stirling numbers of the first kind: n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 2 3 1 4 0 6 11 6 1 5 0 24 50 35 10 1 6 0 120 274 225 85 15 1 7 0 720 1764 1624 735 175 21 1 8 0 5040 13068 13132 6769 1960 322 28 1 9 0 40320 109584 118124 67284 22449 4536 546 36 1 10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 Maximum value from 100th stirling row: 19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000
FreeBASIC
dim as integer S1(0 to 12, 0 to 12) 'initially set with zeroes
dim as ubyte n, k
dim as string outstr
function padto( i as ubyte, j as integer ) as string
return wspace(i-len(str(j)))+str(j)
end function
S1(0, 0) = 1
for n = 0 to 12 'calculate table
for k = 1 to n
S1(n, k) = S1(n-1, k-1) - (n-1) * S1(n-1, k)
next k
next n
print "Signed Stirling numbers of the first kind"
print
outstr = " k"
for k=0 to 12
outstr += padto(12, k)
next k
print outstr
print " n"
for n = 0 to 12
outstr = padto(2, n)+" "
for k = 0 to 12
outstr += padto(12, S1(n, k))
next k
print outstr
next n
Signed Stirling numbers of the first kind k 0 1 2 3 4 5 6 7 8 9 10 11 12 n 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 2 0 -1 1 0 0 0 0 0 0 0 0 0 0 3 0 2 -3 1 0 0 0 0 0 0 0 0 0 4 0 -6 11 -6 1 0 0 0 0 0 0 0 0 5 0 24 -50 35 -10 1 0 0 0 0 0 0 0 6 0 -120 274 -225 85 -15 1 0 0 0 0 0 0 7 0 720 -1764 1624 -735 175 -21 1 0 0 0 0 0 8 0 -5040 13068 -13132 6769 -1960 322 -28 1 0 0 0 0 9 0 40320 -109584 118124 -67284 22449 -4536 546 -36 1 0 0 0 10 0 -362880 1026576 -1172700 723680 -269325 63273 -9450 870 -45 1 0 0 11 0 3628800 -10628640 12753576 -8409500 3416930 -902055 157773 -18150 1320 -55 1 0 12 0 -39916800 120543840 -150917976 105258076 -45995730 13339535 -2637558 357423 -32670 1925 -66 1
Fōrmulæ
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition.
Programs in Fōrmulæ are created/edited online in its website.
In this page you can see and run the program(s) related to this task and their results. You can also change either the programs or the parameters they are called with, for experimentation, but remember that these programs were created with the main purpose of showing a clear solution of the task, and they generally lack any kind of validation.
Solution
A single solution for signed and unsigned versions is presented. Unsigned version uses 1 as factor, signed version used -1.
Version 1. Recursive
Test case 1. Show the unsigned Stirling numbers of the first kind, S₁(n, k), up to S₁(12, 12)
Test case 2. Show the signed Stirling numbers of the first kind, S₁(n, k), up to S₁(12, 12)
Version 2. Non recursive
A faster, non recursive version is presented. This construct a matrix.
Test case 1. Show the unsigned Stirling numbers of the first kind, S₁(n, k), up to S₁(12, 12)
(the result is the same as recursive version)
Test case 2. Show the signed Stirling numbers of the first kind, S₁(n, k), up to S₁(12, 12)
(the result is the same as recursive version)
Test case 3. Find the maximum value of unsigned S₁(n, k) where n ≤ 100
(the result is the same as recursive version)
Test case 4. Find the maximum value of signed S₁(n, k) where n ≤ 100
Go
package main
import (
"fmt"
"math/big"
)
func main() {
limit := 100
last := 12
unsigned := true
s1 := make([][]*big.Int, limit+1)
for n := 0; n <= limit; n++ {
s1[n] = make([]*big.Int, limit+1)
for k := 0; k <= limit; k++ {
s1[n][k] = new(big.Int)
}
}
s1[0][0].SetInt64(int64(1))
var t big.Int
for n := 1; n <= limit; n++ {
for k := 1; k <= n; k++ {
t.SetInt64(int64(n - 1))
t.Mul(&t, s1[n-1][k])
if unsigned {
s1[n][k].Add(s1[n-1][k-1], &t)
} else {
s1[n][k].Sub(s1[n-1][k-1], &t)
}
}
}
fmt.Println("Unsigned Stirling numbers of the first kind: S1(n, k):")
fmt.Printf("n/k")
for i := 0; i <= last; i++ {
fmt.Printf("%9d ", i)
}
fmt.Printf("\n--")
for i := 0; i <= last; i++ {
fmt.Printf("----------")
}
fmt.Println()
for n := 0; n <= last; n++ {
fmt.Printf("%2d ", n)
for k := 0; k <= n; k++ {
fmt.Printf("%9d ", s1[n][k])
}
fmt.Println()
}
fmt.Println("\nMaximum value from the S1(100, *) row:")
max := new(big.Int).Set(s1[limit][0])
for k := 1; k <= limit; k++ {
if s1[limit][k].Cmp(max) > 0 {
max.Set(s1[limit][k])
}
}
fmt.Println(max)
fmt.Printf("which has %d digits.\n", len(max.String()))
}
- Output:
Unsigned Stirling numbers of the first kind: S1(n, k): n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 ------------------------------------------------------------------------------------------------------------------------------------ 0 1 1 0 1 2 0 1 1 3 0 2 3 1 4 0 6 11 6 1 5 0 24 50 35 10 1 6 0 120 274 225 85 15 1 7 0 720 1764 1624 735 175 21 1 8 0 5040 13068 13132 6769 1960 322 28 1 9 0 40320 109584 118124 67284 22449 4536 546 36 1 10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 Maximum value from the S1(100, *) row: 19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 which has 158 digits.
Haskell
Using library: data-memocombinators for memoization
import Text.Printf (printf)
import Data.List (groupBy)
import qualified Data.MemoCombinators as Memo
stirling1 :: Integral a => (a, a) -> a
stirling1 = Memo.pair Memo.integral Memo.integral f
where
f (n, k)
| n == 0 && k == 0 = 1
| n > 0 && k == 0 = 0
| k > n = 0
| otherwise = stirling1 (pred n, pred k) + pred n * stirling1 (pred n, k)
main :: IO ()
main = do
printf "n/k"
mapM_ (printf "%10d") ([0..12] :: [Int]) >> printf "\n"
printf "%s\n" $ replicate (13 * 10 + 3) '-'
mapM_ (\row -> printf "%2d|" (fst $ head row) >>
mapM_ (printf "%10d" . stirling1) row >> printf "\n") table
printf "\nThe maximum value of S1(100, k):\n%d\n" $
maximum ([stirling1 (100, n) | n <- [1..100]] :: [Integer])
where
table :: [[(Int, Int)]]
table = groupBy (\a b -> fst a == fst b) $ (,) <$> [0..12] <*> [0..12]
Or library: monad-memo for memoization.
{-# LANGUAGE FlexibleContexts #-}
import Text.Printf (printf)
import Data.List (groupBy)
import Control.Monad.Memo (MonadMemo, memo, startEvalMemo)
stirling1 :: (Integral n, MonadMemo (n, n) n m) => (n, n) -> m n
stirling1 (n, k)
| n == 0 && k == 0 = pure 1
| n > 0 && k == 0 = pure 0
| k > n = pure 0
| otherwise = (\f1 f2 -> f1 + pred n * f2) <$>
memo stirling1 (pred n, pred k) <*> memo stirling1 (pred n, k)
stirling1Memo :: Integral n => (n, n) -> n
stirling1Memo = startEvalMemo . stirling1
main :: IO ()
main = do
printf "n/k"
mapM_ (printf "%10d") ([0..12] :: [Int]) >> printf "\n"
printf "%s\n" $ replicate (13 * 10 + 3) '-'
mapM_ (\row -> printf "%2d|" (fst $ head row) >>
mapM_ (printf "%10d" . stirling1Memo) row >> printf "\n") table
printf "\nThe maximum value of S1(100, k):\n%d\n" $
maximum ([stirling1Memo (100, n) | n <- [1..100]] :: [Integer])
where
table :: [[(Int, Int)]]
table = groupBy (\a b -> fst a == fst b) $ (,) <$> [0..12] <*> [0..12]
- Output:
n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 ------------------------------------------------------------------------------------------------------------------------------------- 0| 1 0 0 0 0 0 0 0 0 0 0 0 0 1| 0 1 0 0 0 0 0 0 0 0 0 0 0 2| 0 1 1 0 0 0 0 0 0 0 0 0 0 3| 0 2 3 1 0 0 0 0 0 0 0 0 0 4| 0 6 11 6 1 0 0 0 0 0 0 0 0 5| 0 24 50 35 10 1 0 0 0 0 0 0 0 6| 0 120 274 225 85 15 1 0 0 0 0 0 0 7| 0 720 1764 1624 735 175 21 1 0 0 0 0 0 8| 0 5040 13068 13132 6769 1960 322 28 1 0 0 0 0 9| 0 40320 109584 118124 67284 22449 4536 546 36 1 0 0 0 10| 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 0 0 11| 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 0 12| 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 The maximum value of S1(100, k): 19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000
J
NB. agenda set by the test according to the definition test=: 1 i.~ (0 0&-: , 1 0&-:)@:*@:, , < s1=: 1:`0:`0:`($:&<: + (($: * [)~ <:)~)@.test s1&> table i. 13 +----+------------------------------------------------------------------------------------------+ |s1&>|0 1 2 3 4 5 6 7 8 9 10 11 12| +----+------------------------------------------------------------------------------------------+ | 0 |1 0 0 0 0 0 0 0 0 0 0 0 0| | 1 |0 1 0 0 0 0 0 0 0 0 0 0 0| | 2 |0 1 1 0 0 0 0 0 0 0 0 0 0| | 3 |0 2 3 1 0 0 0 0 0 0 0 0 0| | 4 |0 6 11 6 1 0 0 0 0 0 0 0 0| | 5 |0 24 50 35 10 1 0 0 0 0 0 0 0| | 6 |0 120 274 225 85 15 1 0 0 0 0 0 0| | 7 |0 720 1764 1624 735 175 21 1 0 0 0 0 0| | 8 |0 5040 13068 13132 6769 1960 322 28 1 0 0 0 0| | 9 |0 40320 109584 118124 67284 22449 4536 546 36 1 0 0 0| |10 |0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 0 0| |11 |0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 0| |12 |0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1| +----+------------------------------------------------------------------------------------------+ timespacex 's1&> table i. 13' 0.0242955 12928 NB. memoization greatly helps execution time s1M=: 1:`0:`0:`($:&<: + (($: * [)~ <:)~)@.test M. timespacex 's1M&> table i. 13' 0.000235206 30336 NB. third task >./100 s1M&x:&> i.101 19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000
Java
import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
public class SterlingNumbersFirstKind {
public static void main(String[] args) {
System.out.println("Unsigned Stirling numbers of the first kind:");
int max = 12;
System.out.printf("n/k");
for ( int n = 0 ; n <= max ; n++ ) {
System.out.printf("%10d", n);
}
System.out.printf("%n");
for ( int n = 0 ; n <= max ; n++ ) {
System.out.printf("%-3d", n);
for ( int k = 0 ; k <= n ; k++ ) {
System.out.printf("%10s", sterling1(n, k));
}
System.out.printf("%n");
}
System.out.println("The maximum value of S1(100, k) = ");
BigInteger previous = BigInteger.ZERO;
for ( int k = 1 ; k <= 100 ; k++ ) {
BigInteger current = sterling1(100, k);
if ( current.compareTo(previous) > 0 ) {
previous = current;
}
else {
System.out.printf("%s%n(%d digits, k = %d)%n", previous, previous.toString().length(), k-1);
break;
}
}
}
private static Map<String,BigInteger> COMPUTED = new HashMap<>();
private static final BigInteger sterling1(int n, int k) {
String key = n + "," + k;
if ( COMPUTED.containsKey(key) ) {
return COMPUTED.get(key);
}
if ( n == 0 && k == 0 ) {
return BigInteger.valueOf(1);
}
if ( n > 0 && k == 0 ) {
return BigInteger.ZERO;
}
if ( k > n ) {
return BigInteger.ZERO;
}
BigInteger result = sterling1(n-1, k-1).add(BigInteger.valueOf(n-1).multiply(sterling1(n-1, k)));
COMPUTED.put(key, result);
return result;
}
}
- Output:
Unsigned Stirling numbers of the first kind: n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 2 3 1 4 0 6 11 6 1 5 0 24 50 35 10 1 6 0 120 274 225 85 15 1 7 0 720 1764 1624 735 175 21 1 8 0 5040 13068 13132 6769 1960 322 28 1 9 0 40320 109584 118124 67284 22449 4536 546 36 1 10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 The maximum value of S1(100, k) = 19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 (158 digits, k = 5)
jq
Adapted from Wren
Works with gojq, the Go implementation of jq
The Go implementation of jq supports unbounded-precision integer arithmetic and so the results shown below for max(S(100,k)) are based on a run of gojq.
# For efficiency, define the helper function for `stirling1/2` as a
# top-level function so we can use it directly for constructing the table:
# input: [m,j,cache]
# output: [s, cache]
def stirling1:
. as [$m, $j, $cache]
| "\($m),\($j)" as $key
| $cache
| if has($key) then [.[$key], .]
elif $m == 0 and $j == 0 then [1, .]
elif $m > 0 and $j == 0 then [0, .]
elif $j > $m then [0, .]
else ([$m-1, $j-1, .] | stirling1) as [$s1, $c1]
| ([$m-1, $j, $c1] | stirling1) as [$s2, $c2]
| (($s1 + ($m-1) * $s2)) as $result
| ($c2 | (.[$key] = $result)) as $c3
| [$result, $c3]
end;
def stirling1($n; $k):
[$n, $k, {}] | stirling1 | .[0];
# produce the table for 0 ... $n inclusive
def stirlings($n):
# state: [cache, array_of_results]
reduce range(0; $n+1) as $i ([{}, []];
reduce range(0; $i+1) as $j (.;
. as [$cache, $a]
| ([$i, $j, $cache] | stirling1) as [$s, $c]
| [$c, ($a|setpath([$i,$j]; $s))] ));
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
def task($n):
"Unsigned Stirling numbers of the first kind:",
"n/k \( [range(0;$n+1)|lpad(10)] | join(" "))",
((stirlings($n) | .[1]) as $a
| range(0; $n+1) as $i
| "\($i|lpad(3)): \( [$a[$i][]| lpad(10)] | join(" ") )" ),
"\nThe maximum value of S1(100, k) is",
([stirling1(100; range(0;101)) ] | max) ;
task(12)
- Output:
Unsigned Stirling numbers of the first kind: n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 0: 1 1: 0 1 2: 0 1 1 3: 0 2 3 1 4: 0 6 11 6 1 5: 0 24 50 35 10 1 6: 0 120 274 225 85 15 1 7: 0 720 1764 1624 735 175 21 1 8: 0 5040 13068 13132 6769 1960 322 28 1 9: 0 40320 109584 118124 67284 22449 4536 546 36 1 10: 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 11: 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 12: 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 The maximum value of S1(100, k) is 19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000
Julia
using Combinatorics
const s1cache = Dict()
function stirlings1(n, k, signed::Bool=false)
if signed == true && isodd(n - k)
return -stirlings1(n, k)
elseif haskey(s1cache, Pair(n, k))
return s1cache[Pair(n, k)]
elseif n < 0
throw(DomainError(n, "n must be nonnegative"))
elseif n == k == 0
return one(n)
elseif n == 0 || k == 0
return zero(n)
elseif n == k
return one(n)
elseif k == 1
return factorial(n-1)
elseif k == n - 1
return binomial(n, 2)
elseif k == n - 2
return div((3 * n - 1) * binomial(n, 3), 4)
elseif k == n - 3
return binomial(n, 2) * binomial(n, 4)
end
ret = (n - 1) * stirlings1(n - 1, k) + stirlings1(n - 1, k - 1)
s1cache[Pair(n, k)] = ret
return ret
end
function printstirling1table(kmax)
println(" ", mapreduce(i -> lpad(i, 10), *, 0:kmax))
sstring(n, k) = begin i = stirlings1(n, k); lpad(k > n && i == 0 ? "" : i, 10) end
for n in 0:kmax
println(rpad(n, 2) * mapreduce(k -> sstring(n, k), *, 0:kmax))
end
end
printstirling1table(12)
println("\nThe maximum for stirling1(100, _) is:\n", maximum(k-> stirlings1(BigInt(100), BigInt(k)), 1:100))
- Output:
0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 2 3 1 4 0 6 11 6 1 5 0 24 50 35 10 1 6 0 120 274 225 85 15 1 7 0 720 1764 1624 735 175 21 1 8 0 5040 13068 13132 6769 1960 322 28 1 9 0 40320 109584 118124 67284 22449 4536 546 36 1 10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 The maximum for stirling1(100, _) is: 19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000
Kotlin
import java.math.BigInteger
fun main() {
println("Unsigned Stirling numbers of the first kind:")
val max = 12
print("n/k")
for (n in 0..max) {
print("%10d".format(n))
}
println()
for (n in 0..max) {
print("%-3d".format(n))
for (k in 0..n) {
print("%10s".format(sterling1(n, k)))
}
println()
}
println("The maximum value of S1(100, k) = ")
var previous = BigInteger.ZERO
for (k in 1..100) {
val current = sterling1(100, k)
previous = if (current!! > previous) {
current
} else {
println("$previous\n(${previous.toString().length} digits, k = ${k - 1})")
break
}
}
}
private val COMPUTED: MutableMap<String, BigInteger?> = HashMap()
private fun sterling1(n: Int, k: Int): BigInteger? {
val key = "$n,$k"
if (COMPUTED.containsKey(key)) {
return COMPUTED[key]
}
if (n == 0 && k == 0) {
return BigInteger.valueOf(1)
}
if (n > 0 && k == 0) {
return BigInteger.ZERO
}
if (k > n) {
return BigInteger.ZERO
}
val result = sterling1(n - 1, k - 1)!!.add(BigInteger.valueOf(n - 1.toLong()).multiply(sterling1(n - 1, k)))
COMPUTED[key] = result
return result
}
- Output:
Unsigned Stirling numbers of the first kind: n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 2 3 1 4 0 6 11 6 1 5 0 24 50 35 10 1 6 0 120 274 225 85 15 1 7 0 720 1764 1624 735 175 21 1 8 0 5040 13068 13132 6769 1960 322 28 1 9 0 40320 109584 118124 67284 22449 4536 546 36 1 10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 The maximum value of S1(100, k) = 19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 (158 digits, k = 5)
Lua
do -- show some (unsigned) Stirling numbers of the first kind
local MAX_STIRLING = 12
-- construct a matrix of Stirling numbers up to max n, max n
local s1 = {}
for n = 0, MAX_STIRLING do
s1[ n ] = {}
for k = 0, MAX_STIRLING do s1[ n ][ k ] = 0 end
end
s1[ 0 ][ 0 ] = 1
for n = 1, MAX_STIRLING do s1[ n ][ 0 ] = 0 end
for n = 1, MAX_STIRLING do
for k = 1, n do
local s1Term = ( ( n - 1 ) * s1[ n - 1 ][ k ] )
s1[ n ][ k ] = s1[ n - 1 ][ k - 1 ] + s1Term
end
end
io.write( "Unsigned Stirling numbers of the first kind:\n" )
io.write( " k 0" )
for k = 1, MAX_STIRLING do
io.write( string.format( ( k < 6 and "%10d" or "%9d" ), k ) )
end
io.write( "\n" )
io.write( " n\n" );
for n = 0, MAX_STIRLING do
io.write( string.format( "%2d", n ), string.format( "%3d", s1[ n ][ 0 ] ) )
for k = 1, n do
io.write( string.format( ( k < 6 and "%10d" or "%9d" ), s1[ n ][ k ] ) )
end
io.write( "\n" )
end
end
- Output:
Unsigned Stirling numbers of the first kind: k 0 1 2 3 4 5 6 7 8 9 10 11 12 n 0 1 1 0 1 2 0 1 1 3 0 2 3 1 4 0 6 11 6 1 5 0 24 50 35 10 1 6 0 120 274 225 85 15 1 7 0 720 1764 1624 735 175 21 1 8 0 5040 13068 13132 6769 1960 322 28 1 9 0 40320 109584 118124 67284 22449 4536 546 36 1 10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1
Mathematica / Wolfram Language
TableForm[Array[StirlingS1, {n = 12, k = 12} + 1, {0, 0}], TableHeadings -> {"n=" <> ToString[#] & /@ Range[0, n], "k=" <> ToString[#] & /@ Range[0, k]}]
Max[Abs[StirlingS1[100, #]] & /@ Range[0, 100]]
- Output:
k=0 k=1 k=2 k=3 k=4 k=5 k=6 k=7 k=8 k=9 k=10 k=11 k=12 n=0 1 0 0 0 0 0 0 0 0 0 0 0 0 n=1 0 1 0 0 0 0 0 0 0 0 0 0 0 n=2 0 -1 1 0 0 0 0 0 0 0 0 0 0 n=3 0 2 -3 1 0 0 0 0 0 0 0 0 0 n=4 0 -6 11 -6 1 0 0 0 0 0 0 0 0 n=5 0 24 -50 35 -10 1 0 0 0 0 0 0 0 n=6 0 -120 274 -225 85 -15 1 0 0 0 0 0 0 n=7 0 720 -1764 1624 -735 175 -21 1 0 0 0 0 0 n=8 0 -5040 13068 -13132 6769 -1960 322 -28 1 0 0 0 0 n=9 0 40320 -109584 118124 -67284 22449 -4536 546 -36 1 0 0 0 n=10 0 -362880 1026576 -1172700 723680 -269325 63273 -9450 870 -45 1 0 0 n=11 0 3628800 -10628640 12753576 -8409500 3416930 -902055 157773 -18150 1320 -55 1 0 n=12 0 -39916800 120543840 -150917976 105258076 -45995730 13339535 -2637558 357423 -32670 1925 -66 1 19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000
Nim
A simple implementation using the recursive definition is enough to complete the task.
import sequtils, strutils
proc s1(n, k: Natural): Natural =
if k == 0: return ord(n == 0)
if k > n: return 0
s1(n - 1, k - 1) + (n - 1) * s1(n - 1, k)
echo " k ", toSeq(0..12).mapIt(($it).align(2)).join(" ")
echo " n"
for n in 0..12:
stdout.write ($n).align(2)
for k in 0..n:
stdout.write ($s1(n, k)).align(10)
stdout.write '\n'
- Output:
k 0 1 2 3 4 5 6 7 8 9 10 11 12 n 0 1 1 0 1 2 0 1 1 3 0 2 3 1 4 0 6 11 6 1 5 0 24 50 35 10 1 6 0 120 274 225 85 15 1 7 0 720 1764 1624 735 175 21 1 8 0 5040 13068 13132 6769 1960 322 28 1 9 0 40320 109584 118124 67284 22449 4536 546 36 1 10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1
To find the maximum value of S1(n, k) for n = 100, we need to use a third party library such as “bignum”. But this is not enough. To avoid multiple computation of the same terms, we have to use a cache. Note also that this method has its limits as it depends on the allowed depth of recursion. Here, this is not a problem and the result is obtained almost instantaneously.
import tables
import bignum
var cache: Table[(Natural, Natural), Int]
proc s1(n, k: Natural): Int =
if k == 0: return newInt(ord(n == 0))
if k > n: return newInt(0)
if (n, k) in cache: return cache[(n, k)]
result = s1(n - 1, k - 1) + (n - 1) * s1(n - 1, k)
cache[(n, k)] = result
var max = newInt(-1)
for k in 0..100:
let s = s1(100, k)
if s > max: max = s
else: break
echo "Maximum Stirling number of the first kind with n = 100:"
echo max
- Output:
Maximum Stirling number of the first kind with n = 100: 19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000
Perl
use strict;
use warnings;
use bigint;
use feature 'say';
use feature 'state';
no warnings 'recursion';
use List::Util qw(max);
sub Stirling1 {
my($n, $k) = @_;
return 1 unless $n || $k;
return 0 unless $n && $k;
state %seen;
return ($seen{"{$n-1}|{$k-1}"} //= Stirling1($n-1, $k-1)) +
($seen{"{$n-1}|{$k}" } //= Stirling1($n-1, $k )) * ($n-1)
}
my $upto = 12;
my $width = 1 + length max map { Stirling1($upto,$_) } 0..$upto;
say 'Unsigned Stirling1 numbers of the first kind: S1(n, k):';
print 'n\k' . sprintf "%${width}s"x(1+$upto)."\n", 0..$upto;
for my $row (0..$upto) {
printf '%-3d', $row;
printf "%${width}d", Stirling1($row, $_) for 0..$row;
print "\n";
}
say "\nMaximum value from the S1(100, *) row:";
say max map { Stirling1(100,$_) } 0..100;
- Output:
Unsigned Stirling1 numbers of the first kind: S1(n, k): n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 2 3 1 4 0 6 11 6 1 5 0 24 50 35 10 1 6 0 120 274 225 85 15 1 7 0 720 1764 1624 735 175 21 1 8 0 5040 13068 13132 6769 1960 322 28 1 9 0 40320 109584 118124 67284 22449 4536 546 36 1 10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 Maximum value from the S1(100, *) row: 19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000
Phix
with javascript_semantics include mpfr.e constant lim = 100, lim1 = lim+1, last = 12 bool unsigned = true sequence s1 = repeat(0,lim1) for n=1 to lim1 do s1[n] = mpz_inits(lim1) end for mpz_set_si(s1[1][1],1) mpz {t, m100} = mpz_inits(2) for n=1 to lim do for k=1 to n do mpz_set_si(t,n-1) mpz_mul(t,t,s1[n][k+1]) if unsigned then mpz_add(s1[n+1][k+1],s1[n][k],t) else mpz_sub(s1[n+1][k+1],s1[n][k],t) end if end for end for string s = iff(unsigned?"Uns":"S") printf(1,"%signed Stirling numbers of the first kind: S1(n, k):\n n k:",s) for i=0 to last do printf(1,"%5d ", i) end for printf(1,"\n--- %s\n",repeat('-',last*10+5)) for n=0 to last do printf(1,"%2d ", n) for k=1 to n+1 do printf(1,"%9s ",{mpz_get_str(s1[n+1][k])}) end for printf(1,"\n") end for for k=1 to lim1 do mpz s100k = s1[lim1][k] if mpz_cmp(s100k,m100) > 0 then mpz_set(m100,s100k) end if end for printf(1,"\nThe maximum S1(100,k): %s\n",shorten(mpz_get_str(m100)))
- Output:
Unsigned Stirling numbers of the first kind: S1(n, k): n k: 0 1 2 3 4 5 6 7 8 9 10 11 12 --- ----------------------------------------------------------------------------------------------------------------------------- 0 1 1 0 1 2 0 1 1 3 0 2 3 1 4 0 6 11 6 1 5 0 24 50 35 10 1 6 0 120 274 225 85 15 1 7 0 720 1764 1624 735 175 21 1 8 0 5040 13068 13132 6769 1960 322 28 1 9 0 40320 109584 118124 67284 22449 4536 546 36 1 10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 The maximum S1(100,k): 1971090874705526110...6000000000000000000 (158 digits)
Prolog
:- dynamic stirling1_cache/3.
stirling1(N, N, 1):-!.
stirling1(_, 0, 0):-!.
stirling1(N, K, 0):-
K > N,
!.
stirling1(N, K, L):-
stirling1_cache(N, K, L),
!.
stirling1(N, K, L):-
N1 is N - 1,
K1 is K - 1,
stirling1(N1, K, L1),
stirling1(N1, K1, L2),
!,
L is L2 + (N - 1) * L1,
assertz(stirling1_cache(N, K, L)).
print_stirling_numbers(N):-
between(1, N, K),
stirling1(N, K, L),
writef('%10r', [L]),
fail.
print_stirling_numbers(_):-
nl.
print_stirling_numbers_up_to(M):-
between(1, M, N),
print_stirling_numbers(N),
fail.
print_stirling_numbers_up_to(_).
max_stirling1(N, Max):-
aggregate_all(max(L), (between(1, N, K), stirling1(N, K, L)), Max).
main:-
writeln('Unsigned Stirling numbers of the first kind up to S1(12,12):'),
print_stirling_numbers_up_to(12),
writeln('Maximum value of S1(n,k) where n = 100:'),
max_stirling1(100, M),
writeln(M).
- Output:
Unsigned Stirling numbers of the first kind up to S1(12,12): 1 1 1 2 3 1 6 11 6 1 24 50 35 10 1 120 274 225 85 15 1 720 1764 1624 735 175 21 1 5040 13068 13132 6769 1960 322 28 1 40320 109584 118124 67284 22449 4536 546 36 1 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 Maximum value of S1(n,k) where n = 100: 19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000
PureBasic
EnableExplicit
#MAX=12
#LZ=10
#SP$=" "
Dim s1.i(#MAX,#MAX)
Define n.i,k.i,x.i,s$,esc$
s1(0,0)=1
esc$=#ESC$+"[8;24;170t" ; Enlarges the console window
For n=0 To #MAX
For k=1 To n
s1(n,k)=s1(n-1,k-1)-(n-1)*s1(n-1,k)
Next
Next
If OpenConsole()
Print(esc$)
PrintN(~"Signed Stirling numbers of the first kind\n")
Print(#SP$+"k")
For x=0 To #MAX : Print(#SP$+RSet(Str(x),#LZ)) : Next
PrintN(~"\n n"+LSet("-",13*12,"-"))
For n=0 To #MAX
Print(RSet(Str(n),3))
For k=0 To #MAX : Print(#SP$+RSet(Str(s1(n,k)),#LZ)) : Next
PrintN("")
Next
Input()
EndIf
- Output:
Signed Stirling numbers of the first kind k 0 1 2 3 4 5 6 7 8 9 10 11 12 n------------------------------------------------------------------------------------------------------------------------------------------------------------ 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 2 0 -1 1 0 0 0 0 0 0 0 0 0 0 3 0 2 -3 1 0 0 0 0 0 0 0 0 0 4 0 -6 11 -6 1 0 0 0 0 0 0 0 0 5 0 24 -50 35 -10 1 0 0 0 0 0 0 0 6 0 -120 274 -225 85 -15 1 0 0 0 0 0 0 7 0 720 -1764 1624 -735 175 -21 1 0 0 0 0 0 8 0 -5040 13068 -13132 6769 -1960 322 -28 1 0 0 0 0 9 0 40320 -109584 118124 -67284 22449 -4536 546 -36 1 0 0 0 10 0 -362880 1026576 -1172700 723680 -269325 63273 -9450 870 -45 1 0 0 11 0 3628800 -10628640 12753576 -8409500 3416930 -902055 157773 -18150 1320 -55 1 0 12 0 -39916800 120543840 -150917976 105258076 -45995730 13339535 -2637558 357423 -32670 1925 -66 1
Python
computed = {}
def sterling1(n, k):
key = str(n) + "," + str(k)
if key in computed.keys():
return computed[key]
if n == k == 0:
return 1
if n > 0 and k == 0:
return 0
if k > n:
return 0
result = sterling1(n - 1, k - 1) + (n - 1) * sterling1(n - 1, k)
computed[key] = result
return result
print("Unsigned Stirling numbers of the first kind:")
MAX = 12
print("n/k".ljust(10), end="")
for n in range(MAX + 1):
print(str(n).rjust(10), end="")
print()
for n in range(MAX + 1):
print(str(n).ljust(10), end="")
for k in range(n + 1):
print(str(sterling1(n, k)).rjust(10), end="")
print()
print("The maximum value of S1(100, k) = ")
previous = 0
for k in range(1, 100 + 1):
current = sterling1(100, k)
if current > previous:
previous = current
else:
print("{0}\n({1} digits, k = {2})\n".format(previous, len(str(previous)), k - 1))
break
- Output:
Unsigned Stirling numbers of the first kind: n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 2 3 1 4 0 6 11 6 1 5 0 24 50 35 10 1 6 0 120 274 225 85 15 1 7 0 720 1764 1624 735 175 21 1 8 0 5040 13068 13132 6769 1960 322 28 1 9 0 40320 109584 118124 67284 22449 4536 546 36 1 10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 The maximum value of S1(100, k) = 19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 (158 digits, k = 5)
Quackery
[ dip number$
over size -
space swap of
swap join echo$ ] is justify ( n n --> )
[ table ] is s1table ( n --> n )
[ swap 101 * + s1table ] is s1 ( n n --> n )
101 times
[ i^ 101 times
[ dup i^
[ over 0 =
over 0 = and iff
[ 2drop 1 ] done
over 0 >
over 0 = and iff
[ 2drop 0 ] done
2dup < iff
[ 2drop 0 ] done
2dup 1 - swap
1 - swap s1 unrot
dip [ 1 - dup ]
s1 * + ]
' s1table put ]
drop ]
say "Unsigned Stirling numbers of the first kind."
cr cr
13 times
[ i^ dup 1+ times
[ dup i^ s1
10 justify ]
drop cr ]
cr
0 100 times
[ 100 i^ 1+ s1 max ]
echo cr
- Output:
Unsigned Stirling numbers of the first kind. 1 0 1 0 1 1 0 2 3 1 0 6 11 6 1 0 24 50 35 10 1 0 120 274 225 85 15 1 0 720 1764 1624 735 175 21 1 0 5040 13068 13132 6769 1960 322 28 1 0 40320 109584 118124 67284 22449 4536 546 36 1 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000
Raku
(formerly Perl 6)
sub Stirling1 (Int \n, Int \k) {
return 1 unless n || k;
return 0 unless n && k;
state %seen;
(%seen{"{n - 1}|{k - 1}"} //= Stirling1(n - 1, k - 1)) +
(n - 1) * (%seen{"{n - 1}|{k}"} //= Stirling1(n - 1, k))
}
my $upto = 12;
my $mx = (1..^$upto).map( { Stirling1($upto, $_) } ).max.chars;
put 'Unsigned Stirling numbers of the first kind: S1(n, k):';
put 'n\k', (0..$upto)».fmt: "%{$mx}d";
for 0..$upto -> $row {
$row.fmt('%-3d').print;
put (0..$row).map( { Stirling1($row, $_) } )».fmt: "%{$mx}d";
}
say "\nMaximum value from the S1(100, *) row:";
say (^100).map( { Stirling1 100, $_ } ).max;
- Output:
Unsigned Stirling numbers of the first kind: S1(n, k): n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 2 3 1 4 0 6 11 6 1 5 0 24 50 35 10 1 6 0 120 274 225 85 15 1 7 0 720 1764 1624 735 175 21 1 8 0 5040 13068 13132 6769 1960 322 28 1 9 0 40320 109584 118124 67284 22449 4536 546 36 1 10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 Maximum value from the S1(100, *) row: 19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000
REXX
Some extra code was added to minimize the displaying of the column widths.
/*REXX program to compute and display (unsigned) Stirling numbers of the first kind.*/
parse arg lim . /*obtain optional argument from the CL.*/
if lim=='' | lim=="," then lim= 12 /*Not specified? Then use the default.*/
olim= lim /*save the original value of LIM. */
lim= abs(lim) /*only use the absolute value of LIM. */
numeric digits max(9, 2*lim) /*(over) specify maximum number in grid*/
@.=; @.0.0= 1 /*define the (0, 0)th value in grid*/
do n=0 for lim+1 /* [↓] initialize some values " " */
if n>0 then @.n.0 = 0 /*assign value if N > zero. */
do k=n+1 to lim
@.n.k = 0 /*zero some values in grid if K > N. */
end /*k*/
end /*n*/
max#.= 0 /* [↓] calculate values for the grid. */
do n=1 for lim; nm= n - 1
do k=1 for lim; km= k - 1
@.n.k = @.nm.km + nm * @.nm.k /*calculate an unsigned number in grid.*/
max#.k= max(max#.k, @.n.k) /*find the maximum value " " */
max#.b= max(max#.b, @.n.k) /*find the maximum value for all rows. */
end /*k*/
end /*n*/
do k=1 for lim /*find max column width for each column*/
max#.a= max#.a + length(max#.k)
end /*k*/
/* [↓] only show the maximum value ? */
w= length(max#.b) /*calculate max width of all numbers. */
if olim<0 then do; say 'The maximum value (which has ' w " decimal digits):"
say max#.b /*display maximum number in the grid. */
exit /*stick a fork in it, we're all done. */
end
wi= max(3, length(lim+1) ) /*the maximum width of the grid's index*/
say 'row' center('columns', max(9, max#.a + lim), '═') /*display header of the grid.*/
do r=0 for lim+1; $= /* [↓] display the grid to the term. */
do c=0 for lim+1 until c>=r /*build a row of grid, 1 col at a time.*/
$= $ right(@.r.c, length(max#.c) ) /*append a column to a row of the grid.*/
end /*c*/
say right(r,wi) strip(substr($,2), 'T') /*display a single row of the grid. */
end /*r*/ /*stick a fork in it, we're all done. */
- output when using the default input:
row ════════════════════════════════════════columns═════════════════════════════════════════ 0 1 1 0 1 2 0 1 1 3 0 2 3 1 4 0 6 11 6 1 5 0 24 50 35 10 1 6 0 120 274 225 85 15 1 7 0 720 1764 1624 735 175 21 1 8 0 5040 13068 13132 6769 1960 322 28 1 9 0 40320 109584 118124 67284 22449 4536 546 36 1 10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1
- output when using the input of: -100
(Shown at three-quarter size.)
The maximum value (which has 158 decimal digits): 19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000
RPL
« IF DUP2 AND NOT THEN == ELSE SWAP 1 - DUP ROT DUP2 1 - US1 4 ROLLD US1 * + END » 'US1' STO @ ( n k → unsigned S1(n,k) ) « { 12 12 } 0 CON 1 12 FOR n 1 n FOR k n k 2 →LIST DUP EVAL US1 PUT NEXT NEXT » 'TASK' STO
- Output:
1: [[ 1 0 0 0 0 0 0 0 0 0 0 0 ] [ 1 1 0 0 0 0 0 0 0 0 0 0 ] [ 2 3 1 0 0 0 0 0 0 0 0 0 ] [ 6 11 6 1 0 0 0 0 0 0 0 0 ] [ 24 50 35 10 1 0 0 0 0 0 0 0 ] [ 120 274 225 85 15 1 0 0 0 0 0 0 ] [ 720 1764 1624 735 175 21 1 0 0 0 0 0 ] [ 5040 13068 13132 6769 1960 322 28 1 0 0 0 0 ] [ 40320 109584 118124 67284 22449 4536 546 36 1 0 0 0 ] [ 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 0 0 ] [ 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 0 ] [ 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 ]]
Ruby
$cache = {}
def sterling1(n, k)
if n == 0 and k == 0 then
return 1
end
if n > 0 and k == 0 then
return 0
end
if k > n then
return 0
end
key = [n, k]
if $cache[key] then
return $cache[key]
end
value = sterling1(n - 1, k - 1) + (n - 1) * sterling1(n - 1, k)
$cache[key] = value
return value
end
MAX = 12
def main
print "Unsigned Stirling numbers of the first kind:\n"
print "n/k"
for n in 0 .. MAX
print "%10d" % [n]
end
print "\n"
for n in 0 .. MAX
print "%-3d" % [n]
for k in 0 .. n
print "%10d" % [sterling1(n, k)]
end
print "\n"
end
print "The maximum value of S1(100, k) =\n"
previous = 0
for k in 1 .. 100
current = sterling1(100, k)
if previous < current then
previous = current
else
print previous, "\n"
print "(%d digits, k = %d)\n" % [previous.to_s.length, k - 1]
break
end
end
end
main()
- Output:
Unsigned Stirling numbers of the first kind: n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 2 3 1 4 0 6 11 6 1 5 0 24 50 35 10 1 6 0 120 274 225 85 15 1 7 0 720 1764 1624 735 175 21 1 8 0 5040 13068 13132 6769 1960 322 28 1 9 0 40320 109584 118124 67284 22449 4536 546 36 1 10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 The maximum value of S1(100, k) = 19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 (158 digits, k = 5)
Sidef
func S1(n, k) { # unsigned Stirling numbers of the first kind
stirling(n, k).abs
}
const r = (0..12)
var triangle = r.map {|n| 0..n -> map {|k| S1(n, k) } }
var widths = r.map {|n| r.map {|k| (triangle[k][n] \\ 0).len }.max }
say ('n\k ', r.map {|n| "%*s" % (widths[n], n) }.join(' '))
r.each {|n|
var str = ('%-3s ' % n)
str += triangle[n].map_kv {|k,v| "%*s" % (widths[k], v) }.join(' ')
say str
}
with (100) {|n|
say "\nMaximum value from the S1(#{n}, *) row:"
say { S1(n, _) }.map(^n).max
}
- Output:
n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 2 3 1 4 0 6 11 6 1 5 0 24 50 35 10 1 6 0 120 274 225 85 15 1 7 0 720 1764 1624 735 175 21 1 8 0 5040 13068 13132 6769 1960 322 28 1 9 0 40320 109584 118124 67284 22449 4536 546 36 1 10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 Maximum value from the S1(100, *) row: 19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000
Alternatively, the S1(n,k) function can be defined as:
func S1((0), (0)) { 1 }
func S1(_, (0)) { 0 }
func S1((0), _) { 0 }
func S1(n, k) is cached { S1(n-1, k-1) + (n-1)*S1(n-1, k) }
Tcl
This computes the unsigned Stirling numbers of the first kind. Inspired by Stirling_numbers_of_the_second_kind#Tcl, hence similar to #Java.
proc US1 {n k} {
if {$k == 0} {
return [expr {$n == 0}]
}
if {$n < $k} {
return 0
}
if {$n == $k} {
return 1
}
set nk [list $n $k]
if {[info exists ::US1cache($nk)]} {
return $::US1cache($nk)
}
set n1 [expr {$n - 1}]
set k1 [expr {$k - 1}]
set r [expr {($n1 * [US1 $n1 $k]) + [US1 $n1 $k1]}]
set ::US1cache($nk) $r
}
proc main {} {
puts "Unsigned Stirling numbers of the first kind:"
set max 12 ;# last table line to print
set L 9 ;# space to use for 1 number
puts -nonewline "n\\k"
for {set n 0} {$n <= $max} {incr n} {
puts -nonewline " [format %${L}d $n]"
}
puts ""
for {set n 0} {$n <= $max} {incr n} {
puts -nonewline [format %-3d $n]
for {set k 0} {$k <= $n} {incr k} {
puts -nonewline " [format %${L}s [US1 $n $k]]"
}
puts ""
}
puts "The maximum value of US1(100, k) = "
set previous 0
for {set k 1} {$k <= 100} {incr k} {
set current [US1 100 $k]
if {$current > $previous} {
set previous $current
} else {
puts $previous
puts "([string length $previous] digits, k = [expr {$k-1}])"
break
}
}
}
main
- Output:
Unsigned Stirling numbers of the first kind: n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 2 3 1 4 0 6 11 6 1 5 0 24 50 35 10 1 6 0 120 274 225 85 15 1 7 0 720 1764 1624 735 175 21 1 8 0 5040 13068 13132 6769 1960 322 28 1 9 0 40320 109584 118124 67284 22449 4536 546 36 1 10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 The maximum value of US1(100, k) = 19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 (158 digits, k = 5)
Wren
import "./big" for BigInt
import "./fmt" for Fmt
var computed = {}
var stirling1 // recursive
stirling1 = Fn.new { |n, k|
var key = "%(n),%(k)"
if (computed.containsKey(key)) return computed[key]
if (n == 0 && k == 0) return BigInt.one
if (n > 0 && k == 0) return BigInt.zero
if (k > n) return BigInt.zero
var result = stirling1.call(n-1, k-1) + stirling1.call(n-1, k)*(n-1)
computed[key] = result
return result
}
System.print("Unsigned Stirling numbers of the first kind:")
var max = 12
System.write("n/k")
for (n in 0..max) Fmt.write("$10d", n)
System.print()
for (n in 0..max) {
Fmt.write("$-3d", n)
for (k in 0..n) Fmt.write("$10i", stirling1.call(n, k))
System.print()
}
System.print("The maximum value of S1(100, k) =")
var previous = BigInt.zero
for (k in 1..100) {
var current = stirling1.call(100, k)
if (current > previous) {
previous = current
} else {
Fmt.print("$i\n($d digits, k = $d)", previous, previous.toString.count, k - 1)
break
}
}
- Output:
Unsigned Stirling numbers of the first kind: n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 2 3 1 4 0 6 11 6 1 5 0 24 50 35 10 1 6 0 120 274 225 85 15 1 7 0 720 1764 1624 735 175 21 1 8 0 5040 13068 13132 6769 1960 322 28 1 9 0 40320 109584 118124 67284 22449 4536 546 36 1 10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1 The maximum value of S1(100, k) = 19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000 (158 digits, k = 5)
XPL0
define MAX_STIRLING = 12;
integer S1 ( MAX_STIRLING+1, MAX_STIRLING+1 );
integer N, K, S1Term;
begin
\Construct a matrix of Stirling numbers up to max N, max N
for N := 0 to MAX_STIRLING do begin
for K := 0 to MAX_STIRLING do S1( N, K ) := 0
end; \for_N
S1( 0, 0 ) := 1;
for N := 1 to MAX_STIRLING do S1( N, 0 ) := 0;
for N := 1 to MAX_STIRLING do begin
for K := 1 to N do begin
S1Term := ( ( N - 1 ) * S1( N - 1, K ) );
S1( N, K ) := S1( N - 1, K - 1 ) + S1Term
end \for_K
end; \for_N
\Print the Stirling numbers up to N, K = 12
Text(0, "Unsigned Stirling numbers of the first kind:^m^j K" );
Format(10, 0);
for K := 0 to MAX_STIRLING do RlOut(0, float(K) );
CrLf(0);
Text(0, " N^m^j" );
for N := 0 to MAX_STIRLING do begin
Format(2, 0); RlOut(0, float(N));
Format(10, 0);
for K := 0 to N do begin
RlOut(0, float(S1( N, K )) )
end; \for_K
CrLf(0);
end \for_N
end
- Output:
Unsigned Stirling numbers of the first kind: K 0 1 2 3 4 5 6 7 8 9 10 11 12 N 0 1 1 0 1 2 0 1 1 3 0 2 3 1 4 0 6 11 6 1 5 0 24 50 35 10 1 6 0 120 274 225 85 15 1 7 0 720 1764 1624 735 175 21 1 8 0 5040 13068 13132 6769 1960 322 28 1 9 0 40320 109584 118124 67284 22449 4536 546 36 1 10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1
zkl
fcn stirling1(n,k){
var seen=Dictionary(); // cache for recursion
if(n==k==0) return(1);
if(n==0 or k==0) return(0);
z1,z2 := "%d,%d".fmt(n-1,k-1), "%d,%d".fmt(n-1,k);
if(Void==(s1 := seen.find(z1))){ s1 = seen[z1] = stirling1(n - 1, k - 1) }
if(Void==(s2 := seen.find(z2))){ s2 = seen[z2] = stirling1(n - 1, k) }
(n - 1)*s2 + s1; // n is first to cast to BigInt (if using BigInts)
}
// calculate entire table (cached), find max, find num digits in max
N,mx := 12, [1..N].apply(fcn(n){ [1..n].apply(stirling1.fp(n)) : (0).max(_) }) : (0).max(_);
fmt:="%%%dd".fmt("%d".fmt(mx.numDigits + 1)).fmt; // "%9d".fmt
println("Unsigned Stirling numbers of the first kind: S1(n, k):");
println("n\\k",[0..N].pump(String,fmt));
foreach row in ([0..N]){
println("%3d".fmt(row), [0..row].pump(String, stirling1.fp(row), fmt));
}
- Output:
Unsigned Stirling numbers of the first kind: S1(n, k): n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 1 0 1 2 0 1 1 3 0 2 3 1 4 0 6 11 6 1 5 0 24 50 35 10 1 6 0 120 274 225 85 15 1 7 0 720 1764 1624 735 175 21 1 8 0 5040 13068 13132 6769 1960 322 28 1 9 0 40320 109584 118124 67284 22449 4536 546 36 1 10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1 11 0 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55 1 12 0 39916800 120543840 150917976 105258076 45995730 13339535 2637558 357423 32670 1925 66 1
GNU Multiple Precision Arithmetic Library
var [const] BI=Import("zklBigNum"); // libGMP
N=100;
println("Maximum value from the S1(%d, *) row:".fmt(N));
[1..N].apply(stirling1.fp(BI(N)))
.reduce(fcn(m,n){ m.max(n) }).println();
- Output:
Maximum value from the S1(100, *) row: 19710908747055261109287881673376044669240511161402863823515728791076863288440277983854056472903481625299174865860036734731122707870406148096000000000000000000