Threaded Mode | Linear Mode

Thomas Okken · (This post was last modified: 09-17-2017 03:35 PM by Thomas Okken.)

(09-17-2017 11:55 AM)Gerald H Wrote: Thank you, Thomas, for your suggestion, but I fear any algorithm that uses a complicated recursion is doomed to get bogged down & be inefficient.

Similarly Gilles, a nicely small programme, but the recursions will prohibit use for large numbers.

I don't think any recursive programme will be successful.

I disagree:

Code:

<< -> N

  <<

    IF N 0 <=

    THEN 0

    ELSE

      IF 'M' DUP EVAL SAME

      THEN [ -1 ] 'M' STO

      END

      IF N M SIZE LIST-> DROP DUP ROT <

      THEN N 1 ->LIST M SWAP RDM SWAP 1 + N

        FOR I I -1 PUT

        NEXT 'M' STO

      ELSE DROP

      END M N GET DUP

      IF -1 ==

      THEN DROP

        IF N 5 <=

        THEN N

        ELSE 'A(N-A(N-1))+A(N-1-A(N-2))+A(N-2-A(N-3))+A(N-3-A(N-4))+A(N-4-A(N-5))' EVAL

        END DUP M SWAP N SWAP PUT 'M' STO

      END

    END

  >>

>>

'A' STO

I don't have a real calculator to test this on, but in m48 on my iPhone, set to emulate a 48GX at "authentic speed," this evaluates a(100) in 137 seconds.

It looks like evaluating A(N) always requires evaluating all of A(1) through A(N-1), so the algorithm could also be written as an iteration, which would be equivalent in terms of the calculations it performs, but probably much faster.