(33s) OEIS A2516: EARLIEST SEQUENCE WITH A(A(N)) = 2N

[C.Ret]

(08-21-2022 01:05 PM)John Keith Wrote:  Could there be a typo in your code?

Sure, I type an '*' where a '+' is needed in the code !!
Sorry for that, corrected code is :

A2516:
« → m « { m } 0 CON 1 SF                       // Build array [ 0 0 ... 0 ] of size { m } and initialze flag n°1
   1 m FOR k                            // For each element of the array
      k                              // k-th element
         DUP 2 MOD                      // parity of k for IF THEN ELSE structure
         « k 2 + IF 1 FC?C THEN k 6 - + 1 SF END »   // k=2n+1: alternate a(k)=a(2n+1)=2n+3=k+2 when n is even   and  a(k)=a(2n+1)=4n-2=2k-4 when n is odd
         « OVER k 2 / GET 2 * »               // k=2n: a(k)=a(2n)=2*a(n) get a(n) from the already built part of the array
        IFTE
      PUT                            // Put a(k) in the array
   NEXT » »

(08-21-2022 01:05 PM)John Keith Wrote:  As far as speed is concerned, accumulating numbers on the stack and storing them in a list or array at the end is significantly faster than using GET and PUT on an existing array. Also stack operations such as PICK and ROLL are very fast, sometimes even faster than list processing commands on later calculators.

I follow your advice and get a faster and shorter code using the exact same algorithm:


A2516:
« → s
   « 1 SF
    1 s FOR k
      IF k 2 MOD
       THEN
         IF 1 FC?C
          THEN 2 k * 4 - 1 SF
          ELSE k 2 + END
       ELSE
         k 2 / PICK 2 * END
    NEXT
    s →LIST » »

The list of the first 544 elements is now obtained in less than 30 seconds: a great improvement.

Thanks