HP-15C Mini-Challenge: Magic squares !



#14

Hi all:

    Since these next four days will be a loooong weekend here in Madrid, I feel like concocting a brand new HP-15C Mini-ChallengeTM for you to try, namely:


    A magic square is a square arrangement of numbers such that each row, column, and main diagonals add up to the same value, say K, which is called the magic square's constant.

    Now let's say you're given an arbitrary 3rd order magic square which has some (not given) value K as its constant. You must write a routine which takes the given magic square as its input and then computes the elements of another magic square of the same order but having K3 as its constant instead.

    You don't need to include any input or output procedures in your routine, it may assume that the given magic square is already stored in memory in any way you find convenient (such as sequential numeric registers, or a matrix, or whatever) and it just needs to compute the elements of the new magic square and leave them stored in memory, no need to actually output them to the display.

    For example, if given the following magic square:

         71   89    17 
    5 59 113
    101 29 47
    which has K = 177 (all rows, columns, and main diagonals add up to 177) you must compute and store
    the elements of another magic square of the same order but having K = 1773 = 5,545,233.


    You must optimize for program length, the shorter the better. Not counting label and return, it can be done in the number of steps corresponding to a very famous integer traditionally considered having to do with luck (whether good or bad is up to you ...), and further an additional step can be shaved off with one little proviso.

    I'll provide my solution and comments next Monday or so, maybe earlier if someone stumbles upon it. Have a nice weekend and all that, and

Best regards from V.

Edited for typos


Edited: 10 June 2009, 6:39 a.m.


#15

Hi Valentin,

Great to see another 15c Mini challenge.

Here is my solution - 4 steps excluding the LBL and RTN. The solution assumes that the magic square is stored in a Matrix and that the Matrix descriptor is in the X-register before being called.

LBL A
ENTER
f MATRIX 7
x^2
*
RTN

It could be reduced to 3 steps if the matrix descriptor is in both the X and Y registers before the routine is called. In this case the first ENTER can be removed.

The only caveat is that it does not work for magic squares which have negative entries for some of the elements.

Best regards,

Eamonn.


#16

Great to see a mini challenge I can solve !! :-)

My solution, assuming that the magic square is in matrix A: 7 steps excluding LBL and RTN, should work for all magic squares.

01 LBL A
02 f RESULT B
03 RCL MATRIX A
04 ENTER
05 *
06 f RESULT C
07 RCL MATRIX A
08 *
09 RTN

Result is in matrix C and is different from the one obtained with Eamonn solution.


Edited: 10 June 2009, 12:47 p.m.


#17

Hi Didier,

I like your solution. I was not aware that the third power of a magic square matrix is itself a magic square matrix with a magic sum that is the third power of the magic sum of the original matrix. Very nice result.

I played around with some more ideas and here is another seven step solution (not including the LBL and RTN) that I believe solves the challenge as stated and generates a solution that is different to the earlier posted solutions.

This solution requires that the original magic square be stored in the 3x3 Matrix A, with the center square stored in A(1,1). The other values from the original square can be stored in any order in A that is convenient for the user.

LBL A
f MATRIX 1
RCL A
3
y^x
9
*
STO MATRIX A
RTN

