Little math problem(s) May 2021

[Albert Chan]

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.