I Can New Theorems Predict Incomplete 5x5 Magic Square Solutions?

[Vanadium 50]

My thinking on other moduli besides parity goes like this:

If you add up all the rows and columns (10) you get 650. If you include the diagonals (3) you get 780. In the global sum, the middle cell contributes 4x, the rest of the diagonals 3, and every other cell 2.

If you look for a rule mod 3, it removes the diagonals except for the center cell. But they aren't going to tell us anything since their sum is fixed.

I doubt that mod 4 will help, since the only difference is the center cell with respect to the bulk. I think .Scott's study kills that.

Next up is 5. I think mod 5 might be interesting not because of sums, but that it would potentially exclude patterns that use too many 5's, or not enough 2's or something.

 

[mfb]

But when (2,2) = 13, there is no ready way to get that (1...25) => (25...1) effect if you are using the other filters.

You can't stop halfway through 13, yes, but you don't need to check 14-25 in the center.

The total number of solutions found was: 137,652,612

Great! You found code that can find all solutions.

 

[.Scott]

Yesterday I ran the full thing without the x16 optimizations - just so I had a way of further validating the x16 results. That is just fishing up now (about 24 hours). My laptop had 4 cores - so I can run two of these without them slowing each other down. Their effect on other things I have doing on my computer is also mild.

Next up is 5. I think mod 5 might be interesting not because of sums, but that it would potentially exclude patterns that use too many 5's, or not enough 2's or something.

I agree, mod 5 is next - but I might post some other results I generated yest.

 

[mfb]

If you store 16 of the values in each solution the others can be derived trivially. Even without an effective compression that's 16 bytes per solution, or 2.2 GB. Or 3.4 GB when storing all 25. Small enough to store all solutions. Running algorithms over the stored solutions might be much faster than solving magic squares each time.

 

[Vanadium 50]

Here are some of the diagonal rows that do not lead to a solution. They come in pairs, with a reflection of the (edit:) connectors I don't see an obvious pattern mod 5.

For a center value of 1, the upper left corner (defined to be the smallest) runs from 13 to 24.

18 13 1 14 19
18 14 1 13 19
18 12 1 15 19
18 15 1 12 19
18 11 1 16 19
18 16 1 11 19
17 10 1 18 19
17 18 1 10 19
...
13 2 1 24 25
13 24 1 2 25
24 2 1 13 25
24 13 1 2 25
...
18 12 2 14 19
18 14 2 12 19
18 11 2 15 19
18 15 2 11 19
...
24 2 13 1 25
24 1 13 2 25

 

[mfb]

These pairs are coming from another symmetry we didn't consider before. Swap the second and fourth row, swap the second and fourth column. The row and column sums stay the same as each operation doesn't change them, and the diagonals stay the same as we just swap the inner values across the center. That means we can require e.g. n(1,1)>n(3,3) and get the other solutions from symmetry.

Excluding global rotations and reflections there are 275305224 = 2³ * 3 * 109 * 105239 solutions.
* Inverse 1-25 order: 2
* Corner/connector symmetry: 2
* This new symmetry: 2
This means we found all symmetries with a factor 2. There might be one more with three options, even though 3 is an odd number (in both meanings). I don't expect more symmetries.

Edit: Interestingly, this has implications for magic squares where the center is 13, where the 1-25 symmetry could mimic one of the other symmetries in principle. It seems to do this in an even number of times.

 

[Vanadium 50]

275305224 = 23 * 3 * 109 * 105239 solutions

That is a very, very interesting way of looking at it. However, it mixes center = 13 with center <> 13 solutions, with the latter coming in pairs. Also, it's probably not likely there is a symmetry that takes a number in the center and moves it outside. So we should probably look at numbers of squares by center square value.

