Quiet Week-end Challenge (49G?) - Closed

[Gerald H]

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.

[Gerson W. Barbosa]

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

[Gerald H]

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 }

[Gerson W. Barbosa]

(05-10-2015 05:11 PM)Gerald H Wrote:  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 }

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

[Gerald H]

There must be a typo in this line:
a² + b² + c² + d² = e² + f² + g² + d² + e + f + g + h + 1

[Gerald H]

Lagrange' four square theorem does NOT say it's always possible with four evens, nor that it's always possible with four odds.

[Gerson W. Barbosa]

(05-10-2015 06:37 PM)Gerald H Wrote:  There must be a typo in this line:
a² + b² + c² + d² = e² + f² + g² + d² + e + f + g + h + 1

Fixed. Thanks!

[Gerson W. Barbosa]

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

[Gerald H]

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.

[nlj]

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

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.

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

[Gerald H]

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.

[Gilles]

EDIT v2

Slow and trivial but this returns the 377 first results (far below 5,789,854 (*)) in a few minutes with the emulator

EDIT : 728 solutions with a 0 to 14 loop...

HP50G + Gofer List

Code:

«
 {}
 0 12 FOR A
  0 12 FOR B
   0 12 FOR C
    0 12 FOR D
     A B C D 4. ->LIST SORT  
     DUP2 IF POS NOT THEN 1. ->LIST + ELSE DROP END
     A   1. DISP
     MEM 2. DISP
    2 STEP
   2 STEP
  2 STEP
 2 STEP 

 DUP 1. «1 ADD» DOSUBS

 1. «SQ ΣLIST» DOSUBS 
 SWAP
 1. «SQ ΣLIST» DOSUBS  

 DUP2 Intersect Nub
 UNROT ->STR SWAP ->STR
 
 -> Even Odd
 «
  1. «  " " SWAP + " " +  Even OVER " " SREPL NIP SWAP Odd SWAP " " SREPL NIP * » DOSUBS
  ΣLIST
 »
»

[Gerald H]

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.

[Gerson W. Barbosa]

(05-16-2015 07:34 AM)Gerald H Wrote:  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:

HP 49G/50g version:

Code:


%%HP: T(3)A(R)F(.);
\<< 4. \->LIST DUP OBJ\-> DROP \-> a b c d
  \<< b c + d + 1. + d b - c - c b - d - b c - d - 4. \->LIST a NEG - 2. * SWAP 4. * -1. -
  \>>
\>>

0 0 0 0 --> {2. 0. 0. 0.} {1. 1. 1. 1.}
10000 1 1 -4321 --> {11364. 11354. 28642. 28642.} {40001. 5. 5. -17283.}

[Gerald H]

Instead of "a NEG -" you could have "a ADD".

[Gerson W. Barbosa]

(05-16-2015 02:25 PM)Gerald H Wrote:  Instead of "a NEG -" you could have "a ADD".

Yes, if I'd been aware of that usage of ADD. This might be better in this case, even though it's one nibble longer than NEG -. Thanks!