Grogono Photo Pages
Size:  Index   3x3   4x4   5x5   6x6   7x7   8x8   9x9   10x10   11x11   12x12   13x13 

How Many Regular, Prime-Number, Pan-Magic, Squares?

 
This Page: Construction   Latin   Graeco-Latin   Duplicates   Fewest   How Many   Formulae 

Regular, Prime Number, Pan-Magic Squares

Regular prime number, magic squares are constructed in an orderly manner and can be decomposed into magic carpets (Latin squares) with the following properties:

Irregular. Panmagic squares which cannot be decomposed into regularly patterned Latin squares are called Irregular Pan-Magic Squares. Mutsumi Suzuk has recently described Abe Gakuho's construction technique for these squares which he called Pairwise Exchange. Irregular squares are nor further considered here.


How Prime Pan-Magic Squares are Decomposed

Regular prime number pan-magic squares decompose into two Magic Carpets - or Latin Squares if they are presented as letters. Although the smallest magic square (order-3) is not pan-magic it has the advantage that its decomposition is easily visualized. In addition, so can the subsequent assembly of the Latin squares into one Graeco-Latin square.

723
048
561
= 3 x
201
012
120
+
120
012
201
  
  Latin  
Squares:
CAB
ABC
BCA
+
BCA
ABC
CAB
=
CbAcBa
AaBbCc
BcCaAb

The two Latin squares are identical but rotated. They cannot be panmagic because the "Knight's" move is stunted to a 1x1 step and consequently produces diagonals which may be magic but never pan-magic - the broken diagonals cannot add to the magic total. With larger prime number magic squares, there are more options.

This Page: Construction   Latin   Graeco-Latin   Duplicates   Fewest   How Many   Formulae 

How Many Pan-Magic Latin Squares?

Prime number Latin squares are made with "Knight's moves" - two steps forward and one to the side (2x1). A generalized Knight's move consists of any length of step forward and one step to the side, e.g., 1x1, 2x1, 3x1, 4x1, etc. For an order-N magic square, there are N-1 knight's moves and, therefore, N-1 "Orthogonal" Latin Squares:

 

Knight's Moves and Latin Squares for Order-7

ABCDEFG
GABCDEF
FGABCDE
EFGABCD
DEFGABC
CDEFGAB
BCDEFGA
1x1
ABCDEFG
FGABCDE
DEFGABC
BCDEFGA
GABCDEF
EFGABCD
CDEFGAB
2x1
ABCDEFG
EFGABCD
BCDEFGA
FGABCDE
CDEFGAB
GABCDEF
DEFGABC
3x1
ABCDEFG
DEFGABC
GABCDEF
CDEFGAB
FGABCDE
BCDEFGA
EFGABCD
4x1
ABCDEFG
CDEFGAB
EFGABCD
GABCDEF
BCDEFGA
DEFGABC
FGABCDE
5x1
ABCDEFG
BCDEFGA
CDEFGAB
DEFGABC
EFGABCD
FGABCDE
GABCDEF
6x1

Order-7 Latin Squares.

These order-7 Latin squares (above) provide a convenient illustration - big enough but not overwhelming. Of these six Latin squares, the first and last are not pan-magic because their steps produce diagonal rows of letters. Eliminating them leaves four pan-magic Latin squares - 2, 3, 4, and 5. They are mutually orthogonal and can be combined to make "Graeco-Latin" squares. Therefore, the total number of Pan-Magic Latin Squares (L) for prime order N is:

L = N - 3
For order-7:   L = 7 - 3 = 4

While considering the order-7 squares observe that, despite using increasing steps, all four of these pan-magic squares (2, 3, 4, 5) actually contain a 2x1 step in one or other axis. They are a related group. This will be important when we analyze the Fewest Representative Graeco-Latin Squares below.

This Page: Construction   Latin   Graeco-Latin   Duplicates   Fewest   How Many   Formulae 

How Many Graeco-Latin Squares?

A Graeco-Latin square is made from a pair of orthogonal Latin squares. Each one of the L Latin squares can combine with all the others (L - 1). Because L = N - 3, the total number of Graeco-Latin squares (G) is:

G = ( N - 3 ) x ( N - 4)
For order-7:   G = ( 7 - 3 ) x ( 7 - 4 ) = 12

 

How Many Regular Pan-Magic Squares?

To make Magic Squares, numbers are substituted for the letters in each Graeco-Latin square, e.g., in the order-7 square, for the first letter in each cell, the numbers 0 - 6 can be substituted - a total of 7! (= 7x6x5x4x3x2) options. Similar considerations apply to the second letter. For the order-7 square, therefore, there are (7!)2 pan-magic squares for each Graeco-latin square. The total number of Pan-Magic squares (P) is:

P = ( N - 3 ) x ( N - 4) x ( N ! )2
For order-7:   P = ( 7 - 3 ) x ( 7 - 4 ) x ( 7 ! )2 = 304,819,200

This Page: Construction   Latin   Graeco-Latin   Duplicates   Fewest   How Many   Formulae 

Duplicates?

The technique above properly calculates the total number of different pan-magic squares; there are no duplicates if each square is constrained to stay in the same orientation with no translocation.

Huge duplication is apparent when squares are reflected, rotated, and translocated. Just by reflection and rotation, each square is present eight times; and by translocation, these groups of eight appear N2 times. The total number of duplicates (D) is:

D = 8 x N2
For order-7:   D = 8 x 72 = 392

 

