wsl and VcXsrv (and Cygwin)

wsl is the Windows Subsystem for Linux, a nice way to get apps from X-Windows to work in MS-Windows.

Here you can see the MS-Windows taskbar and icons in the desktop. The terminal in the foreground is running wsl in one of its tabs, but the tab for Cygwin is the one that is open. The X applications that comprise the other windows are all Cygwin.

The way it is supposed to work, is that I configure and run wsl so that both Windows and Linux kernels cooperate together, and then install VcXsrv so that I have a way of running X applications on Windows through my MS-Windows installation. For the record, I am running Windows 10, and WSL 2.

I am still in the process of learning how to configure it. Above you see a screenshot of my desktop running the apps you would expect to have run on a properly-configured wsl/VcXsrv installation: you see xcalc, xterm, and xload. You even get xfig. In the foreground is Windows Terminal, so that doesn’t count. VcXsrv is running with the root window hidden so you can see my Windows Desktop along with the attendant X-Windows applications.

So what’s the problem, you ask? It looks like I have gotten it do do whatever I need it to do, so there is little else to learn. And that, my dear reader is where you are mistaken. Yes, VcXsrv is running X-Windows as it should, but the applications are coming from my Cygwin installation, not from wsl. Setting $DISPLAY to 127.0.0.1:0.0 in Cygwin is enough configuration in Cygwin to get it to send apps to VcXsrv directly from Windows Terminal, over the BASH command line.

I have been trying for the past week to get this to work in wsl without success, but I appear to be succeeding in running Cygwin’s X apps without Cygwin’s X-windows.

Have I gained anything by stumbling on this? Well, I have to say that the X server offered by VcXsrv is faster than Cygwin/X. Cygwin’s X-windows server takes nearly a minute to load, while VcXsrv loads in under a second. One thing that is lost is the ability to launch X running one of the window managers, like mint, KDE or Gnome. With the X desktop as given under VcXsrv, there are no window commands or menus apart from the one that appears in the Windows 10 taskbar icon tray on the right. It is nearly identical to the Cygwin/X menu.

But as it is, it has no commands, and would work better if it wasn’t there at all. So, yes you can hide the desktop, just like you can under Cygwin, and have your X-apps mingle with your Windows 10 apps. They can all be accessed by using Alt+TAB just like any windows 10 application.

I have noticed that the “top” command does something different under an X-based terminal than it does in a Windows 10 terminal. Apart from the usual information, it shows a text-based bar graph of the usage of each core on the CPU, as well as the memory and swap used.

This is Cygwin’s rxvt window running under Windows 10 and X-Windows. Unlike normal “top” on wsl and Linux generally, this one also uses bars to indicate cpu loads and other information. Color is toggled with a keypress on both OS’s, but color is default on Cygwin.

The PRIMM approach to computer science teaching

With research from Sue Sentance’s blog and primmportal.com.

The stages of PRIMM make out its acronym:

  • Predict
  • Run
  • Investigate
  • Modify
  • Make

In the Predict stage, students are given code, and asked to predict its output. This can be done in pairs, and can also be a whole day’s lesson. The code is written by the teacher, and has to be tested ahead of time to eliminate student doubts about syntax or runtime errors. The goal here is to get students to determine the function of a piece of code by looking for clues.

Run is the stage where students test their prediction by running the code. This might involve downloading it to their programming environment. It is meant as a confidence booster, and to take away ownership of errors away from the teacher. While it is possible to copy the code, it is not adviseable, due to typos and time spent typing, especially if the code goes on for dozens of lines.

Investigate could mean code tracing, commenting, flowcharting, labelling concepts or special algorithms, or just answering questions. Working in pairs can help students to work out the details of the code.

The first 3 stages, predict, run, and investigate, could be done many times before students understand the underlying concepts in a secure way. It is not necessarily true that students understand if-else statements or loops after only being shown it once.

In the modify stage, students take a working piece of code and are asked to modify it to do something different. At the start of a course or unit, you should start simply, and progress so that students modify ever larger chunks of code. Transfer of ownership of the code now moves from “not mine” to “partly mine”.

In the make stage, students write the program from scratch. The new program can bear similarites to previous programs. The new program can have similarities to previous programs, but should differ in function, context or problem to solve.

What this allows is scaffolding of learning. Mutual support is had through students working in pairs. This also helps students to articulate particular problems that are going on in the code.

A new 2048-style challenge

Yes, the game 2048 is one of those tablet/cellphone games which also run on a desktop browser which have fascinated numerically-inclined people such as myself. It is a wonderful waste of time, something to do while you are doing something else and actually need to pull yourself away for a few moments and clear your mind by diverting your attention to something else for a bit.

As many of you know, it is normally played on a 4×4 grid. When you search for “2048 game” on the Duck Duck Go search engine, at the top of the selection is a game Duck Duck Go has provided:

Duck Duck Go’s attempt to replicate the “classic” game of 2048