The result is returned in the Matrix A, with the very magic property that the new magic square can be read from Matrix A in conventional fashion (i.e. the center of the new magic square ends up in A(2,2), the top left value is in A(1,1), etc. This solution should work for all 3x3 magic squares, even those with a mix of positive and negative values, always returning a square in which all the rows and columns and the main diagonals sum to the cube of the magic number of the original square.

Best regards,

Eamonn.


#18

Well, I realize that I've been a bit quick to jump to a solution. I found it quite intuitively and I've verified it for several magic squares but I don't have a complete demonstration ...

Here are some explanations:
let's take two 3x3 magic squares X, constant K and Y, constant L

     ( a, b, c )      ( r, s, t )
X = ( d, e, f ) Y = ( u, v, w )
( g, h, i ) ( x, y, z )
then
       ( ar + bu + cx, as + bv + cy, at + bw + cz )
X*Y = ( dr + eu + fx, ds + ev + fy, dt + ew + fz )
( gr + hu + ix, gs + hv + iy, gt + hw + iz )
the sum of the first column is:
(a+d+g)r + (b+e+h)u + (c+f+i)x = Kr + Ku +Kx = K(r+u+x) = K*L
and you can see in the same way (using only rows and columns constant property) that the result is the also K*L for all rows and columns.

However I've not found a way to prove it's the same for the main diagonals ... btw it's not true as on a few examples I've tried the diagonal constant is not K*L.

If we suppose that the rows and columns constant of X*Y is K*L then for X*X it's K^2 and for X*X*X it's K^3; and strangely this last one is also true for the diagonals for the different magic squares I've tried so far.

So I still have to prove that the constant for the diagonals of X*X*X is K^3...

Now, to add something else to this incomplete and potentially wrong solution, and as Valentin has expressed previously his interest in the old Sharp Pocket Computers, here is a program for the Sharp PC-1403 using the Matrix functions entry points described earlier on this forum in
this thread:

The Sharp PC-1403 uses 3 matrix: X and Y for calculation, M for memory.

The program below assumes that the magic square is in X and return the result of X^3 in X.

10:"A":CALL 26191:REM X->M
20:CALL 26186: REM X^2->X
30:CALL 26163: REM X<>Y
40:CALL 26199: REM M->X
50:CALL 26119: REM X*Y->X
60:PRINT X(0,0)+X(1,1)+X(2,2),X(0,2)+X(1,1)+X(2,0)

Example:

CALC mode
SHIFT down 'to enter in Matrix mode
3 ENTER 3 ENTER 'to dimension matrix X as 3x3
71 ENTER 89 ENTER 17 ENTER 'enter first row
5 ENTER 59 ENTER 113 ENTER 'enter second row
101 ENTER 29 ENTER 47 ENTER 'enter third row
3 ENTER 3 ENTER 'to dimension matrix Y as 3x3
ENTER (9 times) 'until you get MATRIX OPERATIONS on the display
BASIC mode
DEF A 'to run the program
It ends by printing the constant for the 2 main diagonals, so you can verify it's K^3.
For the example above it shows:
5545233.       5545233.

Edited to add some precisions to the explanations.


Edited: 11 June 2009, 3:25 a.m.


#19

Hi Didier,

Section 8 of the book "Mathematical Explorations with MATLAB" deals with Magic squares. Part of exercise (v) on Page 104 is to prove the the product of an odd number of magic squares is also a magic square. The relevant sections are viewable in Google books (here is a link: Mathematical Explorations with MATLAB).

So, it appears that your solution is good.

Best regards,

Eamonn.


#20

Eamonn, thanks for the link, I will check it. I've prepared my solution below before seeing your post so I'm posting it anyway as it reflect my findings.


Introduction


To provide some formal content to my 15C program submitted above, here is a complete demonstration showing that if M is a 3x3 magic square having K as its constant, then M3 is also a magic square with K3 as its constant.

I suppose there are some smarter and nicer demonstrations as mine is a bit on the "brute force" side, being based on the direct calculation of each term of M3.


The trick


After several tries, I've come to the conclusion that I needed to take advantage of the magic square properties to reduce the number of variables to a minimum.


As I was manipulating 3x3 magic squares I've found an interesting property:

    ( r, s, t )
M = ( u, v, w )
( x, y, z )
being a magic square with K as it's constant, we can write using the rows properties:
3K = (r+s+t) + (u+v+w) + (x+y+z) 
Rearranging the terms to use also the diagonals properties we have:
3K = (r+v+z) + (x+v+t) + (s+u+w+y) -v
3K = (r+v+z) + (x+v+t) + (s+v+y -v + u+v+w -v) -v
3K = (r+v+z) + (x+v+t) + (s+v+y) + (u+v+w) -3v
3K = 4K -3v
3v = K
So: v = K/3

This tell us one thing about 3x3 magic squares: their constant is always a multiple of 3.

Having a direct relation between the magic square constant K and the center value, we can now write M differently:

let's name a the central value and use it as a reference, expressing each value as a + or - something:

    ( a+b   a-b-c  a+c   )
M = ( a-b+c a a+b-c )
( a-c a+b+c a-b )
Now we have an expression of M using only the central value a (which is equal to one third of the constant K) plus 2 others parameters b & c that can be positive or negative and are sufficient to completely define the magic square.


Calculating M2


If we calculate M*M, for the first element (top left) we have:
  (a+b)(a+b)         a2 + ab + ab + b2
+ (a-b-c)(a-b+c) = + a2 - ab + ac - ab + b2 - bc - ac + bc -c2
+ (a+c)(a-c) + a2 - ac + ac - c2

= 3a2 + 2b2 - 2c2

after calculating all terms we get the following matrix:
      ( 3a2+2b2-2c2  3a2-b2+c2    3a2-b2+c2  )
M*M = ( 3a2-b2+c2 3a2+2b2-2c2 3a2-b2+c2 )
( 3a2-b2+c2 3a2-b2+c2 3a2+2b2-2c2)

We can see that for M2 each row and column as well as the diagonal bottom left to top right has the same sum which is 9a2 = K2 (remember: a = K/3) , but the remaining diagonal (top left to bottom right) has a different sum so M2 is not a magic square.


Calculating M3


Now let's calculate M2*M.

First, what's the center value of M3:

  (3a2-b2+c2)(a-b-c)     3a3  -  ab2 +  ac2 - 3a2b + b3  + bc2 - 3a2c + b2c - c3   
+ (3a2+2b2-2c2)a = + 3a3 + 2ab2 - 2ac2
+ (3a2-b2+c2)(a+b+c) + 3a3 - ab2 + ac2 + 3a2b - b3 - bc2 + 3a2c - b2c + c3

= 9a3 (we can simplify a lot of terms above)
= 9(K/3)3
= K3/3

That starts to look interesting as we want to prove that M3 is a magic square with K3 as constant...

Let's continue with all terms (it took me some time to get it right ...) and we have:

     ( 9a3+3b3-3bc2           9a3-3b3+3c3+3bc2-3b2c  9a3-3c3+3b2c          ) 
M3 = ( 9a3-3b3-3c3+3bc2+3b2c 9a3 9a3+3b3+3c3-3bc2-3b2c )
( 9a3+3c3-3b2c 9a3+3b3-3c3-3bc2+3b2c 9a3-3b3+3bc2 )
If we add up each row, column or diagonal we can see now that M3 is a magic square with a constant of: 27a3 = 27(K/3) 3 = K3, so we are done !!!


Conclusion


As a conclusion, many thanks to Valentin for crafting the Mini-challenges. This one has been for me both challenging and rewarding as I've been able to solve it practically with the requested 15C program based on my intuitions and theoretically with a formal demonstration. Overall this was an excellent brain exercise !


Edited to fix a few typos.


Edited: 12 June 2009, 7:00 p.m.


#21

Hi, Didier:

Best regards from V.


#22

Valentin, thanks for contriving this challenge. I look forward to many more.

#23

Hi Valentin,

I find your original solution nicer than mine, even if they do the same thing in the same number of steps. Yours is more elegant with a similar structure for the two operations and looks simpler.

This is, I suppose, the Zen of RPN coding:


1) Operand:

    RCL MATRIX A   