01: 4365792 = 2⁵ x 3³ x 31 x 163
02: 5464716 = 2² x 3 x 455393
03: 7659936 = 2⁵ x 3² x 26597
04: 7835348 = 2² x 1958837
05: 9727224 = 2³ x 3 x 13 x 31177
06: 10403516 = 2² x 523 x 4973
07: 12067524 = 2² x 3² x 7²x 6841
08: 12448644 = 2² x 3 x 13 x 199 x 401
09: 13890160 = 2⁴ x 5 x 23 x 7549
10: 13376136 = 2³ x 3 x 557339
11: 15735272 = 2³ x 7² x 137 x 293
12: 15138472 = 2³ x 1892309
13: 19079744 = 2⁶ x 47 x 6343

So it looks like we have all the 2-way symmetries (smallest exponent is 2).

 

[mfb]

Ah, right, we can't guarantee anything for the solutions with 13.

Okay, general 2-way symmetries are done. And I assume from your post that you have a program that can find all solutions now, too.
There is no other common factor, so we are not missing any other universal symmetry. There might be more to find with 13 in the center.

 

[Vanadium 50]

And I assume from your post that you have a program that can find all solutions now, too.

I've had one for a long time. But a) it runs slowly, and b) I am trying to learn things. (Wouldn't it have been interesting if there were a 109-symmetry?)

 

[mfb]

Fast enough to be useful was implied.
There are more powers of 3 than you would expect naively but I would be surprised to see that linked to symmetry.

 

[Vanadium 50]

I'm struggling with my code.

I have code that finds all the combinations. I changed the print routine so that now when it finds one combination, it prints out the other 7 that can be derived from it (3 if the center value is 13). So it counts 8 times as many. So far so good.

Let's simplify things by ignoring the cases where we change the center square. So every time we find a square, we find four. Again, so far so good.

Now I want to avoid the duplicates. This is not so simple. I can define the square's orientation by requiring the smallest corner to be in the top left and for the top right corner to be larger than the bottom left (and I do). But a simple thing like requiring the top left connector be larger than the top left corner does not work. ("work" defined by "getting the right answer" and "runs twice as fast", neither of which is the case)

 

[mfb]

Do you know what breaks if you do that?

 

[Vanadium 50]

Too many squares and not enough reduction in time.

For example.

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

appears at least twice. Once as a found square, and once as a 2-4 permutation of the following square.

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

 

[mfb]

See post 36 where I first describe this symmetry:

That means we can require e.g. n(1,1)>n(3,3) and get the other solutions from symmetry.

 

[Vanadium 50]

Thanks - that works. (Once I figured out that 1 meant "second row" and 3 meant "fourth".) I get the right number of squares, and a speedup of 1.65. Not the two I hoped for, but still pretty good,

So that's one factor of two. Where is the other one hiding?

Also, when looking at the patterns scroll by, it's impressive how slowly the main diagonal changes. You might think "that makes sense - there are millions of squares but only thousands of ways to add up to 65, so I expect thousands per main diagonal". That's correct. But there are also ones with zero, so it's not so simple.

Further, if printing them out, every so often it pauses for a second or two. That means there are hundreds of thousands of non-squares in a row. I wonder what is happening here.

 

[mfb]

I like to start an index at 0.

So that's one factor of two. Where is the other one hiding?

I lost track, relative to what version?

That means there are hundreds of thousands of non-squares in a row. I wonder what is happening here.

Diagonals with no solution?
I wonder if machine learning could provide some insight here. Feed it half of the diagonals without a solution and half of the diagonals with one, see if it can get predictions for the other half right and then look if there are understandable rules it found.

 

[Vanadium 50]

I like to start an index at 0.

Like French elevators.

I lost track, relative to what version?

I take a square. I apply the two symmetries and get four squares, I apply the n(3,3)-n(1,1) constraint and I have 2 left - that is, I find every square twice. I'd like to find every square once.

Diagonals with no solution?

Yes. I am not sure what ML would tell me that a list of successes and failures does not. Especially something like a NN where the work is being done through a hidden layer. But something like this seems more useful for 6x6 squares and improving the estimate of the number of solutions.

 

[mfb]