My cellphone app offers me a variety of grid dimensions to play on: 4×4, 5×5, 6×6, and 8×8. The bigger the grid size, the easier it gets to obtain the total 2048. Once you obtain that tile, you win, although you can continue playing. You can play until you have no more room to move or merge your tieles. If you run out of room before you reach 2048, you lose.

The 8×8 tileset is so easy, you can have a mess on the grid and still reach 2048 eventually, with plenty of room left on the board to move your tiles around. So if you are just starting out, you might find it easier to play with the larger boards, eventually graduating to the 4×4 board once you have a clear idea what is going on, and have built a sense of intuition. My version of the game allows you to undo your last turn (but no more than that) in case your last move was less than ideal. It is also useful because sometimes I could swipe right and the tiles move in the wrong direction for some reason. They are supposed to move in the direction of the swipe.

Out of curiosity, I went one size down and tried out the 6×6 mode of the app, and so far, I have two 4096 tiles, and a 16384 tile with no end in sight:

A bit blurry, but there are always a ton of empty squares in this game, and the game board, as you can see is less than ideal for tile distribution. But I’m still getting 16384 and beyond. This same game has been played and stored off and on for the past week.

So, since 2048 is fairly easy on grids beyond 6×6, I began to wonder what numbers could pose a challenge on these larger squares. For 8×8, I think I found what might be a suggestion:

Uhhh, woah.

By the title of this game, they appear to be suggesting that I try to reach a tile labelled “2,147,483,648”, a 10-digit number just over 2 billion. I would be curious to see how they achieved fitting such a number on a tile once it is obtained. But how long would that take? On a 4×4 grid, getting that tile could take a couple of hours, if you get there at all.

The original 2048 suggests that 2048 be the winning tile, which is a power of 2, namely 2^{10}. Taking the base-2 log of 2,147,483,648 on my calculator, I find that this new number is equal to 2^{31}. I am beginning to think that I will need to pass this on to my children in my will, assuming I haven’t lost the game yet.

2147483648 is a game offered currently on GitHub, so it is likely the side project of a professional programmer or a pet project for a hobbyist and could still contain bugs (imagine the nightmare in testing and debugging this game into the high numbers). It appears that the only one developing the project is an anonymous, nameless, faceless programmer going by the handle “jiangtyd”. That said, it seems to come with clever innovations, such as allowing the program to auto-move the tiles on its own to create interesting combinations. You can also change base to something like 3, or increase the tiles by way of the Fibonacci sequence. The “3” selection is a bit lame, in that the successive tiles that need to be formed are really 3\times 2^n, so you are really dealing with powers of 2 again, except in a different way.

A Pet Peeve About the Internet

I have said this several times before in many ways, and I will say it again: there is too much importance placed on the internet. It wouldn’t be so bad if the internet was run by the government, since that would make it more accountable. But instead, it is mostly in the hands of large private companies, who are largely unaccountable, and would not be truthful unless regulators, or the threat of regulation, forces their hand.

This was brought out in all its glory yesterday, as the Canadian telecommunications conglomerate, Rogers, experienced a denial of service nationwide, affecting all internet services. It wasn’t just that families were denied Netflix or YouTube, or that you couldn’t receive email or text messages, it was that the entire economy slowed considerably. Interac stopped working, and that meant that people couldn’t make transactions unless they had cash or credit. All major banks and credit unions use Interac, and thus experienced this problem. But in addition, customers were also not able to do e-transfers or pay bills through their bank.

Many vending machines are hooked up to the internet, and some of them were disabled if they had to connect with a Rogers service. Municipal parking, now dependent on the internet as many cities abandon parking meters, were hobbled as municipalities were not able to accept payment for parking. Toronto’s BikeShareTO service, whcih depends on the internet to distribute bikes to users, had to declare their bikes inaccessible for all stations in Toronto. Vancouver had a similar problem with its bike share program. School boards with summer online programs had to go asynchronous and move its deadlines back another day. Public libraries had a stoppage of WiFi service at many locations, as well as self-checkout machines, and book kiosks.

Many retail stores had to close altogether for the day, as was seen in Mississauga’s Square One Mall and Toronto’s Yorkdale Mall. Many condos and apartments experienced a disabling of their buzzer systems due to the outage.

That wasn’t all. 911 services also stopped working in many areas where the 911 services were managed by Rogers. Chatr Mobile and Fido, offshoot services owned by Rogers, also stopped working. Downstream internet service providers (ISPs) also experienced downtime as a consequence.

It caused the phone lines at the CRTC to go down, since they were using IP telephony provided by Rogers. Of course, this would also be true for any IP telephone, which includes all cell phones served by Rogers or its subsidiaries. These IP telephones also went down in passport offices provided by Service Canada. Rogers also manages the multi-factor authentication systems used by the Canada Revenue Agency, so anyone attempting to log in to the CRA website yesterday could not log in.

