| Ruud H.G. van Tol on Wed, 03 Jan 2024 12:33:10 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
| Re: Can I speed up / reduce the stack used by this PARI/GP script? |
On 2024-01-03 02:13, Joe Slater wrote:
I wrote the following script to calculate terms of A060322. It does a
decent job, but takes a lot of memory: at present I can only calculate
around 70 terms. Can anyone suggest a way to push it further?
A060322(n)= /* Provide an array from 1..n of the number of integers with a
stopping time of _n_ */
{
my(v=vector(n,i,[]));
v[1]=[1];
my(v2=v3=v4=[]);
if(n>4,
for(x=5,n,
v2=vector(x-1,i,[(x-1)/3| x<-2^(x-i)*v[i],(x%3)==1]);
v[x]=concat(v2);
)
);
v3=vector(#v,i,#v[i]);
v4=vector(#v,i,vecsum(v3[1..i]));
return(v4)
}
Stopping-time (reaching 1) is owned by dropping-time (reaching first lower-or-equal).
Dropping time is owned by residue classes. https://oeis.org/A100982 https://oeis.org/A368514/a368514.svg For example: 1 + i* 2^2 -> 1 + i* 3^1 2 + i* 2^1 -> 1 + i* 3^0 3 + i* 2^4 -> 2 + i* 3^2 7 + i* 2^7 -> 5 + i* 3^4 11 + i* 2^5 -> 10 + i* 3^3 etc. https://oeis.org/A243115 https://oeis.org/wiki/User:Ruud_H.G._van_Tol/Collatz#Dropping_structureWith these in mind, I presume that many shortcuts (dynamic lookup structures) can be used, to trade memory for speed.
-- Ruud