Re: Can I speed up / reduce the stack used by this PARI/GP script?

[Joe Slater <joe@slatermold.com>]

> I presume that many shortcuts (dynamic lookup structures) can be used, to trade memory for speed.

My current code already does that to some extent by not storing each n, 2n, 4n, etc, but just calculating them as needed. I did consider using more complicated methods like the ones you suggest, but I was hoping to avoid them!

Yours,

Joe Slater

On 3 Jan 2024, at 10:33 pm, Ruud H.G. van Tol <rvtol@isolution.nl> wrote:


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_structure

With these in mind, I presume that many shortcuts (dynamic lookup structures) can be used, to trade memory for speed.

-- Ruud