Unique Pan-Magic Squares

A Unique Pan-Magic square is a normalised representative of all the duplicates. It is normalised by reflection, rotation, and translocation to put the zero in the top left square, with the smallest possible number beside it, the next smallest possible below it. When duplicates are eliminated, the number of Unique Pan-Magic squares (U) is:

U = ( N - 3 ) x ( N - 4) x ( N ! )2 / ( 8 x N2 ), or:
U = ( N - 3 ) x ( N - 4) x ( (N - 1) ! )2 / 8

For order-7:   U = ( 7 - 3 ) x ( 7 - 4 ) x ( (7-1) ! )2 / 8 = 777,600

 

Sources of Duplication

Translocation. Many of the duplicates arise from using ( N ! ) 2 in the formula for P above, which puts the zero just once in every possible cell. This is avoided by using ( (N - 1) ! ) 2 in the formula for U, the mathematical equivalent of normalising the duplicates and keeping the zero in the top left position.

Reflections and Rotations. These rise from using all possible combinations of Graeco-Latin squares. One Graeco-Latin square produces two copies of each Pan-Magic square - oriented differently. Four related Graeco-Latin squares actually produce four sets of similar pairs - which, betweem them, provide all eight different reflections/rotations of all the squares, i.e., any one of the four is capable of generating a sample of every Unique square.

This Page: Construction   Latin   Graeco-Latin   Duplicates   Fewest   How Many   Formulae 

Fewest Representative Graeco Latin-Squares

Avoid the Duplication. If many of the Graeco-Latin squares produce duplicates, the implied question is: "To represent the pan-magic squares of order-N, what is the fewest number of Graeco-Latin squares required?" For the order-7 square it is a quarter (see paragraph above). However, this is too simplistic. The formula required to calculate the fewest number is more complicated:

Calculate Fewest. The Fewest Representative Pan-Magic squares is the number of Graeco-Latin squares produced when a single representative of each group of related Latin squares is paired with just the remaining Latin squares not already paired. A "group" in this context comprises the Latin squares which contain similar Knight's move, e.g., as described above, the apparently different order-7 pan-magic latin squares all contain the 2x1 jump in different orientations. Any one of the four can, therefore, be chosen and combined with the remaining ones. The Fewest number is:

F = INT( N / 4 ) x ( 2 x N - INT( N / 4 ) - 7 ) / 2
For order-  7:   F = INT(  7 / 4) x (2 x  7 - INT( 7 / 4) -  7 ) / 2 = 1 x ( 14 - 1 -  7 ) / 2 =   3
For order-11:   F = INT(11 / 4) x (2 x 11 - INT(11 / 4) - 7 ) / 2 = 2 x ( 22 - 2 - 7 ) / 2 = 13
For order-13:   F = INT(13 / 4) x (2 x 13 - INT(13 / 4) - 7 ) / 2 = 3 x ( 26 - 3 - 7 ) / 2 = 24

This Page: Construction   Latin   Graeco-Latin   Duplicates   Fewest   How Many   Formulae 

Numbers and Formulae for Regular Prime Number Squares.

The number of Regular Pan-Magic, Latin and Graeco-Latin squares up to order 31 is given in the following table. The table following it summarizes the above formulae.

Numbers: (G-L stands for Graeco-Latin)



Order
Pan-Magic
Latin
Squares
All
G-L
Squares
Fewest
G-L
Squares
Total
Pan-Magic
Squares

Dupli-
cates
Unique
Pan-Magic
Squares
N L G F P D U
5 2 2 1 28800 200 144
7 4 12 3 304,819,200 392 777,600
11 8 56 13 8.92276 x 1016 968 9.21773 x1013
13 10 90 24 3.48982 x 1021 1352 2.58122 x1018
17 14 182 46 2.30254 x 1031 2312 9.95911 x1027
19 16 240 54 3.55140 x 1036 2888 1.22971 x1033
23 20 380 85 2.53964 x 1047 4232 6.00104 x1043
29 26 650 154 5.08148 x 1064 6728 7.55274 x1060
31 28 756 168 5.11169 x 1070 7688 6.64893 x1066

This Page: Construction   Latin   Graeco-Latin   Duplicates   Fewest   How Many   Formulae 

Formulae: (G-L stands for Graeco-Latin)
Order of Magic Square: N
Number of Pan-Magic Latin Squares: L = N - 3
Number of G-L Squares: G = (N - 4) x (N - 3)
Fewest Representative G-L Squares: F = INT( N / 4 ) x ( 2 x N - INT( N / 4 ) - 7 ) / 2
Total Number of Pan-Magic Squares: P = ( N - 3 ) x ( N - 4 ) x ( N ! )2
Number of Duplicate Pan-Magic Squares: D = 8 x N2
Number of Unique Pan-Magic Squares: U = ( N - 3 ) x ( N - 4) x ( (N - 1) ! )2 / 8

Conclusion.

Beyond order-7, the numbers are so vast that the only numbers we can understand are the numbers of Graeco-Latin squares. For the smaller squares the number is easy to visualize and can be fairly readily confirmed. The masses of squares which can be derived from each Graeco-Latin square may all look quite different but they share the underlying Magic Carpets - their Latin Squares. For these reasons, when ennumerating the magic carpets and their product, counting the number of Graeco-Latin squares is more meaningful.

 
 
 
 



Copyright © Mar 2010 Magic Squares
Website
Updated
Mar 6, 2010