Create a pointer sequence

Question

Lets define a pointer sequence to be any sequence such that a(n) = a((n-1)-(a(n-1))) forall n greater than some finite number. For example if our sequence begun with

3 2 1 

Our next term would be 2, because a(n-1) = 1, (n-1)-1 = 1, a(1) = 2 (this example is zero index however it does not matter what index you use the calculation will always be the same.). If we repeat the process we get the infinite sequence

3 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2

Task

Given some initial array of positive integers output the pointer sequence starting with that array.

Output types

Output is intended to be flexible, if you choose to write a function as your program it can return, either an infinite list of integers or a function that indexes the sequence. If you choose to write a full program you may output terms of the sequence indefinitely.

You may also choose to take two inputs, the starting array and an index. If you choose to do this you need only output the term of the sequence at that index.

---

You will never be given a sequence that requires indexing before the beginning of the sequence. For example 3 is not a valid input because you would need terms before the 3 to resolve the next term.

This is code-golf so your score will be the number of bytes in your program with a lower score being better.

Test Cases

test cases are truncated for simplicity

2 1   -> 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 ...
2 3 1 -> 2 3 1 3 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 ...
3 3 1 -> 3 3 1 3 3 3 1 3 3 3 1 3 3 3 1 3 3 3 1 3 3 3 1 3 3 3 1 3 ...
4 3 1 -> 4 3 1 3 4 4 3 3 4 4 4 3 4 4 4 4 3 4 4 4 4 3 4 4 4 4 3 4 ...

Answer 1

JavaScript (ES6), 25 bytes

a=>f=n=>a[n]||f(--n-f(n))

An anonymous function that, when called, creates a function f that gives the item at a given index in the sequence.

Please let me know if I misunderstood anything...

Answer 2

Husk, 7 6 bytes

¡S!o_→

Returns an infinite list. Try it online! Note that it takes a while for TIO to truncate and print the result.

Explanation

The operator ¡ has several meanings. Here I'm using "construct infinite list by iterating a function that computes a new element from the list of existing ones". Given a list of length N, the new element will have 1-based index N+1. All we need to do is negate the last element of the list (which is the previous value) and index into the list using the result.

¡S!o_→  Implicit input.
¡       Construct infinite list by iterating this function on input:
 S!      Element at index
    →    last element
  o_     negated.

Answer 3

Haskell, 36 bytes

Takes a list and returns a function that indexes the sequence

l!n|n<length l=l!!n|e<-n-1=l!(e-l!e)

Try it online!

Explanation

Here we are defining a function ! that takes a list l and a index n. If n is less than the length of l we index l by n, otherwise we return l!((n-1)-l!(n-1)). This follows the recursive definition of the function I gave in the question.

Here is the same program ungolfed.

a l n
 |n<length l = l!!n
 |otherwise = (a l) ((n-1) - (a l) (n-1))

I use e<-n-1 instead of otherwise to save bytes while assigning n-1 to e so it can be used later.

Answer 4

MATL, 13 9 bytes

:"tt0)_)h

Outputs the initial terms followed by n additional terms (allowed by the challenge), where n is a positive integer taken as input.

Try it online!

Explanation

:"      % Implicitly input n. Do the following n times
  tt    %    Duplicate the sequence so far, twice. In the first iteration this
        %    implicitly inputs the array of initial terms
  0)    %    Get value of the last entry, say m
  _)    %    Get value of the entry which is m positions back from the last
  h     %    Append. This extends the array with the new entry
        % Implicit end. Implicitly display

Answer 5

Mathematica, 63 bytes

takes two inputs