One way the internet is oversold is in how we market and use IoT (Interent of Things) devices. Imagine for example, the many forms of digital signage you see around you. A good number of them are connected to the internet, and programmed remotely. Examples are digital highway signs which warn of dangers ahead. So are a good number of household appliances, including televisions and tablets. IoT can also centrally link home security systems, allowing a monotoring service to provide surveillance at low cost as if a security guard was on site. IoT has medical applications, such as providing a way to aid medical professionals to monitor someone who has cardiovascular disease. Some of these things seem pretty essential, but others, such as IoT stoves or refrigerators which are sold to households, not so much. All these would stop working if internet providers had a service stoppage the same way Rogers had done, and these effects would have been already felt with the Rogers denial of service.

Too much is riding on the internet, and too much is riding on only a small handful of service providers. So much so, that we appear to take the internet for granted the way we take water, electricity and sewage for granted. We just assume it works and people are doing their jobs.

But the internet is very different from these other public utilities, in that there are too many variables involved in providing people with decent service. Networks can get hacked, and DDOS attacks are common enough to brandish its own acronym. Weather events happen and can cause regions to have to do without service for some time. As we have seen there are many services, and to have the same provider do them all is like putting all your eggs in the one basket.

It must also be added that the Internet wouldn’t exist without government handouts to the telcoms. It was taxpayer’s money that established the main trunk lines for the internet in the 80s and 90s in Canada and the United States. The infrastructure was practically given away to the major telcoms, and we are now seeing an example of what happens when the internet is controlled by too few companies which are largely unregulated and have little public accountability.

There is more than one major provider in Canada – Bell and Cogeco are other big players that come to mind. But we need more than just a few, so that if a DDOS attack happens, the number of people affected will be limited. Outages such as this can slow down the federal government’s attempt to provide all Canadians with universal high-speed internet by 2030.

With information from The CBC, the Toronto Star, and other websites.

Recreational Math I: Magic Squares: Matters of Primes: Part 7

This article concerns the matter of prime numbers in writing computer programs that generate random magic squares of order n where n is prime. My article, like all the other articles in this series, is aimed at hobbyists.

Suppose you wanted to use the Reichmann (1957) algorithm to generate prime-ordered magic squares of any size n where n ≥ 5. If you asked a user to enter a prime number for the square dimensions, there comes a point where the user won’t exactly know, and shouldn’t be expected to know, if a large number is prime. Could an average person be expected to know, off the top of their head, that 127 is prime, for example? Or what about the number 349,871? Both are prime, but I cheated: I used software. But how does the software do it, since that is what you were trying to write?

We’ll get into the algorithm details in a bit. But the easiest thing to do is to have a detection if a number is not prime. If it isn’t prime, then you can’t use Reichmann’s algorithm, and you then need to ask the user for another (hopefully prime) number that is 5 or more. The user is making at best, quasi-educated guesses. Maybe he knows some powers of 2, and by subtracting 1, he could stumble on a Mersenne prime such as the number 127 mentioned earlier, or 31. Or 7.

Prime numbers are numbers divisible by 1 and itself, and has no other factors. A number like 5 is prime because only 1 and 5 divide it evenly. The same can be said of the number 2, since 1 and 2 are its only factors, making it the only even prime number. Numbers which have more than two factors are called composite numbers. A number like 12 has 1, 2, 3, 4, 6, and 12 as factors, and thus is not prime.

Mersenne primes refer to a special class of primes. They are primes of the general formula 2^p - 1, where the exponent p is also a positive prime number.

A programmer could start with a short list of known primes in an array. Let’s say: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, or the primes from 0 to 100. By the Fundamental Theorem of Arithmetic, a number n is composite if any prime number p \le \lfloor \sqrt{n}\rfloor divides it. The symbols \lfloor,  \rfloor represent the floor function which takes the square root of n and essentially chops off the decimal, returning only the integer part of the number. The array of known primes is thus good up to 100^2 = 10,000.

This is a shortcut, but if the user enters larger numbers than 10,000, you can try numbers beyond the scope of your array. But since the computer program doesn’t know any primes offhand beyond 97, the program could then attempt to check each whole number after 97, sqeuentially up to \lfloor \sqrt{n}\rfloor to see if anything divides n evenly. If none are found, then n is prime.

That’s a whole lot more efficient than checking each integer one by one up to n (or even \lfloor n/2 \rfloor, or half of n with the decimal chopped off) to see what divides n, if anything.

If no upper limit of n is specified to the user, even your more efficient \lfloor \sqrt{n}\rfloor could take hours or days to determine if n is prime, even on a computer considered to be fast. Also, for an n \times n magic square, it would be nice if there were only enough rows and columns to be reasonably displayed on a spreadsheet or console screen. On a spreadsheet, there is always the scrollbar to help you see the numbers that ran off the display. A 101 \times 101 magic square is possible for example, but requires a lot of scrolling to see the 10,201 cells containing the numbers. Today’s computers have lots of memory, so while it is possible to go far beyond even that, there is a matter of practicality. While it might be possible to check the correctness of a 324,773 \times 324,773 magic square programmatically, the 105.5 billion numbers it contains preclude the idea that it can be done on a normal household desktop computer running with 8 gigs of RAM.

