Представлено 9-е число Дедекинда

Магистерская диссертация Леннарта Ван Хиртума в KU Leuven превратилась в триумфальный прорыв. Бывший студент компьютерных наук, а ныне научный сотрудник Университета Падерборна, приступил к поиску расшифровки 9-го числа Дедекинда. Эта математическая загадка, которой ученые занимались с 1991 года, теперь разгадана.

Достижение ставит Ван Хиртума и его коллег в эксклюзивную лигу. Ранние номера сериала были обнаружены такими известными личностями, как Ричард Дедекинд, Рэндольф Черч и Морган Уорд. Ван Хиртум размышляет: «Решение D(9) было пугающей задачей, ее осуществимость была под вопросом в течение 32 лет».

От 8-го к 9-му числу Дедекинда: путешествие в вычисления

Восьмое число Дедекинда было найдено в 1991 году с использованием самого мощного суперкомпьютера той эпохи, Cray 2. Вдохновленный этим, Ван Хиртум полагал, что вычисление девятого числа должно быть возможным с помощью современных надежных суперкомпьютеров.

Числа Дедекинда относятся к монотонным булевым функциям. Ван Хиртум сравнивает это с игрой с n-мерным кубом. Задача: подсчитать уникальные красно-белые перекрестки. «Эта задача быстро создает огромные числа; В D(8) уже 23 цифры», — говорит он.

Распутывая D (9): игра с огромными числами

Чтобы понять сложность чисел Дедекинда, рассмотрим легенду о шахматной игре. Игровое поле, заполненное в соответствии с просьбой изобретателя об удвоении зерен, дает 20-значное число, все еще меньшее, чем D (8).

Чтобы раскрыть D(9), Ван Хиртум и его команда использовали метод, разработанный Патриком де Каусмакером, формулу P-коэффициента. Несмотря на свою мощь, он быстро увеличивается в вычислительном времени. «То, что занимает восемь минут для D(8), потребует сотни тысяч лет для D(9)», — объясняет Ван Хиртум.

Преодоление вычислительных барьеров

Ключевым препятствием является быстрый рост формулы. Используя симметрию в формуле, команда сократила члены до «всего» 5,5 × 10 ^ 18, числа, достижимого современными суперкомпьютерами.

Noctua 2, базирующийся в Падерборнском центре параллельных вычислений, обладал необходимой системой FPGA. «Мы хотели поддержать этот лунный проект, — говорит профессор, доктор Кристиан Плессл, глава PC2. После пяти месяцев вычислений команда совершила прорыв 8 марта. Они выявили 42-значное 9-е число Дедекинда: 286386577668298411128469151667598498812366.