Lee Sallows <Lee.Sal(a)inter.nl.net> wrote:
> A nice piece of work.
Thank you.
> What a pity you didn't find the beast sought. So next comes order
> 5. And then..
I don't plan to work on order 5 or larger unless I get a new insight,
since any brute-force search would probably take centuries, if not
eons. I'm continuing to search for semimagic order-4 squares.
> Who knows, perhaps this will go the same way as that other unsolved
> problem concerning the existence of a 3x3 magic square using 9
> distinct squares.
I hope not. If I recall correctly there's a proof that any solution
to that problem would require numbers of at least 14 digits.
>> I'm calling them Sallows squares, for Lee Sallows, who introduced
>> the idea here on October 12th.
Perhaps not the best name, since I've since learned that you've
done work on many other kinds of magic squares. Does anyone have
a suggestion for a better name?
Speaking of terminology, I've made up some:
4set: A set of 4 distinct positive integers, A,B,C,D, associated with
their sum, S, and the sum of their reciprocals, R. (Similarly with
other leading numbers, e.g. 3set, 5set.)
eset: A set of at least two 4sets which share the same S and
the same R. (The "e" is for "equal.") (They can also be phrased,
perhaps more elegantly, as sharing an arithmetic mean and sharing a
harmonic mean. The 9540,1/180 eset has an arithmetic mean of 2385
and a harmonic mean of 720. This shows that every 4set in that eset
must contain at least one number less than 720 and at least one number
greater than 2385 (since a mean can't be outside the range of the
numbers it's the mean of), but it doesn't immediately give me any
other insights.)
8eset: An eset with exactly eight elements. (Similarly with
other leading numbers.) It may be a subset of a larger eset.
8+eset: An eset with at least eight elements. (Similarly with
other leading numbers.)
seset: An eset each of whose 4sets' elements are shared by another
4set. (The "s" is for "saturated," by analogy with organic compounds,
which are said to be saturated iff every carbon links to four
different atoms.)
S search: For a given positive integer S, find all 4sets, then group
them by R's to find all 8+esets with that S. This goes as O(S^3),
since once S, A, B, and C are known, D is fixed.
R search: For a given positive integer's reciprocal R, find all
4sets, then group them by S's to find all 8+esets with that R. This
ought to go as O(1/R^3), since once R, A, B, and C are known, D is
fixed. (In practice, it has been much slower, since my program wastes
time searching vast numbers of large C's for the few that have a
corresponding integer D. There ought to be a way to rewrite it
that's (O(1/R^3).)
(Either an S search over all positive integers or an R search over all
positive integers' reciprocals will eventually find a semimagic square
if one exists.)
SR search: Given both S and R, find all 4sets. This goes as O(S^2),
since once R, S, A, and B are known, C and D are fixed (if a real C
and D exist and if C<D).
Bootstrap search: I can multiply all the elements in all the 4sets in
an eset by some constant K, creating a new eset with a K-times-larger
S and a K-times-smaller R. I can then either do an O(S^2) SR search
with the new S and R to find all additional elements in the new eset,
or do an O(S) search for all additional members of the new eset which
share a number with an existing 4set (e.g. hold A, R, and S constant
and loop through B, which will fix C and D).
Note the link to graph theory. 4sets are vertices, shared elements
(integers) are edges. I have not yet found any seset. The smallest
possible would be a 5seset, since no two elements of an eset can
share more than one element (i.e. if {a,b,c,d} sums to S and R, then
{a,b,e,f} cannot sum to those numbers (assuming, of course, that
a,b,c,d,e, and f all differ)).
The link to graph theory isn't perfect, since it fails to capture the
distinction between links between same numbers and different numbers.
For instance the graph of {{80,372,1240,1488},{80,400,900,1800},
{80,500,600,2000}} is the same as the graph of {{120,144,1296,1620},
{75,675,810,1620},{75,570,1235,1300}}, but in the former 3eset, one
number is shared between all three 4sets, meaning not all three 4sets
can be elements of an 8set that forms a semimagic square. In the
latter 3eset one number is shared between the first and second 4set,
and another number is shared between the second and third 4set. So
all three 4sets could be elements of an 8set that forms a semimagic
square. (Until you look at all 20 elements in the full eset and find
that no 8 of them will work.)
That's not to say that numbers shared by 3 or more 4sets are bad.
They're good in that they give more choices of which 4sets to use
in constructing a semimagic square. If a number is shared by just
two 4sets, either both 4sets must be used or neither.
Finding a semimagic Sallows square in positive integers requires
finding an 8seset that's the K4,4 graph. I don't yet know whether
one exists, and if so, whether it's feasible to find it. K4,4 is
necessary but not sufficient for a semimagic square.
I wonder if all graphs exist in some eset.
>> Those 18 sets of four numbers all sum to 1760, and their
>> reciprocals all sum to 1/45. Good luck finding better; I looked
>> at more than 40 billion sets of four numbers to find those.
I've since found one with 30 esets, summing to 7688 and 1/240. I did
so by doing an R search of successive integers' reciprocals. I had
noticed when doing an S search of successive integers through 2400
that 1/60 appeared remarkably often as the reciprocal sum in 8+esets,
so I decided to find all sets that gave 1/60. That search found
240462 4sets with 185718 distinct S's (from 969 to 179540195349843),
including 763 8+esets (with S's from 1145 to 171988), and one 20eset,
but no sesets.
Since that search went more quickly than I expected, I tried all other
R's from 1 up (i.e. down) to 1/240. Unlike the S search, I didn't
exclude sets with numbers divisible by primes greater than S/4. This
was partly because that wouldn't have saved any time, since I didn't
know S until I already finished the calculation, and partly because
that way I could compare it against Sloane's A241883 to give me more
confidence in my results. (Since the numbers get large (up to 19
digits), I wanted to do something better than mindlessly trying all
combinations, so that the program would finish before the heat death
of the universe. But that risks subtle bugs.)
A241883 lists only 21 terms. My calculation agrees with all of them.
Perhaps I should add terms 22 through 234 to OEIS. (After 234 some
of the numbers in the 4sets get too large for signed 64-bit integers.)
How many terms is too many?
That R search, 1/1 through 1/240, worked a lot better than my previous
S search. The R search found 71377 8+esets, most of them where 1/R
had lots of divisors.
After 1/240, I jumped ahead to 1/360, the next number with more
divisors than any smaller number. Good move. That R alone
has 20119 8+esets, and a new record largest eset, a 38eset:
{{420,6240,7280,10080},{440,3300,8580,11700},{440,3780,5940,13860},
{468,2236,8760,12556},{470,2970,3948,16632},{476,2040,10080,11424},
{480,1980,9240,12320},{480,2480,4320,16740},{520,1500,9000,13000},
{520,1530,7605,14365},{520,1625,5625,16250},{520,1692,4888,16920},
{520,2115,3055,18330},{520,2184,2920,18396},{594,1100,9150,13176},
{594,1122,7344,14960},{594,1410,3008,19008},{594,1431,2915,19080},
{595,1125,7000,15300},{595,1224,4470,17731},{620,1080,5580,16740},
{620,1200,3600,18600},{630,990,10080,12320},{675,900,9045,13400},
{675,920,6900,15525},{675,945,5600,16800},{675,1160,2610,19575},
{720,828,9752,12720},{720,855,6365,16080},{735,840,6030,16415},
{740,1080,2220,19980},{752,828,5520,16920},{756,792,8162,14310},
{779,855,3690,18696},{780,1365,1400,20475},{792,846,3572,18810},
{792,1353,1375,20500},{880,920,1980,20240}}. But, once again,
no sesets.
Then I jumped ahead to 1/720, as 720 is the next number after 360 with
more divisors than any smaller number. Not such a good move. It ran
extremely slowly, so I gave up on it after a week of CPU time.
I suspect the lack of sesets is due to sheer probabilities, though I
haven't yet worked out the odds. On a planet where years last 24020
days, there's a restaurant with 38 tables, with 4 people at each
table. What are the odds that every person at one table shares a
birthday with someone at another table? Or rather, what are the
odds that that's true of all the people at several tables if you
ignore every table at which there's a person without a shared
birthday? I should add that no two people at the same table ever
share a birthday with each other, and that certain birthdays are
more common than others, e.g. about 4/5 of the people are born on
even-numbered days, about 2/3 on days divisible by 3, and about 3/4
on days divisible by 5.
There's also the possibility of a bug in my seset-detecting code, as
it's never been tested. Perhaps I should generate some fake data with
which to test it. So many ideas, so little time.
I think these esets and their equivalent graphs are worthy of study in
their own right, even if it turns out that they can't form a semimagic
square.
>> Also, I'm excluding all numbers divisible by a prime greater than
>> S/4, as those can't possibly be part of a Sallows square. Can you
>> see why not?
R = 1/a + 1/b + 1/c + 1/d = (abc + abd + acd + bcd)/abcd =
(a(bc + bd + cd) + bcd) / abcd. A prime factor of a will be in the
denominator unless canceled out by the same factor in the numerator.
Since a(bc + bd + cd) has that factor, the factor can't cancel out
unless bcd also has that factor. So unless at least one of b, c, and
d shares that factor, the factor must appear in some number on every
row of the semimagic square, since otherwise the reciprocal sums of
the rows couldn't all be the same. That requires four such distinct
numbers, one for each row. But if the factor exceeds S/4 there aren't
four distinct numbers divisible by that factor which are less than S.
(That prime factor must also appear in each column, but the same four
numbers suffice so long as they're arranged properly in the square.)
This helps explain why numbers in 8+esets tend to have lots of small
factors, and to have them in common.
I haven't found any order-4 semimagic squares yet, but it's easy to
generate chains (open, closed, branching, etc.). For instance this
hollow square:
20 76 190 152
88 55
110 209
220 56 140 22
So where do I go from here? I can think of several approaches:
I could try to beat it to death with algebra. For instance if
{a,b,c,d} is a 4set, then any other 4set in the same eset can
be expressed as {a,(b+n),(c+m),(d-n-m)}, where m and n non-zero
integers. I then plugged that into the formula for the inverse
sum and played with it, but all I got was a hideous mess.
I could speed up my R search by skipping large numbers, which
is where my program spends most of my time but finds the fewest
esets. No good can come from 4sets such as this one for R = 1/234:
{235,54991,3023955091,9144304389360863190}. But how large is too
large? Too small a ceiling and I miss lots of esets.
I could try bootstrap searches.
I could try to find a solution in positive irrationals, perhaps powers
of phi (since every integer can be expressed as a finite sum of such
powers, usually in multiple ways), but I don't see that that would be
any easier. Also, it would be less elegant.
I could temporarily (?) give up on searching positive numbers, and
go to mixed plus and minus. But, like my complex solution, it's not
as elegant, and it doesn't work with your original physical model
involving resistors. Henry Baker pointed out that impedance is one of
the few physical quantities for which complex numbers are meaningful,
so if you expand your network to include capacitors and inductors
along with the resistors.... However, the real part of the impedance
can't be negative, so my solution was no good. So I wonder why you
then specified that you were searching for a solution in reals rather
than a solution in *positive* reals. Perhaps because if you toss
the resistors and go with just coils and condensers, that would
correspond to a purely imaginary solution, which any purely real
solution, including one with mixed signs, could be trivially
converted into?
What I'd really like would be a way to combine 4sets from different
esets to generate a new much larger eset. For instance if I had
an 8eset and a 9eset with different S's and different R's, I would
combine each element of one with each element of the other to produce
a 72eset with yet another S, perhaps the product of the other two S's.
This operation would presumably be symmetrical, in the sense that
reordering the 4sets within an eset, or the numbers within a 4set,
wouldn't change the result. And it would presumably be linear, in the
sense that if I were to double all the numbers in one of the esets,
all the numbers in the result would be doubled. Maybe something
matrixy.
The last approach would also make a search for an order 5 or larger
magic square feasible, assuming it generalizes. 5sets differ from
4sets in that they can form double bonds (2 numbers shared between
5sets in an eset), allowing polyunsaturated esets. Of course those
wouldn't be useful in making a magic square.