Hmm... we might link the rotation symmetry with the corner/connector symmetry in a bad way. After requiring that (0,0) is the largest corner, we might need to require that it's larger than all connectors (instead of just (1,1)). That makes sure we get each case exactly once, the symmetric squares then have the largest element of the diagonals in the connectors. After that n(1,1)>n(3,3) can be checked as before.

Edit: Forgot that part. Yes, extracting patterns from the machine learning output is not necessarily easy. One would start with very simple setups. All parity-like patterns could be found by simple checking all different ways to sum/subtract numbers.

 

[Vanadium 50]

we might need to require that it's larger than all connectors (instead of just (1,1)).

That's not enough. About 15% of the squares are found more than once.

 

[mfb]

How? Do you have examples of what is still being found multiple times?

 

[Vanadium 50]

How?

Bug.

 

[Vanadium 50]

How? Do you have examples of what is still being found multiple times?

Thanks your your help!

The bug was that one test was performed twice and another zero times. It's looking like it takes ~20 hours to find all the squares, which is much better than the 458h it took at the beginning of this.

What's impressive is that once the diagonals and the center row and column are placed, 5% of the time we find a magic square. Technically, 0.6% of the time we find 8. But if you just place those 17 numbers at random the probability of finding a magic square is about 4 x 10^-7. So we're doing a million times better.

I find @.Scott 's numbers very intriguing. About half of the X-patterns have no solution. That's potentially a factor of 2 right there, and the rule may be applicable elsewhere.

I had considered parallelizing this, but it's not trivial. Part of the reason is that the code was not designed that way; there's a single Square object, and part of the problem is that parallelizing by center element leaves you with a maximum of 13 workers and a very unbalanced system.

 

[Vanadium 50]

It takes 75774 seconds to do an exhaustive search.

I looked at the main diagonals mod 5. There are three patterns, which I call a straight (e.g. 20134), two pair (e.g. 33144), and three of a kind (e.g. 31114). All three are present, so if there is a way to identify non-solutions mod 5, it will involve both diagonals.

I plan to parallelize with pThreads. Load balancing will come later, but I will probably do it at the main diagonal level. Each thread will look at every Nth element in that list of rows. The machine this will run on has 12 cores and 24 threads. so I suspect N will be 25. Fully load balanced, I imagine it will take between 1 and 2 hours to run.

 

[mfb]

No five of a kind is a little bit of information.

 

[Vanadium 50]

Not so much, since the only 5 of a kind that works is all 3's. That's a single row for a few cases.

 

[mfb]

Wait, so it exists?
And why does it need to be all 3s, unless that's a non-trivial result?

 

[Vanadium 50]

3+8+13+18+23 = 65 The other fives of a kind don't add up to the right number. Further, there's only one such row (and its permutations) for every center square.

 

[mfb]

Oh right, the limit to 1-25 restricts that.

 

[Vanadium 50]

So, I managed to rework the parallelization and got it down to under an hour. Barely. I can find all 275M squares in 59 minutes and 23 seconds. This uses 32 threads on a 12C/24T processor. It's 22.9x faster than one processor.

About ten minutes towards the end, threads start terminating. So there is some room to improve the load balancing: perhaps 5%. This is mitigated somewhat by the fact that as threads terminate, the chip speeds up.

Another potential source for a 5% gain is squares with 13 as their center. If I find a square with 12 as its center, I have also found one with a 14 as its center, under the {26-x} transformation. If I do with with a square with center 13, I find a different square with center 13. So effectively I find each pair twice. If I could find a way to quickly reject the "second" member of the pair, it would double the speed of the 13's, saving maybe 5% overall in time.

That same symmetry has interesting implications for early detection of patterns with no solution. There's been speculation that looking at subsets of cells (one or two diagonals) mod 5 one can conclude there are no solutions. Because of the {26-x} symmetry, should such a pattern be found, a second pattern could be found swapping 0 and 1, and 2 and 4. I think that's very interesting as it is not the "normal" 1 and 4/2 and 3.

I'm not sure if this is a breakthrough or proves it impossible.

 

[Vanadium 50]

Here are the scaling plots (for center = 1 and 25):