Post Reply 
Little math problem(s) May 2021
04-30-2021, 08:54 PM
Post: #1
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
[Image: shortest-math-paper.jpg]

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 :)
Find all posts by this user
Quote this message in a reply
04-30-2021, 10:49 PM
Post: #2
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
 
Visit this user's website Find all posts by this user
Quote this message in a reply
05-01-2021, 07:34 AM
Post: #3
RE: Little math problem(s) May 2021
Hi Valentin!

Thank you for the reference!

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
05-01-2021, 02:51 PM
Post: #4
RE: Little math problem(s) May 2021
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
Find all posts by this user
Quote this message in a reply
05-01-2021, 03:12 PM
Post: #5
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.
Find all posts by this user
Quote this message in a reply
05-03-2021, 10:19 PM
Post: #6
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
Find all posts by this user
Quote this message in a reply
05-04-2021, 04:33 AM (This post was last modified: 05-04-2021 11:26 AM by Albert Chan.)
Post: #7
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)
Find all posts by this user
Quote this message in a reply
05-04-2021, 09:34 AM
Post: #8
RE: Little math problem(s) May 2021
Thank you Albert, super instructive!!!

Cheers,

PeterP
Find all posts by this user
Quote this message in a reply
05-04-2021, 06:26 PM
Post: #9
RE: Little math problem(s) May 2021
Thank you all and EdS2 for the sources!

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
05-06-2021, 11:29 PM
Post: #10
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
[Image: shortest-math-paper.jpg]

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

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
Find all posts by this user
Quote this message in a reply
Post Reply 




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