So can your program also output the decimal square as well?

Printable View

- Jun 3rd 2010, 08:37 AMSamson
- Jun 3rd 2010, 08:52 AMundefined
The following two images should be enough to illustrate the remaining parts of the algorithm.

So, once you have an arrangement for most significant digits, choose the top row of least significant digits, for example:

Attachment 17115

This corresponds with the beginning output of the program, above. (0's stand in for empty slots.)

This is just one of 4! possibilities for the top row; the program is written to exhaustively try all of them. But as it turns out, the very first one produces a regular square.

Now, consider that we only have two options for least significant digit for each cell.

Attachment 17116

To see why, consider the cell in the second row, first column, containing the numbers 1 (blue) 2 3 (red). We can't have 11 because that's already in the first row. And we can't have 10 because we already used 0 as least significant digit in the first row, for that column. So that leaves 12 and 13.

Now, suppose we choose 12 to go into that cell. Then notice that the cell in row 4, column 1 must become 31. Consequently the cell in row 3, column 1 must become 23. Do this throughout the entire square and see that choosing that initial 2 in row 2, column 1, uniquely determines all other cells. The result is the regular square I mentioned above.

As it turns out, there are 24 different initial arrangements of most significant digits. Each of those has 4! possible first rows. Each of those has 2 possible candidate squares.

So the program (if finished) would be finding and testing 24 * 4! * 2 candidates.

The only part I didn't explain is how a candidate can fail to be a regular square. If we follow all the steps above, we are not guaranteed to have all numbers in {0, 1, ..., 15} represented. We have to check the candidates for that property.

For the purposes of counting how many 4 by 4 regular squares exist, we would need to specify whether two squares are equivalent up to permutations of {0,1,2,3}, rotation, reflection. - Jun 3rd 2010, 08:53 AMundefined
- Jun 3rd 2010, 09:14 AMebaines
Regading Q1 - why any "regular square" must also be "magic":

For a base N regular square, the digits 0, 1, 2, ...N-1 must each appear exactly once in the units place for any given row/coumn. Hence the sum of the units digits is (N-1)N/2. Similarly, each digit appears once in the N's column, so it's sum is also (N-1)N/2. Hence the sum of the numbers in any row or column is:

$\displaystyle

\frac {(N-1)} 2 N(N+1)

$

This must be true of all columns, and of all rows. Hence the square is "magic." (However, as noted in the previous discusison about magic squares, this form of "magic square" does not require the diagonals to add to the same number as the rows and columns.) - Jun 3rd 2010, 10:49 AMSamson
- Jun 3rd 2010, 10:54 AMundefined
I don't see why you would want that. But here it is.

Code:`00 05 10 15`

04 00 12 08

08 12 00 04

12 08 04 00

[[], [], [], [], [2, 3], [2, 3], [0, 1], [0, 1], [1, 3], [0, 2], [1, 3], [0, 2], [1, 2], [0, 3], [0, 3], [1, 2]]

00 05 11 14

04 00 12 08

08 12 00 04

12 08 04 00

[[], [], [], [], [2, 3], [2, 3], [0, 1], [0, 1], [1, 2], [0, 3], [1, 2], [0, 3], [1, 3], [0, 2], [0, 2], [1, 3]]

- Jun 3rd 2010, 10:58 AMSamson
Okay! So now I have both the decimal version and the base 4 (base 4 was the first one and your last post is the decimal version of it) ?

- Jun 3rd 2010, 11:07 AMundefined
You seem a bit confused.

My program did**not**output any regular squares. I worked it out on paper while trying the very first candidate (to use as a baseline, as a debugging aid). The first candidate worked, so I didn't bother completing the program.

So, the regular square I provided you is this

Code:`00 11 22 33`

12 03 30 21

23 32 01 10

31 20 13 02

00 05 10 15

06 03 12 09

11 14 01 04

13 08 07 02

Then you asked about output, so I naturally assumed you meant program output, which was near the bottom of that post.

I hope it's clear now. - Jun 4th 2010, 04:45 AMSamson
Okay, well now I'm confused again. Here is what I was looking for in my original post:

Quote:

My book gives example for the 3 dimensional square, but does not give one for 4. Can someone help me find a 4x4 that is regular? I would like to try expressing it in BOTH regular decimal and base-n forms, and for the sake of consistency, I'd like to use a base-4 form. (I can give my example from the book upon request).

Regular Square (Decimal) =

Regular Square (Base 4) =

Sorry for the re-hash, but i'm just a little lost here even though i'm sure what I'm looking for is already in this thread, I just cant decipher it exactly. - Jun 4th 2010, 06:23 AMundefined
- Jun 4th 2010, 08:03 AMSamson
And those are both regular squares? The only reason I ask about clarity is because you said your code did not output regular squares.

- Jun 4th 2010, 08:11 AMundefined
Maybe you don't know what base 4 means...

Code:`Base 4 Base 10`

====== =======

0 0

1 1

2 2

3 3

10 4

11 5

12 6

13 7

20 8

21 9

22 10

23 11

30 12

31 13

32 14

33 15

100 16

My program output is

Code:`00 11 22 33`

10 00 30 20

20 30 00 10

30 20 10 00

[[], [], [], [], [2, 3], [2, 3], [0, 1], [0, 1], [1, 3], [0, 2], [1, 3], [0, 2], [1, 2], [0, 3], [0, 3], [1, 2]]

00 11 23 32

10 00 30 20

20 30 00 10

30 20 10 00

[[], [], [], [], [2, 3], [2, 3], [0, 1], [0, 1], [1, 2], [0, 3], [1, 2], [0, 3], [1, 3], [0, 2], [0, 2], [1, 3]]

**There is no regular square there.**

The regular square I gave you is from work I did on!*PAPER* - Jun 4th 2010, 02:11 PMundefined
After doing some internet research, I've discovered that these objects have been studied by Euler, among others. See this article on Graeco-Latin squares.