The Beauty of Mathematics and the Love of God

N e s t e d M a g i c S q u a r e s
Algorithm by: Samavedula Sita Rama Sastry

Nested Magic Squares are magic squares with the special property that each sub-magic square within the original square is also magical, i.e the rows, columns, and diagonals add up to the same number (although to a number different than the original sum,... obviously)

For example, in the 8 x 8 magic square:

14    56    55    54    53     7     8    13

1     24    16    45    44    43    23    64

63    15    40    26    27    37    50     2

62    48    29    35    34    32    17     3

4     47    33    31    30    36    18    61

5     19    28    38    39    25    46    60

59    42    49    20    21    22    41     6

52     9    10    11    12    58    57    51

the inner 6 x 6 square

24    16    45    44    43    23

15    40    26    27    37    50

48    29    35    34    32    17

47    33    31    30    36    18

19    28    38    39    25    46

42    49    20    21    22    41

is also magical and the magic sum is 195. This nested nature persists all the way to the inner 4 x 4 square.

The page describes an algorithm to generate "nested magic squares" of even and odd sided dimensions. The algorithm was developed by Sri. S. S. R. Sastry. Although the algorithm for generating odd sided magic squares is much simpler, it was the algorithm for even sided magic squares which was developed first. For even sided magic squares, the methodology differs slightly for "double even sided magic squares" (i.e when dimension is divisible by 4) and "single even sided magic squares" (i.e when dimension is divisible by 2 but not by 4).

Tomas Ullrich jr. (tom_ullrich AT hotmail DOT com) has an excellent implementation of this algorithm on in Excel. Download the Excel file or the zipped version of the same.

Matlab files which implement the algorithm are also given.

• Algorithm for odd sided magic squares
• Algorithm for even sided magic squares

A few other Matlab files are provided here as general utilitles:

• ismagic.m: For checking whether a general n x n matrix is a simple magic square (nested-ness and other special properties are not checked). If its not a magic square, returns why not.

·         » help ismagic

·          

·            function [ismag, whynot] = ismagic(square)

·            square: square to be checked for "magicness"

·            ismag: 1 if magical, 0 if not

·            whynot: if ismag == 0, then

·              whynot returns the reason why ismagic fails

·              whynot = 1 : not all elements from 1 to n^2 uniquely used.

·                     = 2 : not all rows and columns add up to the same number

• writemag.m For writing a general n x n matlab matrix as a ASCII file. Useful because the standard save function writes things as double precision digits instead of integers. I'm pretty sure I could have set some options, but small enough function...

·         » help writemag

·          

·              function writemag(magicsquare, fname)

• tablemag.m For generating html tables of magic squares. It also paints each nested square differently to illustrate the nested nature of the square. For example, a 7 x 7 square is rendered as:

• Note however that the html code for the tables tends to be bloated. For example, the 7 x 7 square above takes 64 lines of html to render.

·         » help tablemag

·          

·             function tablemag(magicsquare, fname)

• colorstring.m This file is used by tablemag.m and should be placed in the same directory. This function takes a matlab colormap entry of the form [r g b] where 0 <= r,g,b <= 1 and returns a string which can be used as a colorname string for html documentation.

·         » help colorstring

·          

·             function colstr = colorstring(colarray)

·             takes a matlab colormap entry of the form colarray = [r g b], 

·             where 0 <= r,g,b <= 1 and returns a string which can be used 

·             as a colorvalue attribute in html.

·             For example,

·                 colorstring([0.2, 0.9, 0.6]) = '33e699'

Algorithm for even sided magic squares

Consider the construction of a magic square of dimension n x n where n is divisible by 2. We differentiate between 2 cases. When n is divisble by 4, i.e double even square and when n is not divisible by 4 i.e, single even square. The construction differs only slightly between these 2 cases. In both cases, the middle (n-2) x (n-2) square is filled with (n-2)^2 numbers from the middle of {1,...,n^2}. The periphery of the n x n square is filled with the first 2n-2 and last 2n-2 numbers from {1,...,n^2}. Here we describe how the first 2n-2 numbers i.e, from {1,..., 2n-2} are filled. The last 2n-2 numbers are filled opposing these so that the sum of opposing numbers is 1+n^2.

1. The periphery consists of the following numbers:
• Sp := {1, ..., 2 n - 2 }
• Lp := {n^2 - 2 n + 3, ..., n^2}
2. In the following steps, we describe how to fill the numbers in Sp into the matrix. The numbers in Lp automatically follow in such a way that opposing numbers sum up to n^2 + 1.
3. Place 1 just below the top left corner
4. If n is a single even number i.e, not divisible by 4, then place 2 just to the right of the top left corner.
5. Fill in the next n-3 numbers in a sort of zig-zag pattern as shown in Figures 1 and 2.

0   0   0   0   0   0   0   0

