lookup-optimization

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

In the below code I build up a set 's',
against which I first check each new case
for "congruence".

If no such case was found,
then the new case gets added to the set.

Each element of 's' is a tuple
of a power-of-2 and an offset.

(1) I wonder if Mod() is better for that. Or store the sum?
(2) Would vecsearch() be good to use for this?
(3) Any ideas on doing things differently, are welcome.

-- Greetings, Ruud

- - - - - - - - - - - - - - - - - - -

A243115( N=575, V=0 )= {
  my
  ( r= []  /* result */
  , s= []  /* lookup-set */
  , t= [ [1,2,1,1], [2,1,1,0] ]  /* detailed table */
  );

  forstep
  ( v2= 3, N, 4
  , my( found= 0 );
    for /* Look up v2-class in s */
    ( i=1, #s
    , if
      ( s[i][2] == v2 % 2^s[i][1]
      , found= 1;
        break;
      );
    );
    if( found, next );

    my( p2= 0, p3= 0, v3= v2 );
    until
    ( v3 <= v2  /* until drop */
    , if
      ( v3 % 2
      , v3+= v3\2 + 1; p3++;
      , v3\= 2;
      );
      p2++;
    );
    r= concat(r, v2); /* store */
    s= Set( concat(s, [ [p2, v2] ]) );
    if( 1 < V, t= concat(t, [ [v2, p2, v3, p3] ]) );
  );

  if
  ( 1 < V  /* p.table */
  , for
    ( i=1, #t
    , my( [v2, p2, v3, p3]= t[i] );
      printf
      ( "%4s + i* 2^%3s -> %4s +i* 3^%3s\n"
      , v2, p2, v3, p3
      );
    );
    print("[...]")
  );
  if( V, print("s=", s) ); /* p.lookup-set */
  print("r=", r);  /* p.result */
}

See also https://oeis.org/A243115

? A243115();  \\ non-verbose run (default)
r=[3, 7, 11, 15, 23, 27, 31, 39, 47, 59, 63, 71, 79, 91, 95, 103, 111, 
123, 127, 155, 159, 167, 175, 191, 199, 207, 219, 223, 231, 239, 251, 
255, 283, 287, 303, 319, 327, 347, 359, 367, 383, 411, 415, 423, 447, 
463, 479, 487, 495, 507, 511, 539, 543, 559, 575]
cpu time = 4 ms, real time = 4 ms.

? A243115( 100, 2 );  \\ verbose run
[...]

? A243115(10^5);
r=[...]
cpu time = 5,156 ms, real time = 5,192 ms.

-o-o-o-o-o-o-o-o-