Little math problem(s) May 2021
04-30-2021, 08:54 PM
Post: #1
 pier4r Senior Member Posts: 2,075 Joined: Nov 2014
Little math problem(s) May 2021
I wanted to leave one little problem as usual, hopefully it won't be too trivial but neither too overwhelming.

This is one among of the shortest math publications Anyway they didn't provide the code through which they found the result (although one can suspect they optimized it a bit, despite the CDC6600 being a beast at the time).

Thus the task would be to write a code, for a calculator, that finds the counterexample in an optimized way (as otherwise the search space can blow up), of course aside from hardcoding or nearly hardcoding the counterexample.

----------------

Small digression: I have a lot of backlog to catch up but as usual I have to find the time for it (at the end a matter of priority as the days cannot get longer). It is still awesome that the community continues to thrive (I see at the moment 400 active users, I remember in 2019 they were like 200). For example I need to catch up with the results posted here: https://www.hpmuseum.org/forum/thread-9750.html where a lot of results needs to be put on wiki4hp and the first page of the thread. Thank you to continue giving stats and sorry if I am inconsistently caring about some threads since 2019 (others can create parallel lists if they want of course).

Wikis are great, Contribute :)
04-30-2021, 10:49 PM
Post: #2 Valentin Albillo Senior Member Posts: 776 Joined: Feb 2015
RE: Little math problem(s) May 2021
.
Hi, Pier:

I already posted that problem 15 years ago in this message:

Short & Sweet Math Challenge: Cooking Conjectures

My own solution was

1 DESTROY ALL @ OPTION BASE 0 @ K=150 @ DIM P(K)
2 FOR I=0 TO K @ P(I)=I*I*I*I*I @ NEXT I @ R=.2 @ L=2^R @ M=3^R @ N=4^R
3 FOR E=K TO 1 STEP -1 @ T=P(E) @ DISP E
4 FOR D=E-1 TO E/N STEP -1 @ F=T-P(D) @ U=F^R
5 FOR C=INT(U) TO U/M STEP -1 @ G=F-P(C) @ V=G^R @ FOR B=INT(V) TO V/L STEP -1
6 IF NOT FP((G-P(B))^R) THEN A=(G-P(B))^R @ DISP A;B;C;D;E @ END
7 NEXT B @ NEXT C @ NEXT D @ NEXT E

upon running, it eventually outputs:

>RUN

27 84 110 133 144

which is the sought-for counterexample, 13 seconds on Emu71, 90 min on a physical HP-71B.

Regards.
V.

All My Articles & other Materials here:  Valentin Albillo's HP Collection

05-01-2021, 07:34 AM
Post: #3
 pier4r Senior Member Posts: 2,075 Joined: Nov 2014
RE: Little math problem(s) May 2021
Hi Valentin!

Thank you for the reference!

Wikis are great, Contribute :)
05-01-2021, 02:51 PM
Post: #4
 EdS2 Senior Member Posts: 323 Joined: Apr 2014
RE: Little math problem(s) May 2021
Wonderful! Nice to see HP pitted against CDC.

short paper in pdf
longer paper in pdf
05-01-2021, 03:12 PM
Post: #5
 Albert Chan Senior Member Posts: 1,589 Joined: Jul 2018
RE: Little math problem(s) May 2021
Restricting A ≤ B ≤ C ≤ D, we can improve speed of Valentin's code (Patch in bold)

1 DESTROY ALL @ OPTION BASE 0 @ K=150 @ DIM P(K)
2 FOR I=0 TO K @ P(I)=I*I*I*I*I @ NEXT I @ R=.2 @ L=2^R @ M=3^R @ N=4^R
3 FOR E=K TO 1 STEP -1 @ T=P(E) @ DISP E
4 FOR D=E-1 TO E/N STEP -1 @ F=T-P(D) @ U=F^R
5 FOR C=MIN(D,INT(U)) TO U/M STEP -1 @ G=F-P(C) @ V=G^R @ FOR B=MIN(C,INT(V)) TO V/L STEP -1
6 IF NOT FP((G-P(B))^R) THEN A=(G-P(B))^R @ DISP A;B;C;D;E @ END
7 NEXT B @ NEXT C @ NEXT D @ NEXT E

My Pentium 3 box finished code, from 24.72 to 14.16 sec, speed 1.75X