(Clear@a;(a@#2[[1]]=#)&~MapIndexed~#;a@n_:=a[n-1-a[n-1]];a@#2)&  

Try it online!

-3 bytes from Martin Ender

Answer 6

R, 55 bytes

f=function(a,n)"if"(n<=sum(a|1),a[n],f(a,n-1-f(a,n-1)))

Try it online!

Takes two inputs.

Answer 7

Standard ML (MLton), 58 bytes

fun a$n=if n<length$then List.nth($,n)else a$(n-1-a$(n-1))

Try it online! The function a takes the initial list and an index and returns the sequence element at that index. Example usage: a [4,3,1] 5 yields 4.

Answer 8

Jelly, 6 bytes

NṪịṭµ¡

Takes a sequence S and an integer k, and adds k terms to S.

Try it online!

How it works

NṪịṭµ¡  Main link. Left argument: S (sequence). Right argument: k (integer)

    µ¡  Combine the links to the left into a (variadic) chain and call it k times.
        The new chain started by µ is monadic, so the chain to the left will be
        called monadically.
N           Negate; multiply all elements in S by -1.
 Ṫ          Tail; retrieve the last element, i.e., -a(n-1).
  ị         At-index; retrieve the element of S at index -a(n-1).
            Since indexing is modular and the last element has indices n-1 and 0,
            this computes a( (n-1) - a(n-1) ).
   ṭ        Tack; append the result to S.

Answer 9

Husk, 6 bytes

¡Ṡ!o_→

Try it online!

Figured this out after a lot of frustration with Jo King's help.

Answer 10

Python 2, 48 bytes

a=lambda S,n:n<len(S)and S[n]or a(S,~a(S,~-n)+n)

Try it online!

Answer 11

CJam, 10 bytes

{{(_j-j}j}

For CJam, this does very well (It even beats 05ab1e!).

This is an anonymous block that expects input in the form i n on the stack, where i is the index in the sequence and n is an array of starting numbers.

The reason this works so well is because of the j operator, which provides memoized recursion from a set of starting values.

Explanation:

{    Function j(n) with [j(0), j(1), j(2)] = [4, 3, 1], return j(6):
 (    Decrement:    5
 _    Duplicate:    5 5
 j    j(5):
  (    Decrement:   5 4
  _    Duplicate:   5 4 4
  j    j(4):
   (    Decrement:  5 4 3
   _    Duplicate:  5 4 3 3
   j    j(3):
    (    Decrement: 5 4 3 2
    _    Duplicate: 5 4 3 2 2
    j    j(2) = 1:  5 4 3 2 1
    -    Subtract:  5 4 3 1
    j    j(1) = 3:  5 4 3 3
   -    Subtract:   5 4 0
   j    j(0) = 4:   5 4 4
  -    Subtract:    5 0
  j    j(0) = 4:    5 4
 -    Subtract:     1
 j    j(1) = 3:     3
}j   End:           3

Answer 12

Java (8), 60 bytes

int a(int[]a,int n){return n<a.length?a[n]:a(a,--n-a(a,n));}

Takes two inputs (integer-array a and integer n), and outputs the n'th value of the sequence.

Explanation:

Try it here. (Might take a few seconds.)

int a(int[]a,int n){        // Method with int[] and int parameters and int return-type
  return n<a.length?        //  If input `n` is smaller than the length of the array:
          a[n]              //   Output the `n`'th item of the array
         :                  //  Else:
          a(a,--n-a(a,n));  //   Recursive call with `n-1-a(n-1)`
}                           // End of method

Answer 13

05AB1E, 5 bytes

λN<α₅

Outputs the infinite sequence.

Try it online. (No test suite with all test cases at once, because there is a bug when using the recursive environment within an iterator.)

Outputting the \$n^{th}\$ value or first \$n\$ values would cost an additional byte:
Output the (0-based) \$a(n)\$.
Output the first \$n\$ values.

Explanation:

λ      # Start a recursive environment
       # to output the infinite sequence
       # Using the (implicit) input-list I, start the sequence at a(0)=I[0], a(1)=I[1],
       # ..., a(n)=I[n],
       # For which we calculate the next a(n) value as follows:
       #  (implicitly push a(n-1))
 N<    #  Push n-1
   α   #  Calculate the absolute difference between the two: |a(n-1)-(n-1)|
    ₅  #  And use that as n'th value: a(|a(n-1)-(n-1)|)

Answer 14

Japt, 8 7 bytes

Outputs the nth term, 0-indexed. Change the second g to h to output the first n terms instead.

ÈgZw}gV

Try it

Answer 15

Wolfram Language (Mathematica), 34 31 30 29 bytes

a_f@n_:=a[--t-a@t]&@@a[[t=n]]

Try it online!

Input f[initial...][n], e.g. as f[2, 1][3].

a_f@n_:=                        f[initial...][n], where a=f[initial...]
                     a[[t=n]]   attempt to take an index
        a[--t-a@t]&@@             if out of bounds, recurse

---

Alternative input formats (also 29 bytes):

f=f[#,--t-#~f~t]&@@#[[t=#2]]&

Try it online!

Input [initial, n], e.g. as f[{2, 1}, 3].

h:f@a_=h[--t-h@t]&@@a[[t=#]]&

Try it online!

Input [initial][n], e.g. as f[{2, 1}][3].

Answer 16

Nibbles, 4 bytes

.~~_=`($

explanation

.~~      # append until null (aka always in this case)
   _     # first input int list
    =    # array subscript (aka haskell !!)
     `(  # uncons (returning head)
       $ # second value from uncons (the tail)

Note that the $ can't also be implicit due to part of the uncons bin representation using part of its encoding after its arg :(

I say this is non competing because this problem influenced the idea to have the .~~ operator, although something like this was definitely needed and its a standard op in Husk.

Answer 17

Perl, 38 +3 (-anl) bytes

{print;push@F,$_=$F[$#F-$F[$#F]];redo}

Try It Online

Answer 18

05AB1E, 20 bytes

#`r[=ˆŽ¼}[¯¾¯¾è-è=ˆ¼

Expects the input as a space-separated string, keeps outputting indefinitely; pretty straightforward implementation

Example run:

$ 05ab1e -e '#`r[=ˆŽ¼}[¯¾¯¾è-è=ˆ¼' <<< '3 2 1'
3
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2
2
1
2

Answer 19

Java (OpenJDK 8), 95 93 91 90 bytes

a->i->{int j=0,b[]=new int[++i];for(;j<i;j++)b[j]=j<a.length?a[j]:b[~-j-b[j-1]];return b;}

Try it online!

Answer 20

Perl 5, -a 30 bytes

#!/usr/bin/perl -a
use 5.10.0
say$F[@F]=$F[-1-$F[-1]]while 1

Try it online!