Дедекиндово число

Материал из Циклопедии
Перейти к навигации Перейти к поиску
Не следует путать с дедекиндовыми сечениями — способом построения действительных чисел.
Свободные дистрибутивные решётки монотонных булевых функций от 0, 1, 2 и 3 аргументов с 2, 3, 6 и 20 элементами соответственно

Дедекиндово число — число Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle M(n)} , равное количеству монотонных булевых функций от Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n} переменных. Эквивалентные определения: число антицепей подмножеств Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n} -элементного множества; число элементов в свободной дистрибутивной решётке[en] с Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n} производящими; число абстрактных симплициальных комплексов[en] с Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n} элементами.

Свойства[править]

Последовательность Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \{M(n)\}}  — быстрорастущая, и хотя известны асимптотические оценки Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle M(n)} [1][2][3] и точное выражение в виде суммы[4], но явной вычислительной формулы нет, в связи с чем точное нахождение дедекиндовых чисел остаётся крайне сложной вычислительной задачей; по состоянию на 2023 год точные значения известны для Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n \leqslant 9} [5]:

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, 286386577668298411128469151667598498812366.

Числа от Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle M(0)} до Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle M(4)} вычислил Дедекинд в 1897 году и сформулировал задачу Дедекинда — найти способ вычисления последующих чисел. Число Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle M(5)} вычислил Чёрч в 1940 году[6], результат опроверг гипотезу Биркгофа, что Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle M(n)} всегда делится на Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle (2n-1)(2n-2)} [6]. Числа Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle M(6)} , Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle M(7)} , Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle M(8)} , Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle M(9)} были вычислены соответственно в 1946[7], 1965[8][9], 1991[10] и 2023[11] годах.

Для нахождения Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle M(8)} использовался суперкомпьютер Cray 2[en]. Число Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle M(9)} было получено двумя независимыми группами математиков: Кристиан Якель из Германии применил техники анализа формальных понятий и для вычислительной процедуры использовал графический ускоритель (5311 машиночаса на Nvidia A100[en]); второй группе математиков из Бельгии потребовалось 47 тыс. машиночасов вычислений на ПЛИС Stratix[en] 10 GX под управлением суперкомпьютера Noctua 2[12], занявших около трёх месяцев[13][14]. Обе группы получили одинаковый результат вычислений числа Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle M(9)} , Якель опубликовал препринт на три дня раньше бельгийских коллег.

Если Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n} чётно, то Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle M(n)} также должно быть чётным[15].

Точная формула для вычисления дедекиндовых чисел на основе логического определения антицепей была выведена в 1988 году[4]:

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle M(n)=\sum_{k=1}^{2^{2^n}} \prod_{j=1}^{2^n-1} \prod_{i=0}^{j-1} \left(1-b_i^k b_j^k\prod_{m=0}^{\log_2 i} (1-b_m^i+b_m^i b_m^j)\right)} ,

где Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle b_i^k} является Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle i} -м битом числа Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle k} , который может быть записан с помощью округления вниз:

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle b_i^k=\left\lfloor\frac{k}{2^i}\right\rfloor - 2\left\lfloor\frac{k}{2^{i+1}}\right\rfloor} ,

однако она бесполезна для практического вычисления значений Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle M(n)} для больших Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n} ввиду большого числа членов суммирования.

В 2014 году был найден ещё один вариант формулы, с помощью которой суммированием можно найти дедекиндовы числа:

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle M(n+2)=\sum_{\alpha,\beta\in M_n} \left(|[\bot,\alpha]|2^{C_\alpha,\beta}|[\beta,\top]|\right)}

Эта формула позволяет разложить решетку антицепей на подрешетки в пространствах меньшей размерности.

Логарифм дедекиндова числа можно оценить с помощью границ:

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle {n\choose \lfloor n/2\rfloor}\leqslant \log_2 M(n)\leqslant {n\choose \lfloor n/2\rfloor}\left(1+O\left(\frac{\log n}{n}\right)\right)} ,

где неравенство слева подсчитывает число антицепей, в которых каждое множество имеет в точности Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \lfloor n/2\rfloor} элементов; правая часть неравенства установлена в 1975 году[1].

В 1981 году[2] были даны более точные оценки[16]:

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle M(n)=(1+o(1)) 2^{n\choose \lfloor n/2\rfloor}\exp a(n)}

для чётных Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n} и:

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle M(n)=(1+o(1)) 2^{n\choose \lfloor n/2\rfloor + 1}\exp (b(n)+c(n))}

для нечётных Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n} , где

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle a(n)={n\choose n/2-1}(2^{-n/2} + n^2 2^{-n-5} - n2^{-n-4})} ,
Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle b(n)={n\choose (n-3)/2}(2^{-(n+3)/2} + n^2 2^{-n-6} - n2^{-n-3})} ,
Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle c(n)={n\choose (n-1)/2}(2^{-(n+1)/2} + n^2 2^{-n-4})} .

