sidef-scripts/Math/aitken_s_array.sf

#!/usr/bin/ruby

# Fast algorithm for computing Aitken's array.

# See also:
#   https://oeis.org/A011971 -- Aitken's array
#   https://en.wikipedia.org/wiki/Bell_number

func aitken_array (n) {

    var A = [1]

    [[1]] + (n-1).of {
        A = [A[-1], A...].accumulate
    }
}

func aitken_array_recmap (n) {
    [[1]].recmap {|A|
        A.len >= n ? break : [[A[-1], A...].accumulate]
    }
}

aitken_array(10).each { .say }

assert_eq(aitken_array(10), aitken_array_recmap(10))

__END__
[1]
[1, 2]
[2, 3, 5]
[5, 7, 10, 15]
[15, 20, 27, 37, 52]
[52, 67, 87, 114, 151, 203]
[203, 255, 322, 409, 523, 674, 877]
[877, 1080, 1335, 1657, 2066, 2589, 3263, 4140]
[4140, 5017, 6097, 7432, 9089, 11155, 13744, 17007, 21147]
[21147, 25287, 30304, 36401, 43833, 52922, 64077, 77821, 94828, 115975]