Re: lookup-optimization

["Ruud H.G. van Tol" <rvtol@isolution.nl>]

Thanks a million both. 30 times faster.

Plenty for me to study and learn again.

-- Greetings, Ruud



A (potentially) lighter version for the lookup entries:

A243115_ok(v2)=
{ if
  ( v2 > 2 && 3 == v2 % 4
  , my
    ( v3= v2
    , i2= logint(v2, 2)
    , i= 0
    );

    until
    ( i++ > i2 || v3 <= v2
    , if
      ( bitand(v3, 1)
      , v3+= v3 >> 1 + 1
      , v3>>= 1
      )
    );
    i > i2
  , 0
  )
}

? select( v2->A243115_ok(v2),[i*4+3 |i<-[0..20]] )
% = [3, 7, 11, 15, 23, 27, 31, 39, 47, 59, 63, 71, 79]

(but then p2 isn't set yet)


On 2023-01-09 00:01, Bill Allombert wrote:
> On Sun, Jan 08, 2023 at 11:46:55PM +0100, Karim Belabas wrote:
> > A243115(N = 575) =
> > { my(r= [], s= Map());
> >    forstep(v2 = 3, N, 4,
> >      my(found = 0);
> >      for (i = 1, #s,
> >        if (valuation(s[i][2] - v2, 2) >= s[i][1], found = 1; break));
> >      if (found, next);
> >
> >      my(p2 = 0, v3 = v2);
> >      until (v3 <= v2,
> >        if (bitand(v3,1), v3 += v3 >> 1 + 1;
> >                        , v3 >>= 1);
> >        p2++);
> >      r = concat(r, v2);
> >      s = mapput(~s, v2,p2));
> >    r;
> > }
> By merging with my version I get
>
> A243115(N = 575) =
> { my(r= List(), s= Map());
>    forstep(v2 = 3, N, 4,
>      for(i=1,logint(v2,2)+1,
>        my(nv2=v2%2^i,p2);
>        if (mapisdefined(s,nv2,&p2) && nv2==v2%2^p2, next(2)));
>      my(p2 = 0, v3 = v2);
>      until (v3 <= v2,
>        if (bitand(v3,1), v3 += v3 >> 1 + 1;
>                        , v3 >>= 1);
>        p2++);
>      listput(~r, v2);
>      mapput(~s, v2,p2));
>    Vec(r);
> }
>
> ? A243115(10^5);
>    ***   last result computed in 168 ms.
> ? A243115(10^6);
>    ***   last result computed in 1,936 ms.
>
> (concat is very slow!)