Основная идея этих оценок заключается в том, что в большинстве антицепей все множества имеют размеры, очень близкие к Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n/2} [16]. Для Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n=2, 4, 6, 8} формула даёт оценку, которая имеет ошибку в 9,8 %, 10,2 %, 4,1 % и −3,3 % соответственно[17].

Пример[править]

Для Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n=2} существует шесть монотонных булевых функций и шесть антицепей подмножеств двухэлементного множества Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \{x,y\}} :

  • функция Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle f(x,y) = \bot} , игнорирующая входные значения и всегда возвращающая Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \bot} , соответствует пустой антицепи Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \varnothing} ;
  • логическая конъюнкция Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle f(x,y)=x\wedge y} соответствует антицепи Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \{\{x,y\}\}} , содержащей единственное множество Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \{x,y\}} ;
  • функция Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle f(x,y)=x} , игнорирующая второй аргумент и возвращающая первый аргумент, соответствует антицепи Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \{\{x\}\}} , содержащей единственное множество Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \{x\}} ;
  • функция Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle f(x,y)=y} , игнорирующая первый аргумент и возвращающая второй аргумент, соответствует антицепи Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \{\{y\}\}} , содержащей единственное множество Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \{y\}} ;
  • логическая дизъюнкция Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle f(x,y)=x \vee y} соответствует антицепи Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \{\{x\},\{y\}\}} , содержащей два множества Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \{x\}} и Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \{y\}} ;
  • функция Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle f(x,y)=\top} , игнорирующая входные значения и всегда возвращающая истинное значение, соответствует антицепи Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \{\varnothing\}} , содержащей только пустое множество.

Источники[править]

  1. ↑ 1,0 1,1 Kleitman, Markowsky, 1975
  2. ↑ 2,0 2,1 Коршунов, 1981
  3. ↑ Kahn, 2002
  4. ↑ 4,0 4,1 Kisielewicz, 1988
  5. ↑ последовательность A000372 в OEIS
  6. ↑ 6,0 6,1 Church, 1940
  7. ↑ Ward, 1946
  8. ↑ Church, 1965
  9. ↑ Berman, Köhler, 1976
  10. ↑ Wiedemann, 1991
  11. ↑ Christian Jäkel A computation of the ninth Dedekind Number // Arxiv.org. — 2023.
  12. ↑ Noctua 2 - BullSequana XH2000, AMD EPYC 7763 64C 2.45GHz, InfiniBand HDR100 | TOP500
  13. ↑ Александр Дубов Математики нашли девятое дедекиндово число. В нем оказалось 42 знака. Это 286386577668298411128469151667598498812366. N + 1 (2023-06-27).
  14. ↑ Lennart Van Hirtum, Patrick De Causmaecker, Jens Goemaere, Tobias Kenter, Heinrich Riebler, Michael Lass, Christian Plessl A computation of D(9) using FPGA Supercomputing.
  15. ↑ Yamamoto, 1953
  16. ↑ 16,0 16,1 Zaguia, 1993
  17. ↑ Brown, K. S., «», <https://www.mathpages.com/home/kmath094/kmath094.htm> 

Литература[править]

  • Joel Berman, Peter Köhler Cardinalities of finite distributive lattices // Mitt. Math. Sem. Giessen. — 1976. — том 121. — С. 103–124.
  • Randolph Church Numerical analysis of certain free distributive structures // Duke Mathematical Journal. — 1940. — том 6. — С. 732–734. — DOI:10.1215/s0012-7094-40-00655-x.
  • Randolph Church Enumeration by rank of the free distributive lattice with 7 generators // Notices of the American Mathematical Society. — 1965. — том 11. — С. 724.. Как процитировано Видерманом (Wiedemann (1991)).
  • Richard Dedekind Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler // Gesammelte Werke. — 1897. — Т. 2. — С. 103–148.
  • Jeff Kahn Entropy, independent sets and antichains: a new approach to Dedekind's problem // Proceedings of the American Mathematical Society. — 2002. — В. 2. — том 130. — С. 371–378. — DOI:10.1090/S0002-9939-01-06058-0
  • Andrzej Kisielewicz A solution of Dedekind's problem on the number of isotone Boolean functions // Journal für die Reine und Angewandte Mathematik. — 1988. — том 386. — С. 139–144. — DOI:10.1515/crll.1988.386.139
  • Kleitman D., Markowsky G. On Dedekind's problem: the number of isotone Boolean functions. II // Transactions of the American Mathematical Society. — 1975. — том 213. — С. 373–390. — DOI:10.2307/1998052.
  • Коршунов А. Д. О числе монотонных булевых функций // Проблемы кибернетики. — 1981. — том 38. — С. 5–108.
  • Morgan Ward Note on the order of free distributive lattices // Bulletin of the American Mathematical Society. — 1946. — том 52. — С. 423. — DOI:10.1090/S0002-9904-1946-08568-7
  • Doug Wiedemann A computation of the eighth Dedekind number // Order[en]. — 1991. — В. 1. — том 8. — С. 5–6. — DOI:10.1007/BF00385808.
  • Koichi Yamamoto Note on the order of free distributive lattices // Science Reports of the Kanazawa University. — 1953. — В. 1. — том 2. — С. 5–6.
  • Nejib Zaguia Isotone maps: enumeration and structure // Finite and Infinite Combinatorics in Sets and Logic (Proc. NATO Advanced Study Inst., Banff, Alberta, Canada, May 4, 1991) / Sauer N. W., Woodrow R. E., Sands B.. — Kluwer Academic Publishers, 1993. — С. 421–430.
 
