Quiet Week-end Challenge (49G?) - Closed
|
05-09-2015, 10:50 AM
(This post was last modified: 05-16-2015 07:34 AM by Gerald H.)
Post: #1
|
|||
|
|||
Quiet Week-end Challenge (49G?) - Closed
Challenge is to write a programme that produces a list of four even integers & a list of four odd integers which, on respectively squaring & summing the elements give the same total.
eg { 34388 8306 13454 23910 } & { 18269 40029 2665 7813 }. The programme should be able to produce at least 5,789,854 different pairs of lists. |
|||
05-10-2015, 04:41 PM
(This post was last modified: 05-10-2015 04:43 PM by Gerson W. Barbosa.)
Post: #2
|
|||
|
|||
RE: Quiet Week-end Challenge (49G?)
(05-09-2015 10:50 AM)Gerald H Wrote: The programme should be able to produce at least 5,789,854 different pairs of lists. Do these include lists with elements equal 0 or repeated elements like {18084, 13782, 2, 2} {2469 11357 8643 17527}, for instance? {15914 12474 12 2} {2469 17513 8643 4621} is a valid pair, but in order to find it I had to find at least one solution to the equation a² + b² + c² + d² = 102214055 (a = 7957, b = 6237, c = 6, d = 1). I don't know whether the HP-49G CAS has something that solves this. Anyway, I think a much more powerful method is required to solve this quiet challenge of yours. I am looking forward to your (and other's) interesting solutions. Gerson. |
|||
05-10-2015, 05:11 PM
(This post was last modified: 05-10-2015 05:21 PM by Gerald H.)
Post: #3
|
|||
|
|||
RE: Quiet Week-end Challenge (49G?)
Yes, repeated elements & zeros permitted, also negative numbers - zeros only in the evens list!
Bravo on finding a solution - the first & only so far, but here's one more { 31109 355553 355553 26669 } { 384442 326664 2220 2220 } |
|||
05-10-2015, 06:26 PM
(This post was last modified: 05-10-2015 06:59 PM by Gerson W. Barbosa.)
Post: #4
|
|||
|
|||
RE: Quiet Week-end Challenge (49G?)
(05-10-2015 05:11 PM)Gerald H Wrote: Yes, repeated elements & zeros permitted, also negative numbers - zeros only in the evens list! Thanks! Just a little explanation on how I did it: Let a, b, c, d, e, f, g and h be positive integer numbers. Then 2a, 2b, 2c and 2d are even numbers and (2e + 1), (2f + 1), (2g + 1) and (2h + 1) are odd numbers Thus, a² + b² + c² + d² = (2e + 1)² + (2f + 1)² + (2g + 1)² + (2h + 1)² ... ..... a² + b² + c² + d² = e² + f² + g² + h² + e + f + g + h + 1 So, in order to find pairs of list it suffices to choose four arbitrary integers, e, f, g and h, and solve the equation. For instance, e = 15, f = 10, g = 18 and h = 23. Then a² + b² + c² + d² = 15² + 10² + 18² + 23² + 15 + 10 + 18 + 23 + 1 a² + b² + c² + d² = 1245 Lagrange's four-square theorem says that every natural number can be represented as the sum of four integer squares. This means there will always be integer solutions for the equation above, but finding them is a problem. In this case, one solution is a = 2, b = 4, c =21 and d = 28 (WolframAlpha lists them all). Thus, the list of even and odd numbers are, respectively: { 4 8 42 56 } and { 31 21 37 47} 4² + 8² + 42² + 56² = 31² + 21² + 37² + 47² = 4980 This doesn't appear to be a promising method, though. Edited to fix a typo |
|||
05-10-2015, 06:37 PM
Post: #5
|
|||
|
|||
RE: Quiet Week-end Challenge (49G?)
There must be a typo in this line:
a² + b² + c² + d² = e² + f² + g² + d² + e + f + g + h + 1 |
|||
05-10-2015, 06:42 PM
Post: #6
|
|||
|
|||
RE: Quiet Week-end Challenge (49G?)
Lagrange' four square theorem does NOT say it's always possible with four evens, nor that it's always possible with four odds.
|
|||
05-10-2015, 06:59 PM
Post: #7
|
|||
|
|||
RE: Quiet Week-end Challenge (49G?) | |||
05-10-2015, 07:03 PM
(This post was last modified: 05-10-2015 07:03 PM by Gerson W. Barbosa.)
Post: #8
|
|||
|
|||
RE: Quiet Week-end Challenge (49G?)
(05-10-2015 06:42 PM)Gerald H Wrote: Lagrange' four square theorem does NOT say it's always possible with four evens, nor that it's always possible with four odds. You are right, but the four unknowns (a, b, c and d) are not the even numbers I was looking for. Their doubles are. Likewise, e, f, g and h are arbitrarily odd or even. When doubled and increased by one they become odd. |
|||
05-10-2015, 07:15 PM
Post: #9
|
|||
|
|||
RE: Quiet Week-end Challenge (49G?)
Yes. I'm not always really helpful.
The interesting point, I think, is that there's a bijection between the sets of 4 even squares & 4 odd squares that partition an integer. By the way, I should say I'm only interested in primitive solutions. If you multiply your solution by 97 you'll get another solution, but it wouldn't be essentially different. |
|||
05-13-2015, 11:26 AM
Post: #10
|
|||
|
|||
RE: Quiet Week-end Challenge (49G?)
(05-09-2015 10:50 AM)Gerald H Wrote: Challenge is to write a programme that produces a list of four even integers & a list of four odd integers which, on respectively squaring & summing the elements give the same total. I'm part of the way there, I think. My program looks only at lists whose elements are in the range [0, 200) and finds 935 614 406 different pairs from [[1, 1, 1, 1], [0, 0, 0, 2]] to [[197, 197, 197, 199], [196, 198, 198, 198]] with 17 467 different sums of squares. It's not very interesting that the elements are such small integers, but I suppose I could "fix" that by seeding using consecutive primes instead of consecutive integers, or by generating additional pairs using Euler's four-square identity. The glaring deficiency is that this isn't running on a calculator but on my ancient laptop. However, as the stated problem is to find only 5 789 854 different pairs of lists, I'm optimistic that the calculator might be fast enough to run a stripped down version without taking too many hours to complete. The main problems with porting this solution to the calculator are shortage of memory and storage. During the running of my solution I have as many as 27 749 sums of squares and as many as 6 708 871 4-element lists in memory at once and my output file is approximately 176 MB. Of course these numbers would be considerably smaller if I'm only trying to produce 5 789 854 different pairs of lists, and there's scope for some optimisation. The other problem is that I've rarely programmed a calculator since I had my old HP-28S! The main blockers so far is that looking in the AUR I can't find the following information for the 50g: 1. The size of an integer object. 2. The size-overhead of a list beyond it's contents. 3. The maximum allowed size of a list object. 4. The maximum allowed size of a string object. 5. How to write a text file to SD card. (Just save a string object to Port 3?) |
|||
05-13-2015, 11:54 AM
Post: #11
|
|||
|
|||
RE: Quiet Week-end Challenge (49G?)
nlj - you don't have to produce all the pairs, it just has to be possible using your algorithm.
Answers to 1 BYTES command, or SIZE if you want number of decimal digits; 3 Unlimited; 4 Unlimited; 5 Yes. |
|||
05-13-2015, 10:37 PM
(This post was last modified: 05-14-2015 04:04 PM by Gilles.)
Post: #12
|
|||
|
|||
RE: Quiet Week-end Challenge (49G?)
EDIT v2
Slow and trivial but this returns the 377 first results (far below 5,789,854 ![]() EDIT : 728 solutions with a 0 to 14 loop... HP50G + Gofer List Code: « |
|||
05-16-2015, 07:34 AM
Post: #13
|
|||
|
|||
RE: Quiet Week-end Challenge (49G?)
Unlike New Scientist
https://enigmaticcode.wordpress.com/2011...es-harder/ I will not allow this puzzle to drag on for 31 years. Here an HP 38G programme to produce the desired even & odd lists: Store a list of four integers (pos, neg or zero, repetitions allowed) in L1 & actuate the programme, returning the two lists in L2 & L3. O4SQE4SQ 4*L1+1►L2: L1(2) ►B: L1(3) ►C: L1(4) ►D: 2*(L1(1)+{B+C+D+1,D-B-C,C-B-D,B-C-D})►L3: Honorable mentions for Gerson, nlj & Gilles. |
|||
05-16-2015, 02:13 PM
Post: #14
|
|||
|
|||
RE: Quiet Week-end Challenge (49G?) - Closed
(05-16-2015 07:34 AM)Gerald H Wrote: Here an HP 38G programme to produce the desired even & odd lists: HP 49G/50g version: Code:
0 0 0 0 --> {2. 0. 0. 0.} {1. 1. 1. 1.} 10000 1 1 -4321 --> {11364. 11354. 28642. 28642.} {40001. 5. 5. -17283.} |
|||
05-16-2015, 02:25 PM
Post: #15
|
|||
|
|||
RE: Quiet Week-end Challenge (49G?) - Closed
Instead of "a NEG -" you could have "a ADD".
|
|||
05-16-2015, 02:47 PM
(This post was last modified: 05-16-2015 02:49 PM by Gerson W. Barbosa.)
Post: #16
|
|||
|
|||
RE: Quiet Week-end Challenge (49G?) - Closed | |||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 1 Guest(s)