Van Eck sequence
The sequence is generated by following this pseudo-code:
A: The first term is zero.
Repeatedly apply:
If the last term is *new* to the sequence so far then:
B: The next term is zero.
Otherwise:
C: The next term is how far back this last term occured previousely.
- Example
Using A:
0
Using B:
0 0
Using C:
0 0 1
Using B:
0 0 1 0
Using C: (zero last occured two steps back - before the one)
0 0 1 0 2
Using B:
0 0 1 0 2 0
Using C: (two last occured two steps back - before the zero)
0 0 1 0 2 0 2 2
Using C: (two last occured one step back)
0 0 1 0 2 0 2 2 1
Using C: (one last appeared six steps back)
0 0 1 0 2 0 2 2 1 6
...
- Task
- Create a function/proceedure/method/subroutine/... to generate the Van Eck sequence of numbers.
- Use it to display here, on this page:
- The first ten terms of the sequence.
- Terms 991 - to - 1000 of the sequence.
- References
- Don't Know (the Van Eck Sequence) - Numberphile video.
- Wikipedia Article: Van Eck's Sequence.
- OEIS sequence: A181391.
Clojure
<lang clojure>(defn van-eck
([] (van-eck 0 0 {}))
([val n seen]
(lazy-seq
(cons val
(let [next (- n (get seen val n))]
(van-eck next
(inc n)
(assoc seen val n)))))))
(println "First 10 terms:" (take 10 (van-eck))) (println "Terms 991 to 1000 terms:" (take 10 (drop 990 (van-eck))))</lang>
- Output:
First 10 terms: (0 0 1 0 2 0 2 2 1 6) Terms 991 to 1000 terms: (4 7 30 25 67 225 488 0 10 136)
Go
<lang go>package main
import "fmt"
func main() {
const max = 1000
a := make([]int, max) // all zero by default
for n := 0; n < max-1; n++ {
for m := n - 1; m >= 0; m-- {
if a[m] == a[n] {
a[n+1] = n - m
break
}
}
}
fmt.Println("The first ten terms of the Van Eck sequence are:")
fmt.Println(a[:10])
fmt.Println("\nTerms 991 to 1000 of the sequence are:")
fmt.Println(a[990:])
}</lang>
- Output:
The first ten terms of the Van Eck sequence are: [0 0 1 0 2 0 2 2 1 6] Terms 991 to 1000 of the sequence are: [4 7 30 25 67 225 488 0 10 136]
Alternatively, using a map to store the latest index of terms previously seen (output as before): <lang go>package main
import "fmt"
func main() {
const max = 1000
a := make([]int, max) // all zero by default
seen := make(map[int]int)
for n := 0; n < max-1; n++ {
if m, ok := seen[a[n]]; ok {
a[n+1] = n - m
}
seen[a[n]] = n
}
fmt.Println("The first ten terms of the Van Eck sequence are:")
fmt.Println(a[:10])
fmt.Println("\nTerms 991 to 1000 of the sequence are:")
fmt.Println(a[990:])
}</lang>
Perl 6
Implemented as a lazy, extendable list.
<lang perl6>sub next-van-eck ( $i, $k ) {
state %v;
my $t = %v{$i}.defined ?? $k - %v{$i} !! 0;
%v{$i} = $k;
$t
}
my @Van-Ecks = 0, *.&next-van-eck($++) ... *;
- The task
put "Van-Eck sequence:
First 10 terms: {@Van-Ecks[^10]}
Terms 991 through 1000: {@Van-Ecks[990...999]}";
- And just for the heck of it.
for 1e3, 1e4, 1e5 {
my ($k, $v) = @Van-Ecks.first: * > $_, :kv; printf "%22s: %d at position %d\n", "First term > $_", $v, $k+1;
}</lang>
- Output:
Van-Eck sequence:
First 10 terms: 0 0 1 0 2 0 2 2 1 6
Terms 991 through 1000: 4 7 30 25 67 225 488 0 10 136
First term > 1000: 1024 at position 1150
First term > 10000: 10381 at position 11603
First term > 100000: 100881 at position 104511
Python
<lang python>def van_eck():
n, seen, val = 0, {}, 0
while True:
yield val
last = {val: n}
val = n - seen.get(val, n)
seen.update(last)
n += 1
- %%
if __name__ == '__main__':
print("Van Eck: first 10 terms: ", list(islice(van_eck(), 10)))
print("Van Eck: terms 991 - 1000:", list(islice(van_eck(), 1000))[-10:])</lang>
- Output:
Van Eck: first 10 terms: [0, 0, 1, 0, 2, 0, 2, 2, 1, 6] Van Eck: terms 991 - 1000: [4, 7, 30, 25, 67, 225, 488, 0, 10, 136]
Python: Alternate
The following stores the sequence so far in a list seen rather than the first example that just stores last occurrences in a dict.
<lang python>def van_eck():
n = 0
seen = [0]
val = 0
while True:
yield val
if val in seen[1:]:
val = seen.index(val, 1)
else:
val = 0
seen.insert(0, val)
n += 1</lang>
- Output:
As before.
REXX
This REXX version allows the start and end of two Van Eck sequences (to be displayed). <lang rexx>/*REXX program generates/displays two 'start' to 'end' elements of the Van Eck sequence.*/ parse arg s1 e1 s2 e2 . /*obtain optional arguments from the CL*/ if s1== | s1=="," then s1= 1 /*Not specified? Then use the default.*/ if e1== | e1=="," then e1= 10 /* " " " " " " */ if s2== | s2=="," then s2= 991 /* " " " " " " */ if e2== | e2=="," then e2= 1000 /* " " " " " " */
mx= max(e1, e2); L= length(mx) /*MX: largest end; L: width of MX. */
$= 0 /*the initial (start) value of the seq.*/
do j=1 for mx
$= $ wordpos( reverse( word($, j) ), reverse( subword($, 1, j - 1) ) )
end /*j*/
/*stick a fork in it, we're all done. */
say 'terms' right(s1, L) " through " right(e1, L)': ' subword($, s1, e1-s1+1) say 'terms' right(s2, L) " through " right(e2, L)': ' subword($, s2, e2-s2+1)</lang>
- output when using the default inputs:
terms 1 through 10: 0 0 1 0 2 0 2 2 1 6 terms 991 through 1000: 4 7 30 25 67 225 488 0 10 136
Scala
<lang scala> object VanEck extends App {
def vanEck(n: Int): List[Int] = {
def vanEck(values: List[Int]): List[Int] =
if (values.size < n)
vanEck(math.max(0, values.indexOf(values.head, 1)) :: values)
else
values
vanEck(List(0)).reverse }
val vanEck1000 = vanEck(1000)
println(s"The first 10 terms are ${vanEck1000.take(10)}.")
println(s"Terms 991 to 1000 are ${vanEck1000.drop(990)}.")
} </lang>
- Output:
The first 10 terms are List(0, 0, 1, 0, 2, 0, 2, 2, 1, 6). Terms 991 to 1000 are List(4, 7, 30, 25, 67, 225, 488, 0, 10, 136).