Hi Ed,
I have a proof that a base-2 palindromic solution is impossible if the
number of digits is the same.
_____ _____ _____
| | | |
| a | b | c |
|_____|_____|_____|
| | | |
| d | e | f |
|_____|_____|_____|
| | | |
| g | h | i |
|_____|_____|_____|
For the magic square we know a+i = b+h = c+g = d+f = 2e, so we need to find
two base-2 palindromic numbers which add to produce 2 x another base-2
palindromic number. ie P1 + P3 = 2 x P2 where P1,P2 and P3 are different
base-2 palindromic numbers.
Let P1 have the digits [a1,A1,a1]
Let P2 have the digits [a2,A2,a2]
Let P3 have the digits [a3,A3,a3]
Where a1,a2 and a3 are either 0 or 1
Where A1,A2 and A3 are multiple digit numbers (assume the same number of
digits)
P1 + P3 must be even therefore a1 = a3
P1 < P2 < P3 therefore a2 = a1 = a3
Therefore A1 + A3 = 2 x A2, you can repeat the above until A1 = A2 = A3 =
[]. Therefore the only solution to the equation P1 + P2 = 2 x P2 is when P1
= P2 = P3.
Regards
Brendan
---------------------------------------------------------------------------
From: "Joseph DeVincentis"
To: "Ed Pegg"
Subject: base-2 and base-3-palindromic magic squares
Date: Sunday, May 27, 2001 11:00 PM
Here's the smallest magic square with numbers that are all
palindromes in base 3, with magic sum 242 = 22222 base 3:
151 82 130 12121 10001 11211
100 121 142 10201 11111 12021
112 160 91 11011 12221 10101
The base-2 problem is interesting. Using the property of magic squares
that the four pairs of opposite numbers each have to add to twice the
number in the center, I looked for base-2 palindromes which have at least
four pairs of other base-2 palindromes that add to twice the first number.
I didn't have to look far. These start showing up as early as this set
with a center number of 33: 33*2 = 1+65 = 3+63 = 15+51 = 21+45
I found a few of these, and some (like the above, or the ones that
sum to 129*2) where three of the outside numbers form an edge that adds
to three times the center number (and, thus, the three they are paired
with form another such edge). However, the numbers needed to complete
the square are not palindromes (at least, they aren't *both* palindromes).
I wrote a program to search for these numbers, and found 31 center numbers
under 2^20 for which there are at least 4 pairs of palindromes with the
necessary sum, and three of those add to make a valid edge. But none of
these had more than just that edge and the opposite one made of the
numbers those three were paired with.
I noticed some interesting repetition of numbers among the valid edges
for different center numbers. Most of them paired up like these two
(the first two center numbers to do so):
center 1755
** edge ** 195 + 2925 + 2145
** edge ** 3315 + 585 + 1365
center 2145
** edge ** 195 + 3315 + 2925
** edge ** 4095 + 975 + 1365
Notice how four of the six numbers in the edges are repeated, and one of the
ones from the first group is repeated as the center number for the second!
I figured some sort of extensible pattern in the binary representations
was responsible for this, so I reran the program, printing the results
in binary.
center 11011011011
** edge ** 11000011 + 101101101101 + 100001100001
** edge ** 110011110011 + 1001001001 + 10101010101
center 100001100001
** edge ** 11000011 + 110011110011 + 101101101101
** edge ** 111111111111 + 1111001111 + 10101010101
The pattern can be represented as:
center 27*(2^n+1)
** edge ** 3*(2^n+1) + 45*(2^n+1) + 33*(2^n+1)
** edge ** 51*(2^n+1) + 9*(2^n+1) + 21*(2^n+1)
center 33*(2^n+1)
** edge ** 3*(2^n+1) + 51*(2^n+1) + 45*(2^n+1)
** edge ** 63*(2^n+1) + 15*(2^n+1) + 21*(2^n+1)
The coefficients for 33*(2^n+1) in the center are just the numbers
from the solution for 33 in the center that I found way back in the
beginning. If I had not eliminated center numbers with only 3 pairs
without even looking at them, I would have also found the above edge
for 27 in the center.
Since the center numbers are under 2^12 (n=6 in the formulas for the
pattern), I found 8 more sets of these for n = 7 to 14, and an n=15
repetition for the center number 27*(2^n+1) case.
You can also multiply by (2^2n+2^n+1) and get another repeating set
of solutions; I got two sets of these in my results as well.
All combined, including the case with just 33 in the center, these
represent 24 of the 31 center numbers from my results.
The other two numbers required to complete the magic square are 15 and 39
for the 27 case, and 27 and 39 for the 33 case. Since 39 = 100111 binary
is not a palindrome, and will never be a palindrome when multiplied by
2^n + 1, these patterns will never produce solutions using these edges.
The other unique case I found before these repetitions started coming up
was for a center number of 129. This gave the following numbers:
center 129 = 10000001 binary
** edge ** 27 + 195 + 165
** edge ** 231 + 63 + 93
~~binary~~ 11011 + 11000011 + 10100101
~~binary~~ 11100111 + 111111 + 1011101
Of course, if you multiply all the numbers by 2^n+1 (n >= 8), you get
repetitions of this pattern as well. Five more of my solutions are
such repetitions. Counting the 129 case as well, this now accounts
for 30 of my 31 near-solutions.
The numbers required to complete the square are 99 and 159, and 159
is not a palindrome in base 2, nor will it be when multiplied by
2^n+1, so this pattern does not yield any solutions for these edges.
This is true in general; if the base case for one of these patterns
does not yield a complete solution, the "extended" ones (which are just
multiplied by a factor) will not ever do so using those edge combinations.
They could do so, using entirely different combinations of numbers on the
edges, but I see no reason to expect that to be more likely to occur for
these numbers as for any others.
Finally, I did find one more "near-solution" which is not a multiple
of any of the other earlier solutions:
center 546465 = 10000101011010100001 binary
** edge ** 50115 + 843891 + 745389
** edge ** 1042815 + 249039 + 347541
~~binary~~ 1100001111000011 + 11001110000001110011 + 10110101111110101101
~~binary~~ 11111110100101111111 + 111100110011001111 + 1010100110110010101
(50115 = 257*195 is repeated from one of the multiples of the center-129
case, but all the other numbers are unique and not factorizable in such
an easy, obvious way).
This doesn't help much, except that it shows that there's nothing special
about 27, 33, and 129. It reinforces the idea that there's no particular
subset of base-2 palindromes to look at to shortcut your way to a solution.
With only 4 truly unique near-solutions in this range, and three of them
clustered among small numbers, it looks like the near-solutions are
going to be exceedingly rare among larger numbers, as palindromes get
rarer, but I can't prove that there isn't going to be a solution somewhere.
However, I think this comes close to pushing it into that realm where
the problem is just sitting there, waiting for a proof that there's
no solution.
What's the largest number in the smallest solution to a simply stated
number theory problem? Or perhaps what I mean is what is the largest
space that has ever needed to be searched to find the first solution
to a problem? There may not be any single clear answer to such a
question, but I'm just curious. How far has anybody ever searched for
answers on such a problem, and after trying billions of combinations,
finally found the first solution?
Joseph DeVincentis
---------------------------------------------------------------------------
In base 3:
12121 10201 11011
10001 11111 12221
11211 12021 10101
In base 10:
151 100 112
82 121 160
130 142 91
Similarly, by adding 10001 (base 3) or 82 (base 10) to each
number:
In base 3:
22122 20202 21012
20002 21112 22222
21212 22022 20102
In base 10:
233 182 194
164 203 242
212 224 173
These were obtained through simple manipulation of the ol'
popular
8 3 4
1 5 9
6 7 2
pattern.
Matthew Prins
--------------------------------------------------------------
Hi Ed,
One way to do base 3 is very similar to the base 4 solution, but we have
to wrap the 3-digit solution in 10001 to avoid leading zeros, giving:
11211 10001 12121
12021 11111 10201
10101 12221 11011
It's pretty easy to find a 3x3 square with binary palindromes which is
magic except for the diagonals. Does that count? I guess not, but here's
one anyway:
101000101 100111001 110000011
110101011 100000001 101010101
100010001 111000111 100101001
I think I can prove that you cannot also get magic diagonals if the
numbers are all the same length, but of course they need not be. For
example:
11111 1001 101
11 1111 11011
111 10101 10001
has correct rows and one correct column. That's the best I've done so
far with different length numbers.
Regards
Chris Lusby Taylor
----------------------------------------------------------------------
If leading zeroes are disallowed, I can't find a square...
I searched for all combinations of the 4092 binary palindromes between 0 and
3fffff hexadecimal.
But I can't prove it isn't possible either :-(
Since the "distances" between binary palindromes increase with the longer
lengths, however, it seems unlikely that such a magic square exists.
Luc
------------------------------------------------------------------------
Thanks for some more great puzzles
For the base-3 magic square solution, consider the digits independently...
First, pick the middle digits using this magic square,
021
210
102
And then the digits around it from this one
102
210
021
Then choose 1 (arbitrarily) for the first and last digits. This gives
11011 10201 12121
12221 11111 10001
10101 12021 11211
I haven't found a solution for base-2. The approach above breaks down and a
computer search shows there's no answer with the middle number <90,000. However
I haven't managed to prove it false.
Jon Palin
--------------------------------------------------------------------------
Magic square.
Here are three solutions of this problem for 3-base system.
=============================
10101 12021 11211
12221 11111 10001
11011 10201 12121
91 142 130
160 121 82
112 100 151
===============================
20102 22022 21212
22222 21112 20002
21012 20202 22122
173 224 212
242 203 164
194 182 233
===============================
101101 120021 112211
122221 111111 100001
110011 102201 121121
280 412 400
484 364 244
328 316 448
============================
Best Regards, NorT (Eugene V. Bryzgalov)
--------------------------------------------------------------------------
Well, with 5 digits in each number, I can get:
10101 11211 12021
11011 12121 10201
12221 10001 11111
I'm sure there's a solution with a smaller sum, but this works. ::)
-Matt Elder
-------------------------------------------------------------------------
Hi Ed,
An exhaustive search of the first 91 palindromic
binary numbers (all those up to 1967, 11110101111)
yields no magic squares.
The base 3 solution is
91 142 130 : 10101 12021 11211
160 121 82 : 12221 11111 10001
112 100 151 : 11011 10201 12121
Are you interested in other bases? There are solutions
in base 5 (more than one) and beyond.
Cheers!
Jim Shaw
--------------------------------------------------------------------