The number of magic squares of order 6

User Tools

Site Tools

Trace:
start

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

start [2023/09/06 23:15] – [Codes] minostart [2025/08/15 14:08] (current) – external edit 127.0.0.1
Line 1: Line 1:
-===== The number of magic squares of order six counted up to rotations and reflections. =====+__[[magicsquare6-j|Move to the Japanese page]]__ 
 + 
 +===== The number of magic squares of order six counted up to rotations and reflections =====
 <file - nms6.txt> <file - nms6.txt>
-  17 753 889 189 701 384 304+   17 753 889 197 660 635 632
 </file> </file>
  
-This result is consistent with stochastic estimates 1.7745(16)·10<sup>19</sup>[1] and 1.775392(12)·10<sup>19</sup>[2].+[[https://www.youtube.com/playlist?list=PLO7sVdtn8C_Dg5_JHmelPUmDpI6LZqzBM|YouTube video]] explaining the method to achieve the enumeration.  [[https://ms6.sakura.ne.jp/Manuscript.pdf|manuscript]]  [[https://ms6.sakura.ne.jp/Algorithm.pdf|presentation slides]] 
  
-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.+This number has been confirmed by completing the enumeration twice using hundreds of GPUs provided at cloud resource rental services. Though the number and models of GPUs used varied over time, the initial enumeration took about 80,000 hours of GeForce RTX-4090 and the second enumeration with an improved code took about 54,000 hours.
  
-Because of the extraordinary volume of the calculation, it is not easy to deny a possibility the result is contaminated by accidental errors. I have conducted a preliminary [[crosscheck|cross-check]] trying to exclude such errors and am currently performing a thorough cross-check. I would appreciate confirmations or disputes by others.+As the result of the second enumeration, the initial result 17 753 889 189 701 384 304 
 +obtained in July 2023 was found to be incorrect. More details of the errors are in the next section.
  
 +The result is consistent with stochastic estimates 1.8(2)・10<sup>19</sup>[1], 1.7745(16)·10<sup>19</sup>[2], 1.775392(12)·10<sup>19</sup>[3] and 1.77543(73)·10<sup>19</sup>[4].
 +
 +  - Y. Ohishi, in Japanese, Estimation of number of solutions of 6th order magic square by random sampling, Sugei Puzzle No.177, April 1992
   - K. Pinn and C. Wieczerkowski, Number of Magic Squares From Parallel Tempering Monte Calrlo, International Journal of Modern Physics C, 9 April 1998.    - K. Pinn and C. Wieczerkowski, Number of Magic Squares From Parallel Tempering Monte Calrlo, International Journal of Modern Physics C, 9 April 1998. 
   - W. Trump, [[https://www.trump.de/magic-squares/normal-6/index.html|Estimate of the number of magic squares of order 6]].   - W. Trump, [[https://www.trump.de/magic-squares/normal-6/index.html|Estimate of the number of magic squares of order 6]].
 +  - A. Kitajima and M. Kikuchi, Numerous but Rare: An Exploration of Magic Squares, PROS ONE 10(5) e0125062, 14 May 2015.
 +
 +
 +===== Correction history =====
 +
 +More than a thousand of instances of GPU server were used in the enumeration and some of them were unfortunately faulty and produced wrong results. To find and correct such errors, every subtotal was calculated at least twice and extra counting was done to determine the correct answer when a mismatch happened. There were following two cases where the initial result was incorrect.
 +
 +==== corrected on 2023.09.07 ====
 +
 +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, 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 failures are suspected.
 +
 +As the result of the correction, the number increased by 960(40x24).
 +
 +==== corrected on 2024.02.17 ====
 +
 +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).
 +
 +
  
  
Line 20: Line 46:
  
   * [[Defintion of subsets|Definition of subsets]]   * [[Defintion of subsets|Definition of subsets]]
-  * [[subtotals|List of 4,329 subtotals]] +  * [[subtotals|List of 4,329 subtotals]]  
-  * [[https://ms6.sakura.ne.jp/subsubtotal.txt.gz|List of subsubtotals]] (234MBytes .gz) +    * (3 of subtotals are known to be incorrect, but are kept uncorrected intentionally.) 
- ===== Codes =====+  * [[https://ms6.sakura.ne.jp/subsubtotal.txt.gz|List of subsubtotals]] (234MBytes .gz)  
 +    * (18 of sub-subtoals are known to be incorrect, but are kept uncorrected intentionally.) 
 + ===== Strategies and codes =====
 [[strategies|Strategies in counting magic squares]] [[strategies|Strategies in counting magic squares]]
  
  
- [[ms-20230131.cu|CUDA code]]  + [[ms-20240504.cu|CUDA code]] (corrected on 2023.11.28 and updated on 2024.05.04) 
-  * Counts magic squares of an order 3..6 up to [[https://oeis.org/A266237|M-transformations]]. +  * Counts magic squares of an order from 3 to 6 up to [[https://oeis.org/A266237|M-transformations]]. 
-  * Runs at a typical speed of 2.5G counts/sec on Nvidia GeForce RTX-4090 for order 6.+  * Runs at a typical speed of 3.8G counts/sec (91G magic squares/sec) on Nvidia GeForce RTX-4090 for order 6.
   * Nvidia GPU of Pascal architecture (sm_60) or newer is assumed.    * Nvidia GPU of Pascal architecture (sm_60) or newer is assumed. 
   * Multi GPU systems are supported. **[[https://forums.developer.nvidia.com/t/system-wide-atomic-operation-failure-on-multi-4090-systems/243273| Be cautious, however, when you use a multi-4090 system ]]**.   * Multi GPU systems are supported. **[[https://forums.developer.nvidia.com/t/system-wide-atomic-operation-failure-on-multi-4090-systems/243273| Be cautious, however, when you use a multi-4090 system ]]**.
Line 36: Line 64:
   * The executable takes 0, 2, or 4 parameters. The 1st and the 3rd parameters are just place holders.   * 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''\\     counts all magic squares
-    * ''./a.out //dummy representative_magic_series_in_hex//'' \\    counts magic squares whose representative magic series is equal to a given hex number.+    * ''./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.     * ''./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.     * The code doesn't check the validity of parameters given by users. Invalid parameters will result in a wrong answer or a runtime error.
  
-  * [[ms-20230905.cu|new code]] updated on 2023.09.05 ( 7% faster than the 2023.01.31 version )+  *The code was corrected on 2023.11.28.\\ The code used in the initial enumeration was discovered to contain a mistake related to GPU thread synchronization. Corrected versions of the code were used in the second enumeration. No erroneous result caused by this mistake was found.
  
-[[ms-20230131-m.c|Non-CUDA code in C using pthread]] +[[ms-20230918-m.c|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''   * Compiling and linking: ''gcc -O3 -DNTH=//number_of_threads// ms.c -lpthread -lcrypto''
Line 48: Line 76:
   * Much slower than the CUDA code, but easier to read.   * Much slower than the CUDA code, but easier to read.
  
-  *  [[ms-20230905-m.c|new code]] updated on 2023.09.05 ( 30% faster than the 2023.01.31 version )+ ===== Semi-magic squares ===== 
 + 
 +The latest code used in the second enumeration counted semi-magic squares besides magic squares and produced the same result as discovered by a very different approach of A. Ripatti[5]. This match is considered as a cross verification of the counting method and of computing resources used in the calculation. All [[semi_magic_subtotals|subtotals of semi-magic (including magic) squares]] are available. 
 + 
 +  * 5. A. Ripatti, On the number of semi-magic squares of order 6, arXiv:1807.02983, July 2018. 
 + 
 + ===== Acknowledgments =====
  
 +I would like to thank Walter Trump for his discussion, suggestion, and encouragement. He reviewed my method and verified a part of my result using his own code. He suggested me to count semi-magic squares in the second enumeration and encouraged me to complete my work. Visit his website [[https://www.trump.de/magic-squares/index.html|Notes on Magic Squares and Cubes]], which is a good summary of magic square related topics.
  
-===== Time stamps (proof of existence as of 2023-07-18 JST) =====+===== Time stamps =====
  
-  * the number: [[https://ms6.sakura.ne.jp/magicsquare6.txt?linkonly|file]] (Don't copy-paste, download instead.) [[https://ms6.sakura.ne.jp/magicsquare6.txt.ots|timestamp]] +  * The number [[https://ms6.sakura.ne.jp/magicsquare6_20240520.txt|file]] [[https://ms6.sakura.ne.jp/magicsquare6_20240520.txt.ots|timestamp]] 
-  * the CUDA code: [[https://ms6.sakura.ne.jp/ms-20230131.cu|file]] [[https://ms6.sakura.ne.jp/ms-20230131.cu.ots|timestamp]] +  * CUDA code: 2023.05.04 version [[https://ms6.sakura.ne.jp/ms-20240504.cu|file]] [[https://ms6.sakura.ne.jp/ms-20240504.cu.ots|timestamp]] 
-  * the pthread code: [[https://ms6.sakura.ne.jp/ms-20230131-m.c|file]] [[https://ms6.sakura.ne.jp/ms-20230131-m.c.ots|timestamp]]+  * pthread code: 2023.09.18 version [[https://ms6.sakura.ne.jp/ms-20230918-m.c|file]] [[https://ms6.sakura.ne.jp/ms-20230918-m.c.ots|timestamp]]
   * [[https://opentimestamps.org/|verification site]]   * [[https://opentimestamps.org/|verification site]]
  
 --------------------------------- ---------------------------------
-2023/07/18\\ 
  --- //[[hidetoshimino@gmail.com|Hidetoshi Mino]]//, Ph.D.  --- //[[hidetoshimino@gmail.com|Hidetoshi Mino]]//, Ph.D.
 Professor emeritus, University of Yamanashi, Japan Professor emeritus, University of Yamanashi, Japan
start.1694009701.txt.gz · Last modified: 2023/09/06 23:15 by mino
Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki