Little math problem(s) May 2021

[pier4r]

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

[Valentin Albillo]

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

[pier4r]

Hi Valentin!

Thank you for the reference!

[EdS2]

Wonderful! Nice to see HP pitted against CDC.

There are some hints to the method on this page:
short paper in pdf
longer paper in pdf

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

[PeterP]

Always love your posts Albert, as I learn so much. Can you help me grasp the a^5 = a(mod30) identity easily?

Thank you!

[Albert Chan]

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

[PeterP]

Thank you Albert, super instructive!!!

[pier4r]

Thank you all and EdS2 for the sources!

[PeterP]

(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