Challenge: sum of squares. Let's break 299

[Didier Lachieze]

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}