Little math problem(s) May 2021

04302021, 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 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/thread9750.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 :) 

04302021, 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=E1 TO E/N STEP 1 @ F=TP(D) @ U=F^R 5 FOR C=INT(U) TO U/M STEP 1 @ G=FP(C) @ V=G^R @ FOR B=INT(V) TO V/L STEP 1 6 IF NOT FP((GP(B))^R) THEN A=(GP(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 soughtfor counterexample, 13 seconds on Emu71, 90 min on a physical HP71B. Regards. V. All My Articles & other Materials here: Valentin Albillo's HP Collection 

05012021, 07:34 AM
Post: #3




RE: Little math problem(s) May 2021
Hi Valentin!
Thank you for the reference! Wikis are great, Contribute :) 

05012021, 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 

05012021, 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=E1 TO E/N STEP 1 @ F=TP(D) @ U=F^R 5 FOR C=MIN(D,INT(U)) TO U/M STEP 1 @ G=FP(C) @ V=G^R @ FOR B=MIN(C,INT(V)) TO V/L STEP 1 6 IF NOT FP((GP(B))^R) THEN A=(GP(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 + (78x)^5 G = (57+x)^5 + (78x)^5 To optimize further, we have (a^5 + b^5) divisible by (a+b) 1st equation, G must be divisible by (27+x) + (78x) = 105 2nd equation, G must be divisible by (57+x) + (78x) = 135 Unfortunately, G satsified both(*). But, with table of 5thpower, 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=E1 TO E/N STEP 1 @ F=TP(D) @ U=F^R 5 FOR C=MIN(D,INT(U)) TO U/M STEP 1 @ G=FP(C) @ H=MIN(D,INT(G^R)) 6 FOR L=MOD(GH,30) TO H STEP 30 @ IF MOD(G,L+H) THEN 10 7 FOR X=0 TO (HL)/2 @ Y=P(L+X)+P(HX) @ IF Y<G THEN 10 8 IF Y=G THEN DISP L+X;HX;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. 

05032021, 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 

05042021, 04:33 AM
(This post was last modified: 05042021 11:26 AM by Albert Chan.)
Post: #7




RE: Little math problem(s) May 2021
(05032021 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^41)*a = (a1)*a*(a+1) * (a²+1) = (a1)*a*(a+1) * ((a+2)*(a+3)  5*(a+1)) = (a1)*a*(a+1)*(a+2)*(a+3)  5*(a1)*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) 

05042021, 09:34 AM
Post: #8




RE: Little math problem(s) May 2021
Thank you Albert, super instructive!!!
Cheers, PeterP 

05042021, 06:26 PM
Post: #9




RE: Little math problem(s) May 2021
Thank you all and EdS2 for the sources!
Wikis are great, Contribute :) 

05062021, 11:29 PM
Post: #10




RE: Little math problem(s) May 2021
(04302021 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. 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:
Cheers, PeterP 

« Next Oldest  Next Newest »

User(s) browsing this thread: