The following code is faster, and in your PC much faster than mine...

In my Pc, i get: boo // Timing, = {33.633816, 5482660}.

But with:

JesusCA =
Compile[{{kk, _Integer}},
Module[{}, ptable = Map[(3 #^2 - #)/2 &, Range@4500];
k = kk; out = 0; While[And[k > 1, out == 0],
atk = ptable[];
Do[atj = ptable[];
If[MemberQ[ptable, atk - atj] && MemberQ[ptable, atk + atj],
out = atk - atj;]
, {j, k - 1, 1, -1}]; k--]; out
], RuntimeAttributes -> {Listable}, Parallelization -> True];

JesusCA[2250] // Timing
 
{24.866559, 5482660}

My pc is slower than yours, but my code in faster. Bye.

Now