Классы натуральных чисел
↑
[+]
Степени и
связанные числа

Ахиллесовы • Степени 2 • Степени 10 • Квадраты • Кубы • Четвёртые степени • Пятые степени • Совершенная степень • Полнократное число • Степень простого числа

Числа вида
a × 2b ± 1

Каллена • Двойные числа Мерсенна • Числа Ферма • Мерсенна • Каталана — Мерсенна • Прота • Сабита • Вудала

Другие
полиномиальные
числа

Кэрола • Гильберта • Подходящие числа • Кении • Лейланда • Счастливые числа Эйлера • Репьюниты

Рекурсивно
определённые
числа

Фибоначчи • Якобсталя • Леонардо • Люка • Последовательность Падована • Пелля • Перрина

Множества чисел
со специфичными
свойствами

Кнёделя • Ризеля • Серпинского • Дедекиндово

Выраженные
через суммы

Негипотенузные • Практичные • Главные полупростые • Улама • Вольсенхолма

Полученные
с помощью решета

Счастливые числа

Связанные
с кодами

Миртенса

Фигурные числа
2-мерные
3-мерные
4-мерные
центри-
рованные

пентахорические • треугольные в квадрате

нецентри-
рованные

пентатопные

Псевдопростые

Кармайкла • Каталана • эллиптические • Эйлера • Эйлера — Якоби • Ферма • Фробениуса • Люка • Сомера — Люка • сильные псевдопростые

Комбинаторные
числа

Числа Белла • числа торта • Каталана • Дедекинда • Деланноя • Эйлера • Фусса — Каталана • центральные многоугольные • Лобба • числа Моцкина • Нараяны • Число упорядочений Белла • Числа Шрёдера • Шрёдера — Гиппарха

Арифметические
функции
σ(n)

избыточные • почти совершенные • арифметические • колоссально избыточные • Декарта • гемисовершенные • высокоизбыточные • высокосоставные • гиперсовершенные • мультисовершенные • совершенные • практичные • примитивные избыточные • слегка избыточные • тау-числа • величественные • суперизбыточные • суперсоставные • суперсовершенные

Ω(n)

почти простые • полупростые

φ(n)

высококототиентные • высокототиентные • совершенные тотиентные • слегка тотиентные

s(n)

дружественные • обрученные • недостаточные • полусовершенные

Евклида • Фортуновы числа

По делителям

Вифериха • Фибоначчи — Вифериха • Вольстенхольма • Вильсона

Другие простые
делители или
связанные
с делимостью

Блума • Эрдёша — Вудса • взаимно простые • приятельские • скромные • Джуги • Числа Оре • Люка — Кармайкла • прямоугольные • регулярные • k-грубые • гладкие • компанейские • сфенические • Стёрмера • суперчисла Пуле • Цайзеля

Занимательная
математика
Системы
счисления

автоморфные число • циклические • Осириса • Дьюдени • равноцифровые • экстравагантные • Факторион • Фридмана • довольные • Нивена • Ки́та • Лишрел • сумма с отсутствующей цифрой • Армстронга • палиндромические • панцифровые • паразитные • вредные • магические • первобытные • репдигиты • репьюниты • самопорождённые • самоописательные • Смарандаша — Веллена • строго непалиндромические • перевёртыши • переместительные • триморфные • волнистые • вампиры

последовательность Аронсона • блинные числа

Руниверсалис

Одним из источников, использованных при создании данной статьи, является статья из википроекта «Руниверсалис» («Руни», руни.рф) под названием «Дедекиндово число», расположенная по адресу:

—«https://руни.рф/index.php/Дедекиндово_число»

Материал указанной статьи полностью или частично использован в Циклопедии по лицензии CC BY-SA.

Всем участникам Руниверсалиса предлагается прочитать «Обращение к участникам Руниверсалиса» основателя Циклопедии и «Почему Циклопедия?».

Источник — http://cyclowiki.org/w/index.php?title=Дедекиндово_число&oldid=1720244