---

Instead of brute force for solution, we can use (mod 30)

Identity: a^5 ≡ a (mod 30)

For example, if E=144, D=141, C=78, we have:

G = A^5 + B^5 = E^5 - D^5 - C^5 = 3299353155
G ≡ A + B ≡ E - D - C ≡ 144 - 141 - 78 ≡ 15 (mod 30)

max(B) = min(C, floor(G^0.2)) = min(78, 80) = 78

We can replace variable A, by valid mod30 cases:
If B = 78, then A ≡ 15 - 78 ≡ 27 (mod 30)

This simplified tests to two equations, of single variable, x:
G = (27+x)^5 + (78-x)^5
G = (57+x)^5 + (78-x)^5

To optimize further, we have (a^5 + b^5) divisible by (a+b)
1st equation, G must be divisible by (27+x) + (78-x) = 105
2nd equation, G must be divisible by (57+x) + (78-x) = 135

Unfortunately, G satsified both(*). But, with table of 5th-power, testing is easy !

27^5 + 78^5 - G = -397829880 < 0
57^5 + 78^5 - G = +189513270
58^5 + 77^5 - G = +63787770
59^5 + 76^5 - G = -48903480 < 0

Since A ≤ B, with increasing x, RHS will stay negative.
→ A^5 + B^5 + 78^5 + 141^5 = 144^5 have no integer solution.

This MOD version finished in 4.81 sec. Speed 24.72/4.81 ≈ 5.14X

1 DESTROY ALL @ OPTION BASE 0 @ K=150 @ DIM P(K)
2 FOR I=0 TO K @ P(I)=I*I*I*I*I @ NEXT I @ R=.2 @ M=3^R @ N=4^R
3 FOR E=K TO 1 STEP -1 @ T=P(E) @ DISP E
4 FOR D=E-1 TO E/N STEP -1 @ F=T-P(D) @ U=F^R
5 FOR C=MIN(D,INT(U)) TO U/M STEP -1 @ G=F-P(C) @ H=MIN(D,INT(G^R))
6 FOR L=MOD(G-H,30) TO H STEP 30 @ IF MOD(G,L+H) THEN 10
7 FOR X=0 TO (H-L)/2 @ Y=P(L+X)+P(H-X) @ IF Y<G THEN 10
8 IF Y=G THEN DISP L+X;H-X;C;D;E @ END
9 NEXT X
10 NEXT L @ NEXT C @ NEXT D @ NEXT E

(*) I specifically picked a case where (mod a+b) test passes.
Screening is actually very good. For E=144, it removed >90% of cases.
05-03-2021, 10:19 PM
Post: #6 PeterP Member Posts: 137 Joined: Jul 2015
RE: Little math problem(s) May 2021
Always love your posts Albert, as I learn so much. Can you help me grasp the a^5 = a(mod30) identity easily?

Thank you!

Cheers,

PeterP
05-04-2021, 04:33 AM (This post was last modified: 05-04-2021 11:26 AM by Albert Chan.)
Post: #7
 Albert Chan Senior Member Posts: 1,589 Joined: Jul 2018
RE: Little math problem(s) May 2021
(05-03-2021 10:19 PM)PeterP Wrote:  Always love your posts Albert, as I learn so much. Can you help me grasp the a^5 = a(mod30) identity easily?

a^5 - a
= (a^4-1)*a
= (a-1)*a*(a+1) * (a²+1)
= (a-1)*a*(a+1) * ((a+2)*(a+3) - 5*(a+1))
= (a-1)*a*(a+1)*(a+2)*(a+3) ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ - ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ 5*(a-1)*a*(a+1)²

Both terms are divisible by 30, so does (a^5 -a)

Or, we can use 5 is prime → a^5 ≡ a (mod 5) ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ -- Fermat's little theorem

(a^5 - a) has factor 2, 3 and 5, thus divisible by 2*3*5 = 30

Brute force also very easy (only 3 points needed), for f(a) = a^5 - a

f(0) = 0
f(1) = 1 - 1 = 0
f(2) = 32 - 2 = 30 = 6*5

Because f(a) is odd function, we have these for free: f(-1) = -0, f(-2) = -6*5