ENTER
ENTER
2) First operation:
    RESULT B
*
2) Second operation:
    RESULT C
*
While my solution is mixing data, operations and result assignments and at the end seems more complex and less elegant (at least to me):
    RESULT B
RCL MATRIX A
ENTER
*
RESULT C
RCL MATRIX A
*
... a lot could be learned from even the smallest code.

The list of your HP-related challenges is amazing ! I've not realized there were so many as I'm quite a newbie on this forum (I've been hooked again on HP calculators last year when I got a 11C and a 35s, nearly 30 years after my 41C).

Didier

#24

Hi Valentin,

I didn't try your challenge but I've learned something by walking through this thread. Thanks for your efforts and ideas! Could you create an article with just the link list from this post. It could serve as a reference.

Marcus


#25

I'd like to second all of Markus' comments, an article with all the links would be most fabulous.

(I had come across that particular questions for magic squares when I was high-school and part of a little news-paper editor group with magic squares and the like where I had to come up with new magic squares on a regular basis... Without an HP calcs unfortunately, but a TI 52-II with I think 12 steps or something the like)

Thanks for your postings, its good to see you more around again!

Cheers

Peter

#26

It's again a real pleasure to ponder over your challenge.
It was both entertaining and instructive.

Many thanks, I am looking forward to trying the next one.
(I am going to bookmark the index of former challenges)


Possibly Related Threads...
Thread Author Replies Views Last Post
  HPCC Mini Conference 2013 hugh steers 6 966 09-13-2013, 04:27 PM
Last Post: BruceH
  Picture from the Mini-HHC (LA) Geir Isene 11 1,365 07-07-2013, 01:06 PM
Last Post: Jim Horn
  My birthday, so a little commemorative mini-challenge ! Valentin Albillo 43 4,155 03-07-2013, 03:44 AM
Last Post: Walter B
  WP 34S mini-challenge (B) Gerson W. Barbosa 17 1,912 12-27-2012, 04:39 PM
Last Post: Marcus von Cube, Germany
  Mini-challenge: HHC2012 RPL programming contest with larger input David Hayden 14 1,773 10-05-2012, 10:36 PM
Last Post: David Hayden
  HP41 / SY41CL Mini-B USB Power Connector (Module) Matt Kernal 5 1,892 07-08-2012, 06:23 PM
Last Post: Diego Diaz
  OT: Math, magic and shuffling cards Randy 0 380 12-11-2011, 09:49 AM
Last Post: Randy
  HP-15C (& LE!) 11-11-11 Mini-Challenge Valentin Albillo 28 2,766 11-14-2011, 08:12 AM
Last Post: Valentin Albillo
  Mini challenge. CEIL / FLOOR in RPN M. Joury 47 4,550 10-31-2011, 10:11 AM
Last Post: M. Joury
  Photo of my HP 15c | 15c LE DigiGal 2 710 10-12-2011, 12:34 PM
Last Post: DigiGal

Forum Jump: