Challenge: sum of squares. Let's break 299
01-19-2018, 04:56 PM
Post: #13
 Didier Lachieze Senior Member Posts: 1,227 Joined: Dec 2013
RE: Challenge: sum of squares. Let's break 299
Yes, the timings are in seconds on the HP Prime Virtual Calculator, so it would take significantly more time on the physical Prime.

Here is my code (sorry, there is no comments), I'm using a recursive function to go through the different paths to find the solution. This may not be the most effective way of doing it, but it's quite simple and with recursion the backtracking is "built-in".

SoS(n) is the main function, that you call with the number of terms of the sequence.
rS(l) is the recursive function where most of the time is spent.
tSoS(n) is what I use to time the SoS function, it stores the result in L2.

To optimize the execution, at the beginning of SoS(n), I build a list of n sublists, each sublist being the list of numbers which added to sublist index give a square.

Code:
rS(l) BEGIN  LOCAL a,k,l1,l2,l3,p,s;  s:=SIZE(l);  a:=l(1);  IF s==1 THEN RETURN {1,a}; END;  l1:=l({2,s});  l2:= INTERSECT(l1,L1(a));  FOR k FROM 1 TO SIZE(l2) DO   p:=POS(l1,l2(k));   IF p>1 THEN l1:=CONCAT(l1({p,s-1}),l1({1,p-1})) END;   l3:=rS(l1);   IF l3(1) THEN    l3(0):=a;    RETURN l3;   END;  END;  RETURN {0}; END; EXPORT SoS(n) BEGIN  LOCAL j,k,l1,l2,l3,a;  L1:={};  FOR j FROM 1 TO n DO   L1(j):=DIFFERENCE(MAKELIST(I*(FP(√(j+I))==0),I,1,n),0);  END;  l1:=MAKELIST(I,I,1,n);  FOR j FROM 1 TO n DO   l2:=rS(l1);   IF l2(1) THEN    RETURN l2({2,n+1});   END;   l1(0):=l1(1);   l1:=l1({2,n+1});  END;  RETURN {0}; END; EXPORT tSoS(n) BEGIN  LOCAL t:=TICKS;  L2:=SoS(n);  RETURN (TICKS-t)/1000; END;

Some results (reversed from what my program returns to start with the lowest number):
Code:
57: {1,3,6,10,15,21,28,36,45,55,9,16,20,29,35,46,54,27,37,44,56,8,17,19,30,34,2,47,5​3,11,5,4,32,49,51,13,12,52,48,33,31,50,14,22,42,39,25,24,40,41,23,26,38,43,57,7,​18} 58: {1,3,6,10,15,21,28,36,45,55,9,16,20,5,4,32,49,51,13,12,37,44,56,8,41,40,24,57,43​,38,26,23,58,42,39,25,11,53,47,17,19,30,34,2,7,18,31,33,48,52,29,35,46,54,27,22,​14,50} 59: {1,3,6,10,15,21,28,36,45,55,9,16,20,29,35,46,54,27,37,44,56,8,17,19,30,34,2,47,5​3,11,5,4,32,49,51,13,12,52,48,33,31,50,14,22,59,41,40,24,25,39,42,58,23,26,38,43​,57,7,18} 60: {1,3,6,10,15,21,28,36,45,55,9,16,20,29,35,46,54,27,37,44,56,8,41,59,22,14,50,31,​33,48,52,12,13,51,49,32,17,19,30,34,2,47,53,11,5,4,60,40,24,25,39,42,58,23,26,38​,43,57,7,18} 61: {1,3,6,10,15,21,28,36,45,55,9,16,20,29,35,46,54,27,37,44,56,8,17,19,30,34,2,47,5​3,11,5,59,41,40,24,25,39,61,60,4,32,49,51,13,12,52,48,33,31,50,14,22,42,58,23,26​,38,43,57,7,18} 62: {1,3,6,10,15,21,28,36,45,55,9,16,20,29,35,46,54,27,37,44,56,8,17,19,30,34,47,53,​11,5,4,32,49,51,13,12,52,48,33,31,50,14,22,42,58,23,26,38,43,57,24,25,39,61,60,4​0,41,59,62,2,7,18} 63: {1,3,6,10,15,21,28,36,45,55,9,16,20,29,35,46,54,27,37,44,56,8,17,19,30,34,47,53,​11,14,50,31,33,48,52,12,13,51,49,32,4,5,59,22,42,58,63,18,7,2,62,38,43,57,24,25,​39,61,60,40,41,23,26} 64: {1,3,6,10,15,21,28,36,45,55,9,16,20,29,35,46,54,27,37,44,56,8,17,19,30,34,47,53,​11,5,59,62,2,7,18,63,58,42,22,14,50,31,33,48,52,12,13,51,49,32,4,60,61,39,25,24,​40,41,23,26,38,43,57,64}
 « Next Oldest | Next Newest »

 Messages In This Thread Challenge: sum of squares. Let's break 299 - pier4r - 01-18-2018, 09:32 PM RE: Challenge: sum of squares. Let's break 299 - TheKaneB - 01-18-2018, 10:58 PM RE: Challenge: sum of squares. Let's break 299 - Didier Lachieze - 01-19-2018, 12:08 AM RE: Challenge: sum of squares. Let's break 299 - Didier Lachieze - 01-19-2018, 12:15 PM RE: Challenge: sum of squares. Let's break 299 - Paul Dale - 01-19-2018, 04:29 AM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-20-2018, 05:43 PM RE: Challenge: sum of squares. Let's break 299 - John Keith - 01-20-2018, 08:19 PM RE: Challenge: sum of squares. Let's break 299 - Paul Dale - 01-20-2018, 10:13 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-20-2018, 10:31 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 02:17 AM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-19-2018, 04:29 AM RE: Challenge: sum of squares. Let's break 299 - Paul Dale - 01-19-2018, 06:31 AM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-19-2018, 06:48 AM RE: Challenge: sum of squares. Let's break 299 - pier4r - 01-19-2018, 12:40 PM RE: Challenge: sum of squares. Let's break 299 - Didier Lachieze - 01-19-2018, 12:47 PM RE: Challenge: sum of squares. Let's break 299 - Didier Lachieze - 01-19-2018, 04:26 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-19-2018, 04:33 PM RE: Challenge: sum of squares. Let's break 299 - Didier Lachieze - 01-19-2018 04:56 PM RE: Challenge: sum of squares. Let's break 299 - ggauny@live.fr - 01-20-2018, 06:15 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-20-2018, 09:08 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-21-2018, 05:41 AM RE: Challenge: sum of squares. Let's break 299 - Gilles59 - 01-21-2018, 10:44 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-22-2018, 01:40 AM RE: Challenge: sum of squares. Let's break 299 - TheKaneB - 01-22-2018, 11:54 AM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-22-2018, 01:11 PM RE: Challenge: sum of squares. Let's break 299 - TheKaneB - 01-22-2018, 03:19 PM RE: Challenge: sum of squares. Let's break 299 - Gilles59 - 01-22-2018, 08:49 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-24-2018, 09:18 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-24-2018, 09:43 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-24-2018, 10:03 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-24-2018, 10:08 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-24-2018, 10:14 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-24-2018, 10:16 PM RE: Challenge: sum of squares. Let's break 299 - TheKaneB - 01-24-2018, 10:22 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-24-2018, 10:29 PM RE: Challenge: sum of squares. Let's break 299 - pier4r - 01-25-2018, 05:54 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-24-2018, 10:32 PM RE: Challenge: sum of squares. Let's break 299 - Thomas Okken - 01-24-2018, 10:33 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 01:47 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 01:49 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 01:55 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 02:04 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 03:25 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 04:19 AM RE: Challenge: sum of squares. Let's break 299 - TheKaneB - 01-25-2018, 09:33 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 10:53 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-25-2018, 11:10 PM RE: Challenge: sum of squares. Let's break 299 - TheKaneB - 01-26-2018, 12:29 AM RE: Challenge: sum of squares. Let's break 299 - pier4r - 01-26-2018, 08:15 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-26-2018, 10:01 PM RE: Challenge: sum of squares. Let's break 299 - pier4r - 01-27-2018, 01:23 PM RE: Challenge: sum of squares. Let's break 299 - Massimo Gnerucci - 01-27-2018, 02:14 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 01-28-2018, 04:14 PM RE: Challenge: sum of squares. Let's break 299 - brickviking - 01-29-2018, 07:13 PM RE: Challenge: sum of squares. Let's break 299 - peacecalc - 01-30-2018, 02:51 PM RE: Challenge: sum of squares. Let's break 299 - Allen - 02-01-2018, 03:38 AM RE: Challenge: sum of squares. Let's break 299 - Allen - 02-01-2018, 03:40 AM RE: Challenge: sum of squares. Let's break 299 - TheKaneB - 02-01-2018, 10:54 AM

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