1   0   0   0   0   0   0   0

0   0   0   0   0   0   0   2

0   0   0   0   0   0   0   3

4   0   0   0   0   0   0   0

5   0   0   0   0   0   0   0

0   0   0   0   0   0   0   6

0   0   0   0   0   0   0   0

0   2   0   0   0   0   0   0   0   0

1   0   0   0   0   0   0   0   0   0

0   0   0   0   0   0   0   0   0   3

0   0   0   0   0   0   0   0   0   4

5   0   0   0   0   0   0   0   0   0

6   0   0   0   0   0   0   0   0   0

0   0   0   0   0   0   0   0   0   7

0   0   0   0   0   0   0   0   0   8

9   0   0   0   0   0   0   0   0   0

0   0   0   0   0   0   0   0   0   0

6. Fill in the first and last cells of the first row with the last 2 numbers from Sp. At this stage, we will have:

13  0   0   0   0   0   0  14

1   0   0   0   0   0   0   0

0   0   0   0   0   0   0   2

0   0   0   0   0   0   0   3

4   0   0   0   0   0   0   0

5   0   0   0   0   0   0   0

0   0   0   0   0   0   0   6

0   0   0   0   0   0   0   0

17  2   0   0   0   0   0   0   0  18

1   0   0   0   0   0   0   0   0   0

0   0   0   0   0   0   0   0   0   3

0   0   0   0   0   0   0   0   0   4

5   0   0   0   0   0   0   0   0   0

6   0   0   0   0   0   0   0   0   0

0   0   0   0   0   0   0   0   0   7

0   0   0   0   0   0   0   0   0   8

9   0   0   0   0   0   0   0   0   0

0   0   0   0   0   0   0   0   0   0

7. We are now left with some of the numbers from Sp. These have to be filled into the top and bottom rows of the square such that the following conditions are satisfied:
• An equal number of elements of Sp appear in the top and bottom row. This includes the 2 numbers filled in the top row in the last step, and may also include 2 in the case when n is not divisible by 4.
• The sum of the numbers in the top and bottom row are equal.

This is accomplished using the matlab function distribute as follows:

3. We first calculate how many numbers need to be filled in the bottom row. Call this nlow
4. Calculate how many numbers are remaining from amongst Sp. Call these remain
5. Calculate the number to which the bottom row should add up at this stage. Call this reqdlowsum
6. Start with the largest nlow numbers from amongst remain. Call these numbers selected
7. If sum(selected) > reqdlowsum, move the smallest number of selected to the left till the numbers do add up to reqdlowsum.
8. If the sum cannot be attained by moving the smallest number amongst selected to the very left, move the next smallest number to the left and so on. Keep repeating till the sum is attained.

Once this distribution is done, we will have used up all the "smaller numbers". For the case, n = 8, we will get the following:

14  0   0   0   0   7   8  13

1   0   0   0   0   0   0   0

0   0   0   0   0   0   0   2

0   0   0   0   0   0   0   3

4   0   0   0   0   0   0   0

5   0   0   0   0   0   0   0

0   0   0   0   0   0   0   6

0   9  10  11  12   0   0   0

8. The numbers from Lp are then filled in so that the sum of "opposing" numbers is equal to 1 + n²). This will give:

9.  14  56  55  54  53   7   8  13

10.1    0   0   0   0   0   0  64

11.63   0   0   0   0   0   0   2

12.62   0   0   0   0   0   0   3

13.4    0   0   0   0   0   0  61

14.5    0   0   0   0   0   0  60

15.59   0   0   0   0   0   0   6

16.52   9  10  11  12  58  57  51

17. The algorithm then used recursively to fill in the n-2 x n-2 block of numbers in the middle. In Matlab speak:

18.>> lastsmall = 2*n-2;

19.>> magicsquare(2:n-1, 2:n-1) = evenmagic(n-2) + lastsmall;

Implementation

The following matlab functions implement the algorithm described above:

• evenmagic.m The main algorithm described above.
• distribute.m The algorithm mentioned at the end of step 4.

If you use the matlab files above, please retain the help comments acknowledging the source of the algorithm. I'd also greatly appreciate it if you dropped me a line at srinath_a@usa.net.

Results

The following text files contain some magic squares in plain ascii format. They were tested using the following matlab function ismagic.m

• mag30.txt a 30 x 30 magic square.
• mag40.txt a 40 x 40 magic square.
• mag80.txt a 80 x 80 magic square.

Algorithm for odd sided magic squares

The algorithm for generating odd sided magic squares is much simpler than the one for the even sided magic squares and will directly be explained using 2 examples without any equations. As with the even sided magic squares, because of the nested nature of the square, we only describe the method to fill the periphery. The inner square is filled with a recursize call to the same function. Consider filling a square of dimensions n x n (when n is not divisible by 2)

1. The periphery consists of the following numbers:
• Sp := {1, ..., 2 n - 2 }
• Lp := {n^2 - 2 n + 3, ..., n^2}
2. In the following steps, we describe how to fill the numbers in Sp into the matrix. The numbers in Lp automatically follow in such a way that opposing numbers sum up to n^2 + 1.
3. First we fill in all the odd numbers in Sp in the following manner:
• For n = 9

o    0   0   0   0   0   0   0   0   0

o    1   0   0   0   0   0   0   0   0

o    3   0   0   0   0   0   0   0   0

o    5   0   0   0   0   0   0   0   0

o    0   0   0   0   0   0   0   0   9

o    0   0   0   0   0   0   0   0  11

o    0   0   0   0   0   0   0   0  13

o    0   0   0   0   0   0   0   0  15

o    0   0   0   0   7   0   0   0   0

Here, the odd numbers in Sp are {1,3,...,15}. The middle odd number, 7, is placed at the center of the bottom row. The oddnumbers from {1,...,5} are placed in the first clumn starting from the 2nd row, while the odd numbers after the middle odd number, i.e from {9,11,...,15} are placed in the last column as shown.

• For n = 7, we will have

o    0   0   0   0   0   0   0

o    1   0   0   0   0   0   0

o    3   0   0   0   0   0   0

o    0   0   0   0   0   0   7

o    0   0   0   0   0   0   9

o    0   0   0   0   0   0  11

o    0   0   0   5   0   0   0

Notice that the manner of placing the odd numbers doesnt change from n = 7 to n = 9.

4. The even numbers are then placed in the first and last row as follows:
• The last 2 even numbers in Sp are placed in the first and last cells of the first row as shown (the numbers filled in this step are shown in red):

o    14  0   0   0   0   0   0   0  16       10  0   0   0   0   0  12    

o    1   0   0   0   0   0   0   0   0       1   0   0   0   0   0   0

o    3   0   0   0   0   0   0   0   0       3   0   0   0   0   0   0

o    5   0   0   0   0   0   0   0   0       0   0   0   0   0   0   7

o    0   0   0   0   0   0   0   0   9       0   0   0   0   0   0   9

o    0   0   0   0   0   0   0   0  11       0   0   0   0   0   0  11

o    0   0   0   0   0   0   0   0  13       0   0   0   5   0   0   0

o    0   0   0   0   0   0   0   0  15              (n = 7)

o    0   0   0   0   7   0   0   0   0

o     

o                 (n = 9)

• The remaining even numbers are filled in as shown: (for n = 9)

o    14  0   0   0   0   8  10  12  16 

o    1   0   0   0   0   0   0   0   0

o    3   0   0   0   0   0   0   0   0

o    5   0   0   0   0   0   0   0   0

o    0   0   0   0   0   0   0   0   9 

o    0   0   0   0   0   0   0   0  11 

o    0   0   0   0   0   0   0   0  13 

o    0   0   0   0   0   0   0   0  15 

o    0   2   4   6   7   0   0   0   0

i.e, the first half of the remaining even numbers go in the bottom row while the rest go in the top row as shown above. In exactly the same manner, the remaining even numbers for n = 7

10  0   0   0   6   8  12 

1   0   0   0   0   0   0

3   0   0   0   0   0   0

0   0   0   0   0   0   7 

0   0   0   0   0   0   9 

0   0   0   0   0   0  11 

0   2   4   5   0   0   0

5. At this stage, we have filled in all the numbers in Sp. The remaining peripheral numbers are filled in so that opposing numbers give a total of 1 + n^2.
   For n = 9, we will have:

6.  14  80  78  76  75   8  10  12  16 

7.  1    0   0   0   0   0   0   0  81 

8.  3    0   0   0   0   0   0   0  79 

9.  5    0   0   0   0   0   0   0  77 

10.73   0   0   0   0   0   0   0   9 

11.71   0   0   0   0   0   0   0  11 

12.69   0   0   0   0   0   0   0  13 

13.67   0   0   0   0   0   0   0  15 

14.66   2   4   6   7  74  72  70  68 

15. The inner square of dimension n-2 x n-2 is filled in with a recursive call to the algorithm. In matlab speak,

16.>> lastsmall = 2*n - 2;

17.>> magicsquare(2:n-1, 2:n-1) = oddmagic(n-2) + lastsmall;

The following matlab function implements the algorithm described above:

• oddmagic.m The main algorithm described above.

If you use the matlab files above, please retain the help comments acknowledging the source of the algorithm. I'd also greatly appreciate it if you dropped me a line at srinath_a@usa.net.

Results

The following text files contain some magic squares in plain ascii format.

• mag51.txt a 51 x 51 magic square.
• mag75.txt a 75 x 75 magic square.
• mag99.txt a 99 x 99 magic square.