Recreational Math I: Magic Squares: the “really good” kind – Part 6

Welcome to part 6, where the magic squares are 7×7. 7 was the number of known planets in medieval times, as well as the number of known elements, and the number of days in the week. The rest is all alchemy.

The algorithm for a 7×7 matrix is the same as for 5×5. In fact, it should work for any odd prime-ordered matrix. Do the first based on a random sequence of the numbers between 1 and 7:

1623475
7516234
3475162
6234751
5162347
4751623
2347516

Now, do the second matrix using 0 and every seventh number after it up to 42:

742021143528
021143528742
143528742021
287420211435
420211435287
211435287420
352874202114

The resulting matrix is magic, but not “hyper-magic” like the 5x5s were:

848224184233
7261541301046
1739351243623
349454281936
4712716383214
2521402913443
3731114952220

The matrix above was done using Excel, and checked using VBA, where I checked it for “magic”. The loss of hypermagic is unfortunate, but I suppose inevitable when you scale up. There are (7!)2 = 25,401,660 magic squares possible by this algorithm. The VBA proved handy later when I used dynamic programming to produce any odd-ordered magic square of any size, and investigated the results.

What if I made a mistake and got the shifting wrong, such as shifting from the second number from the left instead of the right? The result is variable; full magic can only be restored if the rightward diagonal is all 4/s:

7362514
3625147
6251473
2514736
5147362
1473625
4736251

Why does this work? This is because the sum of the numbers 1 to 7 in any order is 28. Notice that whatever number is in the opposite diagonal is repeated 7 times. There is only one number, when multiplied by 7, equals 28, and that is 4. All other numbers will result in a loss of magic. This appears to be a way to maintain magic in all odd-ordered magic squares past order 7. This can possibly generalize for squares of prime order n by taking the middle number (n+1)/2 and making it the main diagonal.

When added to the second preliminary square, both diagonals became magic, as well as the columns and rows. But because the opposite diagonal consists of all 4’s, we lose variety with this restriction, but not by much: 7!6! = 3,628,800. Still enough to occupy you on a rainy day.

9×9 magic squares won’t work so well, because the second square is shifted by 3, which is a number that divides 9. This will result in certain rows repeating in one of the pre-squares; and the result generally is that one of the diagonals won’t total the magic number (369 in this case).

13667859278343846
74552233341541770
26729374912697763
32455316657358216
48156881622522840
64765724536445211
61201313951147280
93543471067756023
42501871795619430

This is a consequence of 9 not being a prime number. The algorithm that works so well for 5×5 and 7×7 magic squares breaks down when the odd number is composite. Thus, the algorithm is known to work for 11×11, 13×13, 17×17, and has been tried all the way to 101×101 and beyond on my Excel spreadsheet.

The magic number can be known in advance of any magic square because an order-n magic square obeys the formula (n × (n2 + 1))/2. The best bet is to look for odd-ordered n × n squares where n is prime. In my VBA program, I made double sure by sticking to magic squares where the order is prime. Here is an 11 × 11 square, where the magic number is 671:

11220608734192331055167
62782429332102527012117
113995231015371120146381
962611050731111364821036
10947741142261841359727
75115215885444942910046
12578654391301035572117
83734903110454691181566
37992810645681191665808
25107487711618567993898
49761131959886408924108

Finally, to stretch things out to the boldly absurd, what about an order-23 square whose magic number is 6095?

92369279275108466226403125327360316554574851419218223442536145524
28327111546121041313132836431156442498171931812324283115951080381
10347321440913832334832162443502121941662454313215850883376297257
22839512633535231769438486222001672494263314352186377296255106468
12933036630357450490182071622334363914452581378281268109469227393
3653016044550441951742374324613950991384282272104470212406132331
6344650321981692514183415151387391277256114476213410127332350314
48815201170250416371465277337928926011048320839413733835131858447
1961712354294014752671382284274964712203981333453463026845348919
236433351485118438528527394474215412119333358306644604843206177
4515451288380286258107477216411117336353320504484967202184231417
50772390292259111472217396130339354319484514912118817224342141161
3862992549548222339713433435530461454492201861752384352714951976
266994782303921183443613056544949351991782394342515251490372287
4642184041223403683004945949962031732404193815551589370290261113
3991363263563125345550611871832464204215051674383293262112462221
3243593076744149413191179253415261605227538728826397475224400135
308664394978205165241427301565297037129826998479219401120337362
452500920416324442244142517823752942769346322940712134135730951
10189176247423431405207738928026410546722541411632536731552456495
18024242428153523783882782671004812114021283293633224744050516190
43029157518793732912701014802094051233433493105944450123185164252
14152885374295265102465222408124342347313544584871119716824843724
The 23 columns may not all be visible here.

That probably ran into the neighbouring columns, but it’s just for illustration. The code, which I have used to generate magic squares of as high an order as 113 (magic number 721,505) is fewer than 170 lines in VBA for Excel 2007. And yes, even the above square, and the order 113 square are magic.

