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 --------------------------------------------------------------------