A 42-digit-long number that mathematicians have been hunting for decades, thanks to its sheer difficulty to calculate, has suddenly been found by two separate groups at the same time. This ninth Dedekind number, as it is known, may be the last in the sequence that is feasible to discover.
Dedekind numbers describe the number of ways a set of logical operations can be combined. For sets of just two or three elements, the total number is easy to calculate by hand, but for larger sets it rapidly becomes impossible because the number grows so quickly, at what is known as a double exponential speed.
鈥淵ou鈥檝e got two to the power two to the power n, as a very rough estimate of the complexity of this system,鈥� says at KU Leuven in Belgium. 鈥淚f you want to find the Dedekind numbers, that is the kind of magnitude of counting that you will have to face.鈥�
Advertisement
The challenge of calculating higher Dedekind numbers has attracted researchers in many disciplines, from pure mathematicians to computer scientists, over the years. 鈥淚t鈥檚 an old, famous problem and, because it鈥檚 hard to crack, it鈥檚 interesting,鈥� says Christian J盲kel at Dresden University of Technology in Germany.
In 1991, mathematician Doug Wiedemann found the eighth Dedekind number using 200 hours of number crunching on the Cray-2 supercomputer, one of the most powerful machines at the time. No one could do any better, until now.
After working on the problem on and off for six years, J盲kel published his calculation for the ninth Dedekind number in early April. Coincidently, Causmaecker and , also at KU Leuven, published their work three days later, having produced the same result. Both groups were unaware of one another. 鈥淚 was shocked, I didn鈥檛 know about their work. I thought it would take at least 10 years or whatever to recompute it,鈥� says J盲kel.
The resulting number is 286,386,577,668,298,411,128,469,151,667,598,498,812,366, which is 42 digits long.
J盲kel鈥檚 calculation took 28 days on eight graphical processing units (GPUs). To reduce the number of calculations required, he multiplied together elements from the much smaller fifth Dedekind number.
Causmaecker and van Hirtum instead used a processor called a field-programmable gate array (FPGA) for their work. Unlike a CPU or a GPU, these can perform many different kinds of interrelated calculations at the same time. 鈥淚n an FPGA, everything is always happening all at once,鈥� says van Hirtum. 鈥淵ou can compare it to a car assembly line.鈥�
Like J盲kel, the team used elements from a smaller Dedekind number, in their case the sixth, but this still required 5.5 quadrillion operations and more than four months of computing time using the Noctua 2 supercomputer at Paderborn University, says van Hirtum.
People are divided on whether another Dedekind number will ever be found. 鈥淭he tenth Dedekind number will be in the realm of 10 to the power of 82, which puts you at the number of atoms in the visible universe, so you can imagine you need something big in technical advancement that also grows exponentially,鈥� says Jakel.
Van Hirtum also thinks the amount of computing power becomes impractical for the next number, requiring trillions more computations which would require capturing the power output of the entire sun. 鈥淭his jump in complexity remains absolutely astronomical,鈥� he says.
Causmaecker, however, is more positive, as he thinks new ways of calculating could bring that requirement down. 鈥淭he combination of exponential growth of computing power, and the power of the mathematical algorithms, will go together and maybe in 20 or 30 years we can compute [Dedekind number] 10.鈥�
Reference: &