Recreational Math I: Magic Squares: the “really good” kind – Part 5

I have met with some disappointment as to how a methodology for creating a 4×4 square should pan out, and instead I have come up with many different algorithms, each resulting in its own small sets of magic squares, but had stumbled upon a set of squares with similar “hyper-magical” properties which I called the Durer Series.

I had met with some disappointment at this, and am still in the middle of writing my own 4×4 square program in Visual Basic .NET (it’s going to use a “brute force” algorithm … sorry!). With that, I had to learn about how .NET does objects. To those of you out of the loop on the recent .NET versions of VB, this language actually allows you to create your own novel objects, thus saving processing time if the right kind of objects are created. It’s a work in progress.

For now, I wanted to centre on the pièce de résistance of this series: that of the odd prime-ordered magic squares, those of order 5 and beyond. As I hinted at the beginning of this series, these are special and unique in that an algorithm can be made for an order-n magic square (where n is an odd prime greater than or equal to 5) which can generate (n!)2 squares, all magic (even after weeding out duplicates, the numbers of unique squares will still be in the thousands).

This seems to be a hard-to-find algorithm, except from a book called “The Fascination of Numbers”, written on the year of The Queen’s coronation in 1957 by W. J. Reichmann while he was still a headmaster at a Grammar School located in Spalding, Lincolnshire, England (according to my signed copy of the book, purchased from an English vendor through Amazon used books). I read it for the first time at a university library, and it is likely to be found in a similar univeristy or college collection near you.

What I like about this algorithm is that while I have used it to write computer programs for magic squares, it really requires no more than pencil and paper, and a bit of skill at addition.

First of all, write down the numbers from 1 to 5, in any order at all:

3, 2, 1, 5, 4

A 5×5 square matrix is constructed in a pattern by starting from the fourth number in the sequence, then proceeding with the 5th number, then the first, second and finally the third:

4 2 1 5 3
5 3 4 2 1
2 1 5 3 4
3 4 2 1 5
1 5 3 4 2

Next, scramble the first 5 multiples of 5 (counting 0):

20, 0, 5, 15, 10

Create a 5×5 matrix by shifting the order of these numbers by 2 to the left as follows:

20  0  5 15 10
 5 15 10 20  0
10 20  0  5 15
 0  5 15 10 20
15 10 20  0  5

Now add them together, adding together numbers located in the same columns and rows in both squares, as in matrix addition:

24262013
101814221
12215819
39171125
16152347

The result is a magic square which has many more ways of obtaining  the magic number 65 than just adding the rows, columns, and diagonals. Taking any 3×3 sub-square on the corners or left/right sides of this square and adding its corner numbers to the middle number will obtain 65. This seems to be true of all magic squares made by this method. Since both squares can be scrambled independently, there will be (5!)2 = 14,400 possible squares before duplicates are weeded out. I have written programs in many languages regarding this 5×5 square, and can attest to the robustness of this algorithm in producing a nearly endless series of 5×5 magic squares, all sharing very similar “magical” properties.

Reichmann also reminds us that the scrambled 5×5 squares we created initially are also magic.

