Edit: As usual, non-messed-up formatting version available here
cryptogenic (adj.): Of unknown origin
cryptogenic (adj.): Of unknown origin
saleratus (n.): bicarbonate of soda: a white soluble compound (NaHCO3) used in effervescent drinks and in baking powders and as an antacid
Pretty cool words today. Anyway, a bit about magic squares:
Magic Squares
A lot of people have played with or at least seen magic squares - arrangements of the numbers 1 through n2 in an nxn grid so that all the rows sum to the same value and all the columns sum to the same value - before. Surprisingly though, very few people know of the easy way to generate large magic squares of any size.
There is a pretty cool, simple algorithm that lets you generate a magic square for an odd value of n. Let's demonstrate it below for n=5.
? ? ? ? ?
? ? ? ? ?
? ? ? ? ?
? ? ? ? ?
1 ? ? ? ?
Start as such, with a 1 in the lower left corner of the square.
? ? ? ? ?
? ? ? ? ?
? 2 ? ? ?
? ? ? ? ?
1 ? ? ? ?
? ? 3 ? ?
? ? ? ? ?
? 2 ? ? ?
? ? ? ? ?
1 ? ? ? ?
.
.
.
? ? 3 ? ?
? ? ? ? 5
? 2 ? ? ?
? ? ? 4 ?
1 ? ? ? ?
As you can see, each time we move one unit to the right and two units up (wrapping around if necessary) to place the next number. At 5 we run into a problem - the next number we'd have to place would coincide with the 1. So we go down instead:
? ? 3 ? ?
? ? ? ? 5
? 2 ? ? 6
? ? ? 4 ?
1 ? ? ? ?
And so on:
? ? 3 ? ?
? ? ? ? 5
? 2 ? ? 6
7 ? ? 4 ?
1 ? ? ? ?
etc.
07 20 03 11 24
13 21 09 17 05
19 02 15 23 06
25 08 16 04 12
01 14 22 10 18
Which happens to be a magic square =). Of course, it doesn't matter where you start with the 1 (because, you can tile the plane with any nxn magic square, take a nxn chunk of the plane, and you'll have a magic square). Even cooler is that moving one to the right and two up is completely arbitrary. In fact, you can always move r to the right and s up - as long as both r and s are relatively prime to n. And we can actually extend it a bit more. We don't necessarily have to move just one unit down after every n moves. Actually, we can move e units right and f units down, and it still works as long as rf-se is relatively prime to n.
Seeing why this is the case is not obvious. However, it helps to see that (we let [x] denote the floor of x):
xj = (a + rj + e[j/n]) mod n
yj = (b + sj + f[j/n]) mod n
Where (xj,yj) is where j+1 is located, and (a,b) is where 1 is located. After this, proving that this method always fills the square with a magic square is really just an exercise in elementary number theory.
So now we have odd squares. What about even squares?
Well, evidently enough if we've found a magic square of size m, and a magic square of size n, we can combine them to get a magic square of size mn. We can find a magic square of size 4 easily enough (the famous Melancolia square, for example), so this saves us for things of the form o*22n. (o is odd, of course). What about sizes like 6, or 8?
Unfortunately there's no 2x2 magic square, so we can't use it to generate these. If we could generate squares of size 2o we could generate magic squares of any size. There are such methods - one very famous method is Conway's LUX method. It's not as simple as the above method but it's not bad - search it on wikipedia if you want.
Of course, what if we want something like... magic cubes? Try adapting the above method to make magic cubes (hint: you'll need to do something after every n2).
There's also something cool known as 'regular' squares. It's quite natural to write the elements of an nxn square in base n. A regular square is one such that the n base n digits appear in the unit's digits of each row and column and in the column's digits of each row and column. Writing our 5x5 above square in base 5 (after we modify it to 0-24), we have:
11 34 02 20 43
22 40 13 31 04
33 01 24 42 10
44 12 30 03 21
00 23 41 14 32
So our square is regular. Turns out it's quite easy to get regular squares for odd n or doubly even n - singly even n are trickier. Euler conjectured that there are no regular squares for any singly even n, but it turned out that there regular squares for all singly even n except 2 and 6 (too bad it was nigh impossible to check 10... it still almost is).
As well, the number of magic squares of size n grows rapidly. For n=1,2,3,4,5 it is 1, 0, 1, 880, 275305224, and no one knows the number of magic squares of size 6. It's estimated at about 1.7745×1019.
That's all for magic squares. In case you haven't heard, Yoda and Darth Vader are in Soul Calibur 4. Also, the first round of the TCHS Tourney was today. I feel a bit stupid for not getting the 1000 pointer, since I should have been able to get it, but I progressed and my rating change was +7, so oh well. The next two rounds are much more important =).
Until next time, ciao.
-squidout
? ? 3 ? ?
? ? ? ? 5
? 2 ? ? 6
? ? ? 4 ?
1 ? ? ? ?
And so on:
? ? 3 ? ?
? ? ? ? 5
? 2 ? ? 6
7 ? ? 4 ?
1 ? ? ? ?
etc.
07 20 03 11 24
13 21 09 17 05
19 02 15 23 06
25 08 16 04 12
01 14 22 10 18
Which happens to be a magic square =). Of course, it doesn't matter where you start with the 1 (because, you can tile the plane with any nxn magic square, take a nxn chunk of the plane, and you'll have a magic square). Even cooler is that moving one to the right and two up is completely arbitrary. In fact, you can always move r to the right and s up - as long as both r and s are relatively prime to n. And we can actually extend it a bit more. We don't necessarily have to move just one unit down after every n moves. Actually, we can move e units right and f units down, and it still works as long as rf-se is relatively prime to n.
Seeing why this is the case is not obvious. However, it helps to see that (we let [x] denote the floor of x):
xj = (a + rj + e[j/n]) mod n
yj = (b + sj + f[j/n]) mod n
Where (xj,yj) is where j+1 is located, and (a,b) is where 1 is located. After this, proving that this method always fills the square with a magic square is really just an exercise in elementary number theory.
So now we have odd squares. What about even squares?
Well, evidently enough if we've found a magic square of size m, and a magic square of size n, we can combine them to get a magic square of size mn. We can find a magic square of size 4 easily enough (the famous Melancolia square, for example), so this saves us for things of the form o*22n. (o is odd, of course). What about sizes like 6, or 8?
Unfortunately there's no 2x2 magic square, so we can't use it to generate these. If we could generate squares of size 2o we could generate magic squares of any size. There are such methods - one very famous method is Conway's LUX method. It's not as simple as the above method but it's not bad - search it on wikipedia if you want.
Of course, what if we want something like... magic cubes? Try adapting the above method to make magic cubes (hint: you'll need to do something after every n2).
There's also something cool known as 'regular' squares. It's quite natural to write the elements of an nxn square in base n. A regular square is one such that the n base n digits appear in the unit's digits of each row and column and in the column's digits of each row and column. Writing our 5x5 above square in base 5 (after we modify it to 0-24), we have:
11 34 02 20 43
22 40 13 31 04
33 01 24 42 10
44 12 30 03 21
00 23 41 14 32
So our square is regular. Turns out it's quite easy to get regular squares for odd n or doubly even n - singly even n are trickier. Euler conjectured that there are no regular squares for any singly even n, but it turned out that there regular squares for all singly even n except 2 and 6 (too bad it was nigh impossible to check 10... it still almost is).
As well, the number of magic squares of size n grows rapidly. For n=1,2,3,4,5 it is 1, 0, 1, 880, 275305224, and no one knows the number of magic squares of size 6. It's estimated at about 1.7745×1019.
That's all for magic squares. In case you haven't heard, Yoda and Darth Vader are in Soul Calibur 4. Also, the first round of the TCHS Tourney was today. I feel a bit stupid for not getting the 1000 pointer, since I should have been able to get it, but I progressed and my rating change was +7, so oh well. The next two rounds are much more important =).
Until next time, ciao.
-squidout
0 comments:
Post a Comment