a^5 - a ≡ 0 (mod2, mod3 and mod5)
a^5 - a ≡ 0 (mod 30)
05-04-2021, 09:34 AM
Post: #8 PeterP Member Posts: 137 Joined: Jul 2015
RE: Little math problem(s) May 2021
Thank you Albert, super instructive!!!

Cheers,

PeterP
05-04-2021, 06:26 PM
Post: #9
 pier4r Senior Member Posts: 2,075 Joined: Nov 2014
RE: Little math problem(s) May 2021
Thank you all and EdS2 for the sources!

Wikis are great, Contribute :)
05-06-2021, 11:29 PM
Post: #10 PeterP Member Posts: 137 Joined: Jul 2015
RE: Little math problem(s) May 2021
(04-30-2021 08:54 PM)pier4r Wrote:  I wanted to leave one little problem as usual, hopefully it won't be too trivial but neither too overwhelming.

This is one among of the shortest math publications Anyway they didn't provide the code through which they found the result (although one can suspect they optimized it a bit, despite the CDC6600 being a beast at the time).

Thus the task would be to write a code, for a calculator, that finds the counterexample in an optimized way (as otherwise the search space can blow up), of course aside from hardcoding or nearly hardcoding the counterexample.

----------------

Loved the idea of trying to get it out of the HP41CX. Code below, not particularly optimized (or using any of Albert's ingenious knowledge), gets the solution for 144 in 6 minutes 3 seconds, and that there is no solution for 145 in 13 minutes and 39 seconds. (on the i41CX emulator).

The code uses that the 4 numbers are increasing in size. Starting from the largest possible number to be part of the sequence, and sees if it is possible to find a solution with that. Doing this recursively from 4 to 3 to 2 numbers, stopping whenever it has gone over the threshold or no solution is possible.

Equation to check: a^5 + b^5 + c^5 + d^5 = e^5

Variables:
STO 20 : d^5
STO 21: Trial for d (d_i)
STO 22: max possible d
STO 10 : e^5 - d_i^5
STO 11: trial for c (c_i)
STO 12: max possible c, given d_i
STO 00: e^5 - d_i^5 - c_i^5
STO 01: trial for b (b_i)
STO 02: max possible b, given d_i, c_i

STO 15 : 5 (hp number entry is slow...)
STO 14 : 1/5
STO 03 : 0.000001 (precision of HP 41 arithmetic is not good enough to calculate fifth roots from O(1e10) with sufficient accuracy.

STO 16 : start time
STO 17 : total duration for solution

Flag 0 = solution found
Flag 5 = do not play a tone

Code:
 Lbl 'QQQQ STO 20 5  STO 15 1/x  STO 14 0.000001  STO 03 CF 00 TIME STO 16 2 RCL 15 Y^x 3 RCL 15 y^x + INCX CHS RCL 20 + RCL 14 Y^x INT STO 21 STO 22 4 RCL 14 Y^x ST/ 22 LBL 00 RCL 21 VIEW X RCL 15 Y^x CHS RCL 20 + XEQ 'QQQ FS?C 00 GTO'FOUND RCL 21 DECX STO 21 RCL 22 X>Y? GRO 'NF GTO 00 LBL'FOUND BEEP TIME RCL 16 HMS- STO 17 CLX RCL 21 'SOLUTION AVIEW STOP END LBL 'QQQ STO 10 DECX 2 RCL 15 Y^x - RCL 14 Y^x INT STO 11 STO 12 RCL 21 X<Y? RTN 3 RCL 14 Y^x ST/ 12 LBL 00 RCL 11 RCL 15 Y^x CHS RCL 10 + XEQ 'QQ FS?C 00 GTO 'FND RCL 11 DECX STO 11 RCL 12 X>Y ? RTN GTO 00 LB 'FND 'FOUND QQQ RCL 11 AVIEW SF 00 RTN END LBL 'QQ STO 00 DECX RCL 14 Y^x INT STO 01 STO 02 RCL 11 X<Y? RTN 2 RCL 14 Y^x ST/ 02 LBL 00 RCL 01 RCL 15 Y^x CHS RCL 00 + RCL 14 Y^x ENTER CEIL - ABS RCL 03 X>Y? GTO 'FF RCL 01 DECX STO 01 RCL 02 X>Y? RTN GTO 00 LBL 'FF 'FOUND SF 00 BEEP RCL 01 AVIEW RTN

Cheers,

PeterP
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)