malachite_base/num/arithmetic/
bell_number.rs

1// Copyright © 2026 Mikhail Hogrefe
2//
3// This file is part of Malachite.
4//
5// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
6// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
7// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
8
9use crate::num::arithmetic::traits::{BellNumber, CheckedBellNumber};
10
11// The Bell numbers grow superexponentially, so for every primitive width the entire range of
12// representable values is a short hardcoded table, checked against OEIS A000110.
13const BELL_NUMBERS_U8: [u8; 7] = [1, 1, 2, 5, 15, 52, 203];
14const BELL_NUMBERS_U16: [u16; 10] = [1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147];
15const BELL_NUMBERS_U32: [u32; 16] = [
16    1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322,
17    1382958545,
18];
19const BELL_NUMBERS_U64: [u64; 26] = [
20    1,
21    1,
22    2,
23    5,
24    15,
25    52,
26    203,
27    877,
28    4140,
29    21147,
30    115975,
31    678570,
32    4213597,
33    27644437,
34    190899322,
35    1382958545,
36    10480142147,
37    82864869804,
38    682076806159,
39    5832742205057,
40    51724158235372,
41    474869816156751,
42    4506715738447323,
43    44152005855084346,
44    445958869294805289,
45    4638590332229999353,
46];
47const BELL_NUMBERS_U128: [u128; 43] = [
48    1,
49    1,
50    2,
51    5,
52    15,
53    52,
54    203,
55    877,
56    4140,
57    21147,
58    115975,
59    678570,
60    4213597,
61    27644437,
62    190899322,
63    1382958545,
64    10480142147,
65    82864869804,
66    682076806159,
67    5832742205057,
68    51724158235372,
69    474869816156751,
70    4506715738447323,
71    44152005855084346,
72    445958869294805289,
73    4638590332229999353,
74    49631246523618756274,
75    545717047936059989389,
76    6160539404599934652455,
77    71339801938860275191172,
78    846749014511809332450147,
79    10293358946226376485095653,
80    128064670049908713818925644,
81    1629595892846007606764728147,
82    21195039388640360462388656799,
83    281600203019560266563340426570,
84    3819714729894818339975525681317,
85    52868366208550447901945575624941,
86    746289892095625330523099540639146,
87    10738823330774692832768857986425209,
88    157450588391204931289324344702531067,
89    2351152507740617628200694077243788988,
90    35742549198872617291353508656626642567,
91];
92
93macro_rules! impl_bell_numbers {
94    ($t:ident, $bs:ident) => {
95        impl CheckedBellNumber for $t {
96            /// Computes the $n$th Bell number: the number of ways to partition a set of $n$
97            /// elements.
98            ///
99            /// If the result is too large to be represented, the function returns `None`.
100            ///
101            /// # Worst-case complexity
102            /// Constant time and additional memory.
103            ///
104            /// # Examples
105            /// See [here](super::bell_number#checked_bell_number).
106            #[inline]
107            fn checked_bell_number(n: u64) -> Option<$t> {
108                $bs.get(usize::try_from(n).ok()?).copied()
109            }
110        }
111
112        impl BellNumber for $t {
113            /// Computes the $n$th Bell number: the number of ways to partition a set of $n$
114            /// elements.
115            ///
116            /// # Worst-case complexity
117            /// Constant time and additional memory.
118            ///
119            /// # Panics
120            /// Panics if the result is too large to be represented.
121            ///
122            /// # Examples
123            /// See [here](super::bell_number#bell_number).
124            #[inline]
125            fn bell_number(n: u64) -> $t {
126                $t::checked_bell_number(n).unwrap()
127            }
128        }
129    };
130}
131impl_bell_numbers!(u8, BELL_NUMBERS_U8);
132impl_bell_numbers!(u16, BELL_NUMBERS_U16);
133impl_bell_numbers!(u32, BELL_NUMBERS_U32);
134impl_bell_numbers!(u64, BELL_NUMBERS_U64);
135impl_bell_numbers!(u128, BELL_NUMBERS_U128);
136
137impl CheckedBellNumber for usize {
138    /// Computes the $n$th Bell number: the number of ways to partition a set of $n$ elements.
139    ///
140    /// If the result is too large to be represented, the function returns `None`.
141    ///
142    /// # Worst-case complexity
143    /// Constant time and additional memory.
144    ///
145    /// # Examples
146    /// See [here](super::bell_number#checked_bell_number).
147    #[inline]
148    fn checked_bell_number(n: u64) -> Option<Self> {
149        BELL_NUMBERS_U64
150            .get(Self::try_from(n).ok()?)
151            .and_then(|&b| Self::try_from(b).ok())
152    }
153}
154
155impl BellNumber for usize {
156    /// Computes the $n$th Bell number: the number of ways to partition a set of $n$ elements.
157    ///
158    /// # Worst-case complexity
159    /// Constant time and additional memory.
160    ///
161    /// # Panics
162    /// Panics if the result is too large to be represented.
163    ///
164    /// # Examples
165    /// See [here](super::bell_number#bell_number).
166    #[inline]
167    fn bell_number(n: u64) -> Self {
168        Self::checked_bell_number(n).unwrap()
169    }
170}
malachite_base/num/arithmetic/bell_number.rs

malachite_base/num/arithmetic/
bell_number.rs
