The number of magic squares of order 6

nms6.txt

   17 753 889 197 660 635 632 updated  on 2024.02.17 and still to be confirmed.
  (17 753 889 189 701 385 264 updated  on 2023.09.07.)
  (17 753 889 189 701 384 304 reported on 2023.07.18.)

This result is consistent with stochastic estimates 1.7745(16)·10¹⁹[1], 1.775392(12)·10¹⁹[2] and 1.77543(73)·10¹⁹[3].

Using hundreds of GPUs at cloud resource rental services, it took about six months to complete the counting, Though the number and models of GPUs used varied over time, the total computation time amounts to about 80,000 hours of GeForce RTX-4090.

Because of the extraordinary volume of the calculation, it is not easy to deny a possibility that the result is contaminated by accidental errors. I am currently performing a thorough double-check and it is 50% completed. I would appreciate confirmations or disputes by others.

1. K. Pinn and C. Wieczerkowski, Number of Magic Squares From Parallel Tempering Monte Calrlo, International Journal of Modern Physics C, 9 April 1998.
2. W. Trump, Estimate of the number of magic squares of order 6.
3. A. Kitajima and M. Kikuchi, Numerous but Rare: An Exploration of Magic Squares, PROS ONE 10(5) e0125062, 14 May 2015.

In the enumeration, more than five hundreds of instances were created, and some of them were unfortunately faulty and produced wrong results. The followings are such cases I discovered so far by recounting subtotals.

Another erroneous instance was found. It ran with an RTX-4090 for about one month and produced about 19,000 sub-subtotals. Out of those sub-subtotals, 6 were incorrect. All of the incorrect results were produced in the last one hour of the lifetime of the instance. After the erroneous behavior, the GPU of the instance became unusable with an error message of “invalid memory access”.

As the result of the correction, the number increased by 7 959 250 368 (331 635 432 x24).

During the thorough double-check, it was discovered that a portion of the results generated by an instance was incorrect. The instance ran with two RTX-4090s for 60 hours and generated 3,771 sub-subtotals. Out of those sub-subtotals, only 12 were incorrect and all incorrect results were generated by only one of the two RTX-4090s. It is unlikely that these errors are due to logical flaws or coding mistakes. Hardware defects or instability are the most probable causes.

As the result of the correction, the number increased by 960(40×24).

While these errors have not damaged my confidence in the logic and the code used in the calculation, it is possible that errors of similar nature may still be contained in the result. Therefore, the results should be considered unconfirmed until the thorough double-check is completed.

The code used in the initial enumeration was discovered to contain a mistake related to GPU thread synchronization. A corrected version of the code is currently running for the thorough double-check. No discrepancy due to the mistake has been found so far.

Since the number is too huge to count in a single task, the entire task is divided into numerous small sub-tasks. Counts for the sub-tasks are available.

• Definition of subsets
• List of 4,329 subtotals 3 of subtotals are known to be incorrect, but are kept uncorrected intentionally.
• List of subsubtotals (234MBytes .gz) 18 of sub-subtoals are known to be incorrect, but are kept uncorrected intentionally.

Strategies in counting magic squares

CUDA code (corrected on 2023.11.28 and updated on 2024.04.10)

• Counts magic squares of an order from 3 to 6 up to M-transformations.
• Runs at a typical speed of 3.8G counts/sec on Nvidia GeForce RTX-4090 for order 6.
• Nvidia GPU of Pascal architecture (sm_60) or newer is assumed.
• Multi GPU systems are supported. Be cautious, however, when you use a multi-4090 system .
• Compiling and linking: nvcc -O3 -arch=sm_60 -maxrregcount=40 -Wno-deprecated-declarations ms.cu -lcrypto
  • If you don't need md5 checksums, add -DnoMD5 and drop -Wno-deprecated-declarations and -lcrypto.
• For orders less than 6, specify the order by a compiler option -DN=order.
• The executable takes 0, 2, or 4 parameters. The 1st and the 3rd parameters are just place holders.
  • ./a.out
    counts all magic squares
  • ./a.out dummy representative_magic_series_in_hex
    counts magic squares whose representative magic series is equal to the given hex number.
  • ./a.out dummy1 representative_magic_series_in_hex dummy2 2nd_largest_magic_series_in_hex
    counts magic squares whose representative magic series and the 2nd magic series parallel to the representative are as specified.
  • The code doesn't check the validity of parameters given by users. Invalid parameters will result in a wrong answer or a runtime error.

Non-CUDA code in C using pthread (updated on 2023.09.18)

• Compiling and linking: gcc -O3 -DNTH=number_of_threads ms.c -lpthread -lcrypto
• Options -DnoMD5 and -DN=order have the same effects as in the Cuda code.
• Much slower than the CUDA code, but easier to read.

• CUDA code: 2023.04.10 version file timestamp
• pthread code: 2023.09.18 version file timestamp
• verification site

2024/04/10
— Hidetoshi Mino, Ph.D. Professor emeritus, University of Yamanashi, Japan