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,53,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,53,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,53,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,40,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}
|