I suspect there may be more than 14,400 magic squares. Are there any squares that cannot be produced by this algorithm? This must be checked against a “brute-force” (read: computational) method for generating all possible magic squares to see if this is really the definitive number. It is certainly a couple of orders of magnitude greater than what Danny Dawson did with his 4×4 squares (around 920 squares or so, with some duplicates). It would also be interesting to know what squares could not have originiated from Reichmann’s algorithm (proven by working backwards to show, supposedly, that duplicate numbers appear in some rows of the first or second matrix, which disappears in the resultant matrix.

It also seems that 4×4 and 5×5 squares can have such “compound” magical properties; it is harder to find for 7×7 matrices, although they are additive to the magic number in just enough ways so as to say they are magic. We’ll leave that for the next journal entry.

Recreational Math I: Magic Squares: the “really good” kind – Part 4

How to Make a Random Square

I have noticed that it has been difficult to elucidate a method for systematically creating even-ordered magic squares of any but the most basic kind. I don’t know why this is, since the art has been alive in Europe for at least 600 years, and probably longer in other cultures. There are a few methodologies out there, but they are perfunctory. Such as, this method offered by Reichmann (1957), which tells us little more than to write the numbers down from 1 to 16 and reverse the order of the diagonals:

 1  2  3  4        16  2  3 13
 5  6  7  8  ====>  5 11 10  8
 9 10 11 12         9  6  7 12
13 14 15 16         4 14 15  1

Well, only a limited number of magic squares are possible that way. You can reverse the order of the numbers, or write the numbers in order down the columns instead of the rows, followed by a similar reversal of the diagonals (these would not be considered to be unique solutions, since these methods amount to mirroring or rotating the square).

After some playing around with known 4×4 magic squares (thanks to the thorough resource offered here), and using some simple rules, I think I may have come upon a method on my own. I would suppose that it could not generate all magic squares possible, but I don’t intend to offer a complete solution. I estimate that I would be able to generate maybe another 10 or so magic squares with this method. The intent here is to allow the reader to create a 4×4 magic square sitting down at a table with little more than pencil and paper. I am sure this methodology is published elsewhere, but I wasn’t able to come up with anything.

I just have a few simple rules in coming up with the method. First of all, all of the 16 numbers are the result of a sum of two smaller numbers a and b, where a is a number from 1 to 4 such that a = {1, 2, 3, 4}, and b is a multiple of 4: b = {0, 4, 8, 12}. All 16 unique numbers generated will be the result of adding a number from set a to a number in set b.

The numbers 1, 2, 3 and 4 are the result of adding set a to 0 in set b.

The numbers 5, 6, 7, 8 come from adding set a to 4 in set b.

The numbers 9, 10, 11, 12 come from adding set a to 8 in set b.

And the numbers 13, 14, 15, 16 come from adding set a to 12 in set b.

My solution is inspired by Reichmann’s (1957) work on odd-ordered matrices. This solution on even-ordered matrices is quite different than for odd-ordered matrices, but the idea of adding two matrices and getting a magic square appealed to me, so I went with that basic idea.

The first matrix uses numbers from set a, in the following pattern:

4  3  2  1
1  2  3  4
1  2  3  4
4  3  2  1

These numbers may be randomized, but I’ll just stick to numeric order for now. The second matrix is composed of the numbers of set b arranged in a pattern reminiscent of the Durer square:

12  0  0 12
 4  8  8  4
 8  4  4  8
 0 12 12  0

The sum of the two matrices has all the magic of the Durer square, and consist of the unique numbers 1 to 16:

16  3  2 13
 5 10 11  8
 9  6  7 12
 4 15 14  1

In fact, it is the Durer square itself. Now that we know it works, what about mixing things up? Take note of the patterns. Let the first matrix represent numbers {a, b, c, and d} belonging to set a; and {e, f, g, and h} belonging to set b. whatever randomization is chosen, the numbers must fit the following scheme:

a  b  c  d      e  h  h  e
d  c  b  a      f  g  g  f
d  c  b  a   +  g  f  f  g
a  b  c  d      h  e  e  h

a, b, c, and d may be any permutation of the numbers 1 to 4, without apparent limitation. The second and third rows on teh first matrix are the reversals of the first and fourth. The second matrix, however is much more restricted. Considering e and f to be one pair; g and h to be another pair: 12 can only be paired on the same row with 0; and 4 only be paired with 8. Otherwise, no joy.

So, on with a randomized square: let a = {3, 1, 4, 2} and b = {8, 0, 12, 4}

3  1  4  2     8  4  4  8     11  5  8 10
2  4  1  3     0 12 12  0      2 16 13  3
2  4  1  3  + 12  0  0 12  =  14  4  1 15
3  1  4  2     4  8  8  4      7  9 12  6

What about a = {2, 4, 1, 3}, and b = {4, 12, 0, 8}

2  4  1  3      8  4  4  8     10  8  5 11
3  1  4  2     12  0  0 12     15  1  4 14
3  1  4  2  +   0 12 12  0  =   3 13 16  2
2  4  1  3      4  8  8  4      6 12  9  7

You may also treat sets a and b oppositely, while randomizing. This time the restriction is on matrix a — 4 pairs with 1, and 2 pairs with 3:

3  2  2  3     8 12  0  4     11 14  2  7
4  1  1  4     4  0 12  8      8  1 13 12
1  4  4  1  +  4  0 12  8  =   5  4 16  9
2  3  3  2     8 12  0  4     10 15  3  6

The reason I say these squares are limited to about 10 or so, is because as you can see, the individual rows or columns end up being about the same — at best, a shuffling or reversal the same rows found in the Durer square. There are at best 24 such squares, not subtracting tilted (squares the same when laid on its side) or reflected squares (where the squares are mirror images of each other). All that might be said, is that we may have discovered all the ways a magic square may be constructed with the same “hyper-magic” as the Durer square, which may be a pretty cool thing to say actually. It’s just that my goal was more ambitious at the start. I will refer to the set of 4×4 hypermagic squares built on the same rules as “the Durer series.”

Any known magic square, however, is the result of a unique combination of the basic squares built on sets a and b. Respectively, I will call the matrices A and B.  This allows us to work backwards from a 4×4 square we know is magic, and discern any patterns. The above squares were done that way. What patterns can be observed for the following square, which this website offers as #379 out of 900 or so others?

                Matrix "A"      Matrix "B"
13 12  6  3     1  4  2  3     12  8  4  0
10  5 11  8     2  1  3  4      8  4  8  4
 7 16  2  9  =  3  4  2  1  +   4 12  0  8
 4  1 15 14     4  1  3  2      0  0 12 12

One may discern a pattern here, but it is not all that obvious, especially for the square built on set b. It doesn’t seem to resolve itself into simple rules and patterns the way the Durer series of squares did. Also, you might have noticed that this square is not quite as “magic” as the Durer series, though all rows, columns, and both diagonals give you 34.

But I do notice that in matrix A the last column is a reversal of pairs of the first column. Also, the third column is built on the middle numbers of the first column, and the second column are built on the middle numbers of the last column.

What of Matrix B? The first and last columns are reversals (of all 4 numbers, not of pairs), the second and third both start with the middle two numbers, then first, then last from their adjacent end columns: “e f g h” becomes: “f g e h”.

When I tried to build on these rules, I got duplicate numbers in my squares (and with that, some missing numbers). It would appear that the observable number patterns in such squares are limited to getting you maybe 4 to 8 unique squares, then you have to make a new set of rules each time. With over 900 squares discovered (give or take a duplicate or two), that’s a lot of rules. The total number of 4×4 squares, both magic and not, are equal to 16! = 21 trillion possible squares. Finding all possible magic squares, weeding out any duplicates, reflections, and sideways duplicates would seem a tad non-trivial. Even at the website I referred to for these squares, it has been shown that the number “924” claimed as the number of possible 4×4 magic squares, might be too high, due to some duplicates found. Their scripts took just under 25 seconds to generate and check these squares — but just to check them for magic, less so for duplication, which sounds like it would take more computer time.

Recreational Math I: Magic Squares: the “really good” kind – Part 3

Notice that to show the rules for making these kind of magic squares, I used only odd-ordered square matrices as examples. What about matrices of even numbers of rows and columns? The rules for these vary.

This is a small part of a 1514 engraving by Albrecht Durer, called Melancholia. The author of the article that houses this graphic asserts that there are 32 possible 4×4 magic squares with the famous pun “1514” in the same position as above. This magic square has a symmetry in the numbers, as explained below.

The famous Durer magic square, with the year of the engraving cleverly made a part of a magic square, has a certain organization in its construction, as well as a certain symmetry. The numbers are constructed, in sequence:

_   3   2   _        _   3   2   _
_   _   _   _        5   _   _   8
_   _   _   _  ====> _   6   7   _
4   _   _   1        4   _   _   1         

_   3   2   _       16   3   2  13
5  10  11   8        5  10  11   8
9   6   7  12  ====> 9   6   7  12
4   _   _   1        4  15  14   1

So, you start from the bottom right and proceed in a horseshoe to the top then the bottom left. The next diagram places the numbers 5-8 in a pattern that is left-to-right u-shape. Then the same u-shape for the numbers 9-12 from left to right, except this time it’s upside-down. Finally ending as we started, the same horseshoe shape (except right side up) from right to left.

Durer’s square has many things about it, apart from its magic number (34) which works on all the attendant diagonals, rows and columns. The middle 4 squares add up to 34 (10 + 11 + 6 + 7 = 34); the four corners add to 34 (16 + 13 + 4 + 1 = 34), and all corner foursomes add to 34: (16 + 3 + 5 + 10); (2 + 13 + 11 + 8); (9 + 6 + 4 + 15); and (7 + 12 + 14 + 1).

The numbers at the ends of the two middle rows add to 34:

16   3   2  13
 5  10  11   8
 9   6   7  12
 4  15  14   1

and the numbers at the tops and bottoms of the two middle columns add to 34:

16   3   2  13
 5  10  11   8
 9   6   7  12
 4  15  14   1

If we take another symmetrical combination: a rightward-slanting rectangle whose corners are 2, 8, 9, and 15, these also add to 34:

16   3   2  13
 5  10  11   8
 9   6   7  12
 4  15  14   1

The leftward-slanting rectangle, whose corners are 5, 3, 12, and 14 also add to 34:

16   3   2  13
 5  10  11   8
 9   6   7  12
 4  15  14   1

Starting from 2 and proceeding in an “L”-shape to the left to the number 5, and continuing counter-clockwise in the same manner gets us the corners of a tilted square whose numbers 2, 5, 15, and 12, add to 34:

16   3   2  13
 5  10  11   8
 9   6   7  12
 4  15  14   1

Starting from “3” and doing likewise yields the numbers 3, 9, 14, and 8, also adding to 34:

16   3   2  13
 5  10  11   8
 9   6   7  12
 4  15  14   1

And what about this talk about “symmetry”? By this, we mean that we may take pairs of numbers at the start and end of any row, and they add up to the same number in a symmetrical place elsewhere. 16 + 3 = 4 + 15, taking the top and bottom of the first and second column. Likewise can be done for the last two columns: 2 + 13 = 14 + 1. The middle two rows have the same property: 5 + 10 = 9 + 6; and 11 + 8 = 7 + 12. On a larger scale, the sums of the middle two rows of columns 1 and 2 are the same as the tops and bottoms of columns 3 and 4: 11 + 8 = 7 + 12 = 16 + 3 = 4 + 15. Likewise, the sums of the middle two rows of columns 3 and 4 are the same as the tops and bottoms of columns 1 and 2: 2 + 13 = 14 + 1 = 5 + 10 = 9 + 6. These two groups of symmetrical numbers are illustrated below in red and green:

16   3   2  13
 5  10  11   8
 9   6   7  12
 4  15  14   1

The sums of 15 (green) and 18 (red) across each row form this pattern

16   3   2  13
 5  10  11   8
 9   6   7  12
 4  15  14   1

The downward symmetry is also interesting. Here, the sum of 25 is in gold and the sum of 9 is in blue. In the process, we can discern the patterns that we used to construct the square in the first place:

16   3   2  13
 5  10  11   8
 9   6   7  12
 4  15  14   1

This is an incredible amount of magic, but if you follow the order of filling (horseshoes are right-to-left, u-shapes are left-to-right, along with the peculiar pattern of filling u’s and horseshoes), there really are four possible patterns that have these “hyper-magic” qualities, but you lose the “1514” idea in two of them:

 8  11  10   5      12   7   6   9       4  15  14   1
13   2   3  16       1  14  15   4      12   6   7   9
 1  14  15   4      13   2   3  16       5  11  10   8
12   7   6   9       8  11  10   5      16   3   2  13

Of course, you could reverse all of the numbers in the rows of the first two squares to get your “1514” back.

Every time I look at that darned Durer square, I keep seeing more patterns. I think there comes a point where one has to leave the remaining observations up to the reader.

There is yet another 4×4 square, and with it we can increase the magic, if that can even be conceivable after all I have said. But there is a square with even more magic than the Durer square. R. J. Reichmann mentioned it in his book “The Fascination of Numbers”, first published in 1957. The square could be constructed like this:

-  -  3  -        -  -  3  6        - 10  3  6        15 10  3  6
4  -  -  - ====>  4  5  -  - ====>  4  5  -  9  ====>  4  5 16  9
-  -  2  -        -  -  2  7        - 11  2  7        14 11  2  7
1  -  -  -        1  8  -  -        1  8  - 12         1  8 13 12

This square has all the magic of the Durer square and then some. One thing this new square has over the Durer square is that any four numbers in square formation will add to 34, from anywhere in the square. These include the foursomes:

10  3     16   9     11   2       4   5
5  16      2   7      8  13      14  11

Recreational Math I: Magic Squares: the “really good” kind – Part 2

Last time I introduced the idea of magic squares. I promised I would show you how to make one. In this post, I will begin by discussing “trivial” squares, or squares made by simple rules of following diagonals and wrapping.

When I say a square is “magic”, I mean that all rows, columns, and diagonals add up to the same number. While other sources, such as Wolfram’s Mathematica, say that only the main diagonal of the matrix need be magic, I will take the more strict requirement that both leftward and rightward diagonals have to be magic.

There are trivial magic squares that begins by following a rule where you start with “1” in the top middle square, then move up and to the right one square, and place a “2” there.

_  1  _
_  _  _
_  _  _

But you may have noticed that if you start at the top, how can you move “up and to the right”? You get around this by “wrapping” to the bottom, treating the bottom of the rightward column as though it is above.

_  1  _
_  _  _
_  _  2

OK, you say, but now there’s no “right” after the last column. Now what? Now you can wrap so that the leftmost column is treated as “right of” the rightmost column:

_  1  _
3  _  _
_  _  2

Now another problem: up and to the right of “3”, there is a “1” in the way. If this happens, you are allowed to place the fourth number below the “3”:

_  1  _
3  _  _
4  _  2

Now, following these rules and exceptions, we can keep going:

8  1  6
3  5  7
4  9  2

The result is a magic square whose rows, columns and diagonals add up to 15.

I found that if I moved the 1 elsewhere and followed these rules in the same manner, some or all of the “magic” is lost. There seems to be only one magic square that can be made using these rules, at least one that adds up to 15 in all of its rows, columns and diagonals. The following 3×3 magic squares were the closest I could come to any credible “magic” by placing the “1” in a different position:

6  8  1                4  9  2
7  3  5 and similarly: 8  1  6
2  4  9                3  5  7

But notice in both cases, neither of the diagonals add up to 15. In the next post, I will discuss a way to break this limitation, making it possible to construct up to 36 3×3 magic squares.

Meanwhile, let’s expand the idea to 5×5, using the same, identical rules. This one seems easier in a way, since there aren’t as many blockages early on:

17  24   1   8  15
23   5   7  14  16
 4   6  13  20  22
10  12  19  21   3
11  18  25   2   9

I particularly like 5×5 squares. But my experience with placing the “1” elsewhere than the exact middle position of the top row has resulted in a loss of “magic”. However, I was lucky on my first attempt with moving the “1” around. The following magic square has a “Mathematica” level of magic:

11  18  25   2   9
17  24   1   8  15
23   5   7  14  16
 4   6  13  20  22
10  12  19  21   3

Later in this series, we can break this limitation, too. But next, we shall discuss some 4×4 magic squares, including one that made history.