The number of magic squares of order 6

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
===== 6次魔方陣の総数 (回転、反転を除く) =====
<file - nms6.txt>
   17 753 889 197 660 635 632
</file>

[[https://www.youtube.com/playlist?list=PLO7sVdtn8C_CkDeblrmFUK370sWDGVUkQ|数え上げ方法の解説YouTubeビデオ]]  
[[https://youtu.be/1DNRZ-eFNgM|より入門的な解説「6次魔方陣を数え上げた話」]] 

この値は数え上げを2回行って確認されています。
数え上げはクラウドサービスが提供する多数のGPUを利用して行われました。
使用された GPUの数やモデルは一定ではありませんが、
最初の数え上げには GeForce RTX-4090 で 80,000時間相当の延べ時間を要し、
2回目の数え上げには、性能改善されたプログラムを使って延べ
 54,000時間を要しました。

2回目の数え上げを行うことにより、2023年7月に発表した最初の結果
 17 753 889 189 701 384 304 は間違っていることがわかりました。
訂正の詳細については次の節をご覧ください。

本結果はこれまでに報告されている以下の統計的な推定値と整合しています。

1.8(2)・10<sup>19</sup>[1], 
1.7745(16)·10<sup>19</sup>[2], 
1.775392(12)·10<sup>19</sup>[3],
1.77543(73)·10<sup>19</sup>[4].

  - 大石 弥幸 「ランダムサンプリングによる6次魔方陣の総数の推定」, 数芸パズル 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. 
  - 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.


===== 訂正の記録 =====

この数え上げを遂行する上で、千を超えるGPUサーバのインスタンスが使用されましたが、そのいくつかは残念なことに問題を抱えており、誤った結果を出しました。そのような誤りを発見し訂正するために、すべての小計は少なくとも2回計算され、不一致が起きたときにはさらに訂正のための計算が追加されました。訂正が必要となったケースは以下の2つです。

==== 2023.09.07に訂正 ====

徹底した検算のなかで、あるインスタンスの結果が正しくないことが発見されました。そのインスタンスは2つのRTX-4090を備えており、約60時間稼働して 3,771個の小小計を生成しました。それらの小小計のうち12個が間違っていましたが、間違っていた答はすべて、2つのRTX-4090のうちの特定の一つだけから生成されていました。このような間違いが論理的な間違いやプログラミングエラーによって起こるとは考えにくく、ハードウェアの不具合が疑われます。

訂正の結果、総計は 960(40x24)増えました。

==== 2024.02.17に訂正 ====

また別のインスタンスに問題がみつかりました。そのインスタンスは一つのRTX-4090を備え、およそ1ヶ月にわたって約 19,000個の小小計を生成しました。それらの小小計のうち、6つが正しくありませんでした。すべての間違った答はこのインスタンスの稼働時間の最後の1時間に生じており、誤った答を生成するようになった後、インスタンスのGPUは "invalid memory access"というエラーメッセシージとともに使えなくなりました。

訂正の結果、総計は 7 959 250 368 (331 635 432 x24)増えました。





===== 小集合の定義と小計 =====

6次魔方陣の総数は膨大であるため、魔方陣全体の集合を細かい小集合に分けて
数え上げます。小集合の定義と小集合ごとの小計を以下に掲載します。

  * [[Defintion of subsets-j|小集合の定義]]
  * [[subtotals|4,329 個の小計]] 
    * (小計のうち、3つは間違っていますが、意図的にそのままにしています。)
  * [[https://ms6.sakura.ne.jp/subsubtotal.txt.gz|小小計のリスト]] (234MBytes .gz) 
    * (小小計のうち、18個は間違っていますが、意図的にそのままにしています。)

===== 数え上げの戦略とプログラム =====
[[strategies-j|魔方陣数え上げの戦略]]


 [[ms-20240504.cu|CUDAプログラム]] (corrected on 2023.11.28 and updated on 2024.05.04)
  * 次数が 3から6の魔方陣の数を数えることができます。[[https://oeis.org/A266237|M-変換]]で生成される分は数えません。
  * Nvidia GeForce RTX-4090 を使った場合、典型的な例では毎秒約3.8G個のスピードで6次魔方陣を数えます。(M-変換の自由度をかけると毎秒91G個)
  * Pascal アーキテクチャ(sm_60) またはそれ以降の Nvidia GPUを想定して書かれています。 
  * マルチGPUシステムもサポートします。ただし、**[[https://forums.developer.nvidia.com/t/system-wide-atomic-operation-failure-on-multi-4090-systems/243273| あるバージョンの Dockerに注意 ]]**してください。
  * コンパイルとリンク: '' nvcc -O3 -arch=sm_60 -maxrregcount=40 -Wno-deprecated-declarations ms.cu -lcrypto ''
    * md5チェクサムが不要な場合は ''-DnoMD5'' オプションをつけてください。その場合 '' -Wno-deprecated-declarations'' と '' -lcrypto'' は不要です。
  * ディフォルトでは 6次魔方陣を数えます。5次以下を数えたい場合は''-DN=//order//''で次数を指定します。
  * 実行ファイルはコマンドライン引数として 0個、2個、4個のいずれかをとりますが、1番目と3番目の引数は意味のないダミーです。   
    * ''./a.out''\\     すべての魔方陣を数えます
    * ''./a.out //dummy 代表魔方組(16進数)//'' \\  与えられた数を代表魔法組とする魔方陣を数える
    * ''./a.out //dummy1 代表魔方組(16進数) dummy2 2番目に大きい魔方組(16進数)//'' \\  指定された代表魔方組と指定された(代表魔法組に並行で)2番目に大きい魔方組を持つ魔方陣を数える
    * プログラムはコマンドライン引数の正当性をチェックしません。不当な引数を与えた場合、意味のない答えを出すか、実行時エラーになるでしょう。

  *2023.11.28 に誤りが修正されました。\\ 最初の数え上げに使われたプログラムにはスレッド同期に関する間違いがありました。2回目の数え上げは修正されたプログラムで行われており、この間違いによって結果に誤りが生じた例は発見されていません。

[[ms-20230918-m.c|pthreadプログラム]] (updated on 2023.09.18)

  * コンパイルとリンク: ''gcc -O3 -DNTH=//スレッド数// ms.c -lpthread -lcrypto''
  * ''-DnoMD5'' と ''-DN=//次数//'' は CUDA版と同じ。
  * CUDAプログラムと比べて遥かに遅いですが、内容は理解しやすいでしょう。

 ===== 準魔方陣(Semi-magic squares) =====

2回目の数え上げでは、魔方陣の数と同時に準魔方陣の数も数えました。その結果は、全く異なる手法で数えられた A. Ripattiによる結果[5]と一致しています。 この一致は2つの手法の正しさを相互に検証しあうものであり、使用されたリソースの健全さを証明するものです。 [[semi_magic_subtotals|準魔方陣の小計]]を掲載します。

  * 5. A. Ripatti, On the number of semi-magic squares of order 6, arXiv:1807.02983, July 2018.

 ===== 謝辞 =====

有益な議論と示唆、激励を与えてくれた Walter Trump氏に感謝します。彼は私の手法を検討し、結果の一部を独自のプログラムで検証してくれました。彼はまた、2回目の数え上げにおいて準魔方陣を数えるよう提案し、私がこのプロジェクトを完遂するよう励ましてくれました。彼のウェブサイト [[https://www.trump.de/magic-squares/index.html|Notes on Magic Squares and Cubes]]は魔方陣に関連するトピックスの良いまとめになっています。

===== Time stamps =====

  * The number [[https://ms6.sakura.ne.jp/magicsquare6_20240520.txt|file]] [[https://ms6.sakura.ne.jp/magicsquare6_20240520.txt.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]]
  * 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]]

---------------------------------
 --- //[[hidetoshimino@gmail.com|美濃 英俊]]// 山梨大学名誉教授 理学博士