6 kyu

van Eck sequences

34 of 36JohanWiltink

Description:

What's the next term?      Don't know  
How fast does it grow?     Don't know  
Does every number appear?  Don't know

Consider a sequence that is generated as follows:

  1. the starting term(s) is or are given
  2. if a term did not appear previously in the sequence, the next term in the sequence is 0
  3. if a term did appear previously in the sequence, the next term in the sequence is the number of steps back in the sequence that it appeared

Given 0, the sequence starts: 0, 0, 1, 0, 2, 0, 2, 2, 1, 6, ..

  • first term is 0; sequence is now [0]
  • 0 did not appear previously: add 0; sequence is now [0,0]
  • 0 last appeared previously 1 place before current term: add 1; sequence is now [0,0,1]
  • 1 did not appear previously: add 0; sequence is now [0,0,1,0]
  • 0 last appeared previously 2 places before current term: add 2; sequence is now [0,0,1,0,2]
  • 2 did not appear previously: add 0; sequence is now [0,0,1,0,2,0]
  • 0 last appeared previously 2 places before current term: add 2; sequence is now [0,0,1,0,2,0,2]
  • 2 last appeared previously 2 places before current term: add 2; sequence is now [0,0,1,0,2,0,2,2]
  • 2 last appeared previously 1 place before current term: add 2; sequence is now [0,0,1,0,2,0,2,2,1]
  • 1 last appeared previously 6 places before current term: add 6; sequence is now [0,0,1,0,2,0,2,2,1,6]
  • 6 did not appear previously .. and so on, and so on

Task

Implement

class VanEck {}
class VanEck()

initialised with the starting term(s) ( at least 1 )

constructor(...a) { return instance; }
val vanEck0 = VanEck(0)
val vanEck00 = vanEck(0, 0)

exposing the following methods

term(i)     { return n; }        // term at index `i` ( `0`-based )
sequence(i) { return [n,n,..]; } // the complete sequence of terms `0..i` ( exclusive )
first(n)    { return i; }        // the index of the first occurrence of the number `n`
every(n)    { return i; }        // the lowest index where all numbers `0..n` ( inclusive ) have occurred
fast(i)     { return n; }        // the maximum of terms `0..i` ( inclusive )
def term(i: Int): Int = ???                 // term at index `i` ( `0`-based )

def sequence(i: Int): Iterable[Int] = ???   // the complete sequence of terms `0..i` ( exclusive )

def every(n: Int): Int = ???                // the lowest index where all numbers `0..n` ( inclusive ) have occurred

def first(n: Int): Int = ???                // the index of the first occurrence of the number `n`

def fast(i: Int): Int = ???                 // the maximum of terms `0..i` ( inclusive )

Notes

  • All input is valid
  • methods will be tested up to argument 1 000
  • in fixed tests only, term will additionally be tested up to argument 1 000 000

Resources

OEIS
Youtube / Numberphile

Algorithms

Stats:

CreatedJun 18, 2019
PublishedJun 18, 2019
Warriors Trained264
Total Skips22
Total Code Submissions253
Total Times Completed36
JavaScript Completions34
Scala Completions3
Total Stars15
% of votes with a positive feedback rating95% of 19
Total "Very Satisfied" Votes17
Total "Somewhat Satisfied" Votes2
Total "Not Satisfied" Votes0
Total Rank Assessments3
Average Assessed Rank
6 kyu
Highest Assessed Rank
5 kyu
Lowest Assessed Rank
7 kyu
Ad
Contributors
  • JohanWiltink Avatar
  • LegendaryFartMaster Avatar
  • user8436785 Avatar
Ad