Van Eck sequence: Difference between revisions
Line 122: | Line 122: | ||
showList(vanEck(10)), ¬ |
showList(vanEck(10)), ¬ |
||
"", ¬ |
"", ¬ |
||
"Terms |
"Terms 990 to 1000:", ¬ |
||
showList(items -10 thru -1 of vanEck(1000))}) |
showList(items -10 thru -1 of vanEck(1000))}) |
||
end run |
end run |
Revision as of 12:25, 23 July 2020
You are encouraged to solve this task according to the task description, using any language you may know.
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.
Ada
<lang Ada>with Ada.Text_IO;
procedure Van_Eck_Sequence is
Sequence : array (Natural range 1 .. 1_000) of Natural;
procedure Calculate_Sequence is begin Sequence (Sequence'First) := 0; for Index in Sequence'First .. Sequence'Last - 1 loop Sequence (Index + 1) := 0; for I in reverse Sequence'First .. Index - 1 loop if Sequence (I) = Sequence (Index) then Sequence (Index + 1) := Index - I; exit; end if; end loop; end loop; end Calculate_Sequence;
procedure Show (First, Last : in Positive) is use Ada.Text_IO; begin Put ("Element" & First'Image & " .." & Last'Image & " of Van Eck sequence: "); for I in First .. Last loop Put (Sequence (I)'Image); end loop; New_Line; end Show;
begin
Calculate_Sequence; Show (First => 1, Last => 10); Show (First => 991, Last => 1_000);
end Van_Eck_Sequence;</lang>
- Output:
Element 1 .. 10 of Van Eck sequence: 0 0 1 0 2 0 2 2 1 6 Element 991 .. 1000 of Van Eck sequence: 4 7 30 25 67 225 488 0 10 136
AppleScript
AppleScript is not the tool for the job, but here is a quick assembly from ready-made parts: <lang applescript>use AppleScript version "2.4" use scripting additions
-- vanEck :: Int -> [Int]
on vanEck(n)
-- First n terms of the vanEck sequence. script go on |λ|(xns, i) set {x, ns} to xns set prev to item (1 + x) of ns if 0 ≠ prev then set v to i - prev else set v to 0 end if {{v, insert(ns, x, i)}, v} end |λ| end script {0} & item 2 of mapAccumL(go, ¬ {0, replicate(n, 0)}, enumFromTo(1, n - 1))
end vanEck
TEST ---------------------------
on run
unlines({¬ "First 10 terms:", ¬ showList(vanEck(10)), ¬ "", ¬ "Terms 990 to 1000:", ¬ showList(items -10 thru -1 of vanEck(1000))})
end run
GENERIC --------------------------
-- enumFromTo :: Int -> Int -> [Int] on enumFromTo(m, n)
if m ≤ n then set lst to {} repeat with i from m to n set end of lst to i end repeat lst else {} end if
end enumFromTo
-- foldl :: (a -> b -> a) -> a -> [b] -> a
on foldl(f, startValue, xs)
tell mReturn(f) set v to startValue set lng to length of xs repeat with i from 1 to lng set v to |λ|(v, item i of xs, i, xs) end repeat return v end tell
end foldl
-- insert :: [Int] -> Int -> Int -> [Int]
on insert(xs, i, v)
-- A list updated at position i with value v. set item (1 + i) of xs to v xs
end insert
-- intercalate :: String -> [String] -> String
on intercalate(delim, xs)
set {dlm, my text item delimiters} to ¬ {my text item delimiters, delim} set s to xs as text set my text item delimiters to dlm s
end intercalate
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
-- The list obtained by applying f -- to each element of xs. tell mReturn(f) set lng to length of xs set lst to {} repeat with i from 1 to lng set end of lst to |λ|(item i of xs, i, xs) end repeat return lst end tell
end map
-- mReturn :: First-class m => (a -> b) -> m (a -> b)
on mReturn(f)
-- 2nd class handler function lifted into 1st class script wrapper. if script is class of f then f else script property |λ| : f end script end if
end mReturn
-- 'The mapAccumL function behaves like a combination of map and foldl;
-- it applies a function to each element of a list, passing an
-- accumulating parameter from |Left| to |Right|, and returning a final
-- value of this accumulator together with the new list.' (see Hoogle)
-- mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])
on mapAccumL(f, acc, xs)
script on |λ|(a, x, i) tell mReturn(f) to set pair to |λ|(item 1 of a, x, i) {item 1 of pair, (item 2 of a) & {item 2 of pair}} end |λ| end script foldl(result, {acc, []}, xs)
end mapAccumL
-- Egyptian multiplication - progressively doubling a list, appending
-- stages of doubling to an accumulator where needed for binary
-- assembly of a target length
-- replicate :: Int -> a -> [a]
on replicate(n, a)
set out to {} if 1 > n then return out set dbl to {a} repeat while (1 < n) if 0 < (n mod 2) then set out to out & dbl set n to (n div 2) set dbl to (dbl & dbl) end repeat return out & dbl
end replicate
-- showList :: [a] -> String
on showList(xs)
"[" & intercalate(", ", map(my str, xs)) & "]"
end showList
-- str :: a -> String
on str(x)
x as string
end str
-- unlines :: [String] -> String
on unlines(xs)
-- A single string formed by the intercalation -- of a list of strings with the newline character. set {dlm, my text item delimiters} to ¬ {my text item delimiters, linefeed} set s to xs as text set my text item delimiters to dlm s
end unlines</lang>
- Output:
First 10 terms: [0, 0, 1, 0, 2, 0, 2, 2, 1, 6] Terms 999 to 1000: [4, 7, 30, 25, 67, 225, 488, 0, 10, 136]
AWK
<lang AWK>
- syntax: GAWK -f VAN_ECK_SEQUENCE.AWK
- converted from Go
BEGIN {
limit = 1000 for (i=0; i<limit; i++) { arr[i] = 0 } for (n=0; n<limit-1; n++) { for (m=n-1; m>=0; m--) { if (arr[m] == arr[n]) { arr[n+1] = n - m break } } } printf("terms 1-10:") for (i=0; i<10; i++) { printf(" %d",arr[i]) } printf("\n") printf("terms 991-1000:") for (i=990; i<1000; i++) { printf(" %d",arr[i]) } printf("\n") exit(0)
} </lang>
- Output:
terms 1-10: 0 0 1 0 2 0 2 2 1 6 terms 991-1000: 4 7 30 25 67 225 488 0 10 136
C
<lang c>#include <stdlib.h>
- include <stdio.h>
int main(int argc, const char *argv[]) {
const int max = 1000; int *a = malloc(max * sizeof(int)); for (int n = 0; n < max - 1; n ++) { for (int m = n - 1; m >= 0; m --) { if (a[m] == a[n]) { a[n+1] = n - m; break; } } }
printf("The first ten terms of the Van Eck sequence are:\n"); for (int i = 0; i < 10; i ++) printf("%d ", a[i]); printf("\n\nTerms 991 to 1000 of the sequence are:\n"); for (int i = 990; i < 1000; i ++) printf("%d ", a[i]); putchar('\n');
return 0;
}</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
C++
<lang cpp>#include <iostream>
- include <map>
class van_eck_generator { public:
int next() { int result = last_term; auto iter = last_pos.find(last_term); int next_term = (iter != last_pos.end()) ? index - iter->second : 0; last_pos[last_term] = index; last_term = next_term; ++index; return result; }
private:
int index = 0; int last_term = 0; std::map<int, int> last_pos;
};
int main() {
van_eck_generator gen; int i = 0; std::cout << "First 10 terms of the Van Eck sequence:\n"; for (; i < 10; ++i) std::cout << gen.next() << ' '; for (; i < 990; ++i) gen.next(); std::cout << "\nTerms 991 to 1000 of the sequence:\n"; for (; i < 1000; ++i) std::cout << gen.next() << ' '; std::cout << '\n'; return 0;
}</lang>
- Output:
First 10 terms of the Van Eck sequence: 0 0 1 0 2 0 2 2 1 6 Terms 991 to 1000 of the sequence: 4 7 30 25 67 225 488 0 10 136
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)
Common Lisp
<lang Lisp>
- Tested using CLISP
(defun VanEck (x) (reverse (VanEckh x 0 0 '(0))))
(defun VanEckh (final index curr lst) (if (eq index final) lst (VanEckh final (+ index 1) (howfar curr lst) (cons curr lst))))
(defun howfar (x lst) (howfarh x lst 0))
(defun howfarh (x lst runningtotal) (cond ((null lst) 0) ((eq x (car lst)) (+ runningtotal 1)) (t (howfarh x (cdr lst) (+ runningtotal 1)))))
(format t "The first 10 elements are ~a~%" (VanEck 9)) (format t "The 990-1000th elements are ~a~%" (nthcdr 990 (VanEck 999))) </lang>
- Output:
The first 10 elements are (0 0 1 0 2 0 2 2 1 6) The 990-1000th elements are (4 7 30 25 67 225 488 0 10 136)
D
<lang d>import std.stdio;
void vanEck(int firstIndex, int lastIndex) {
int[int] vanEckMap; int last = 0; if (firstIndex == 1) { writefln("VanEck[%d] = %d", 1, 0); } for (int n = 2; n <= lastIndex; n++) { int vanEck = last in vanEckMap ? n - vanEckMap[last] : 0; vanEckMap[last] = n; last = vanEck; if (n >= firstIndex) { writefln("VanEck[%d] = %d", n, vanEck); } }
}
void main() {
writeln("First 10 terms of Van Eck's sequence:"); vanEck(1, 10); writeln; writeln("Terms 991 to 1000 of Van Eck's sequence:"); vanEck(991, 1000);
}</lang>
- Output:
First 10 terms of Van Eck's sequence: VanEck[1] = 0 VanEck[2] = 0 VanEck[3] = 1 VanEck[4] = 0 VanEck[5] = 2 VanEck[6] = 0 VanEck[7] = 2 VanEck[8] = 2 VanEck[9] = 1 VanEck[10] = 6 Terms 991 to 1000 of Van Eck's sequence: VanEck[991] = 4 VanEck[992] = 7 VanEck[993] = 30 VanEck[994] = 25 VanEck[995] = 67 VanEck[996] = 225 VanEck[997] = 488 VanEck[998] = 0 VanEck[999] = 10 VanEck[1000] = 136
Dyalect
<lang dyalect>const max = 1000 var a = Array.empty(max, 0) for n in 0..(max-2) {
var m = n - 1 while m >= 0 { if a[m] == a[n] { a[n+1] = n - m break } m -= 1 }
} print("The first ten terms of the Van Eck sequence are: \(a[0..10])") print("Terms 991 to 1000 of the sequence are: \(a[991..1000])")</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: {7, 30, 25, 67, 225, 488, 0, 10, 136}
F#
The function
<lang fsharp> // Generate Van Eck's Sequence. Nigel Galloway: June 19th., 2019 let ecK()=let n=System.Collections.Generic.Dictionary<int,int>()
Seq.unfold(fun (g,e)->Some(g,((if n.ContainsKey g then let i=n.[g] in n.[g]<-e;e-i else n.[g]<-e;0),e+1)))(0,0)
</lang>
The Task
- First 50
<lang fsharp> ecK() |> Seq.take 50 |> Seq.iter(printf "%d "); printfn "";; </lang>
- Output:
0 0 1 0 2 0 2 2 1 6 0 5 0 2 6 5 4 0 5 3 0 3 2 9 0 4 9 3 6 14 0 6 3 5 15 0 5 3 5 2 17 0 6 11 0 3 8 0 3 3
- 50 from 991
<lang fsharp> ecK() |> Seq.skip 990 |> Seq.take 50|> Seq.iter(printf "%d "); printfn "";; </lang>
- Output:
4 7 30 25 67 225 488 0 10 136 61 0 4 12 72 0 4 4 1 24 41 385 0 7 22 25 22 2 84 68 282 464 0 10 25 9 151 697 0 6 41 20 257 539 0 6 6 1 29 465
- I thought the longest sequence of non zeroes in the first 100 million items might be interesting
It occurs between 32381749 and 32381774:
9 47 47 1 10 33 27 548 548 1 6 33 6 2 154 15657 695734 270964 235721 238076 4896139 655158 7901804 146089 977945 21475977
Alternative recursive procedure
<lang fsharp> open System.Collections.Generic let VanEck() =
let rec _vanEck (num:int) (pos:int) (lastOccurence:Dictionary<int, int>) = match lastOccurence.TryGetValue num with | (true, position) -> set num pos (pos - position) lastOccurence | _ -> set num pos 0 lastOccurence and set num pos next lastOccurenceByNumber = seq { lastOccurenceByNumber.[num] <- pos yield next yield! _vanEck next (pos + 1) lastOccurenceByNumber }
seq { yield 0 yield! _vanEck 0 1 (new Dictionary<int, int>()) }
VanEck() |> Seq.take 10 |> Seq.map (sprintf "%i") |> String.concat " " |> printfn "The first ten terms of the sequence : %s" VanEck() |> Seq.skip 990 |> Seq.take 10 |> Seq.map (sprintf "%i") |> String.concat " " |> printfn "Terms 991 - to - 1000 of the sequence : %s" </lang>
Factor
<lang factor>USING: assocs fry kernel make math namespaces prettyprint sequences ;
- van-eck ( n -- seq )
[ 0 , 1 - H{ } clone '[ building get [ length 1 - ] [ last ] bi _ 3dup 2dup key? [ at - ] [ 3drop 0 ] if , set-at ] times ] { } make ;
1000 van-eck 10 [ head ] [ tail* ] 2bi [ . ] bi@</lang>
- Output:
{ 0 0 1 0 2 0 2 2 1 6 } { 4 7 30 25 67 225 488 0 10 136 }
FreeBASIC
<lang freebasic> Const limite = 1000
Dim As Integer a(limite), n, m, i
For n = 0 To limite-1
For m = n-1 To 0 Step -1 If a(m) = a(n) Then a(n+1) = n-m: Exit For Next m
Next n
Print "Secuencia de Van Eck:" &Chr(10) Print "Primeros 10 terminos: "; For i = 0 To 9
Print a(i) &" ";
Next i Print Chr(10) & "Terminos 991 al 1000: "; For i = 990 To 999
Print a(i) &" ";
Next i End </lang>
- Output:
Secuencia de Van Eck: Primeros 10 terminos: 0 0 1 0 2 0 2 2 1 6 Terminos 991 al 1000: 4 7 30 25 67 225 488 0 10 136
Fōrmulæ
In this page you can see the solution of this task.
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text (more info). Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for transportation effects more than visualization and edition.
The option to show Fōrmulæ programs and their results is showing images. Unfortunately images cannot be uploaded in Rosetta Code.
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>
Haskell
<lang haskell>import Data.List (elemIndex) import Data.Maybe (maybe)
vanEck :: Int -> [Int] vanEck n = reverse $ iterate go [] !! n
where go [] = [0] go xxs@(x:xs) = maybe 0 succ (elemIndex x xs) : xxs
main :: IO () main = do
print $ vanEck 10 print $ drop 990 (vanEck 1000)</lang>
- Output:
[0,0,1,0,2,0,2,2,1,6] [4,7,30,25,67,225,488,0,10,136]
And if we wanted to look a little further than the 1000th term, we could accumulate a Map of most recently seen positions to improve performance:
<lang haskell>{-# LANGUAGE TupleSections #-}
import qualified Data.Map.Strict as M hiding (drop) import Data.List (mapAccumL) import Data.Maybe (maybe)
vanEck :: [Int] vanEck = 0 : snd (mapAccumL go (0, M.empty) [1 ..])
where go (x, dct) i = ((,) =<< (, M.insert x i dct)) (maybe 0 (i -) (M.lookup x dct))
main :: IO () main =
mapM_ print $ (drop . subtract 10 <*> flip take vanEck) <$> [10, 1000, 10000, 100000, 1000000]</lang>
- Output:
[0,0,1,0,2,0,2,2,1,6] [4,7,30,25,67,225,488,0,10,136] [7,43,190,396,2576,3142,0,7,7,1] [92,893,1125,47187,0,7,34,113,140,2984] [8,86,172,8878,172447,0,6,30,874,34143]
J
The tacit verb (function)
<lang j>VanEck=. (, (<:@:# - }: i: {:))^:(]`0:)</lang>
The output
<lang j> VanEck 9 0 0 1 0 2 0 2 2 1 6
990 }. VanEck 999
4 7 30 25 67 225 488 0 10 136</lang>
A structured derivation of the verb (function)
<lang j> next =. <:@:# - }: i: {: NB. Next term of the sequence VanEck=. (, next)^:(]`0:) f. NB. Appending terms and fixing the verb</lang>
Java
Use map to remember last seen index. Computes each value of the sequence in O(1) time. <lang java> import java.util.HashMap; import java.util.Map;
public class VanEckSequence {
public static void main(String[] args) { System.out.println("First 10 terms of Van Eck's sequence:"); vanEck(1, 10); System.out.println(""); System.out.println("Terms 991 to 1000 of Van Eck's sequence:"); vanEck(991, 1000); } private static void vanEck(int firstIndex, int lastIndex) { Map<Integer,Integer> vanEckMap = new HashMap<>(); int last = 0; if ( firstIndex == 1 ) { System.out.printf("VanEck[%d] = %d%n", 1, 0); } for ( int n = 2 ; n <= lastIndex ; n++ ) { int vanEck = vanEckMap.containsKey(last) ? n - vanEckMap.get(last) : 0; vanEckMap.put(last, n); last = vanEck; if ( n >= firstIndex ) { System.out.printf("VanEck[%d] = %d%n", n, vanEck); } } }
} </lang>
- Output:
First 10 terms of Van Eck's sequence: VanEck[1] = 0 VanEck[2] = 0 VanEck[3] = 1 VanEck[4] = 0 VanEck[5] = 2 VanEck[6] = 0 VanEck[7] = 2 VanEck[8] = 2 VanEck[9] = 1 VanEck[10] = 6 Terms 991 to 1000 of Van Eck's sequence: VanEck[991] = 4 VanEck[992] = 7 VanEck[993] = 30 VanEck[994] = 25 VanEck[995] = 67 VanEck[996] = 225 VanEck[997] = 488 VanEck[998] = 0 VanEck[999] = 10 VanEck[1000] = 136
JavaScript
Either declaratively, without premature optimization:
<lang JavaScript>(() => {
'use strict';
// vanEck :: Int -> [Int] const vanEck = n => reverse( churchNumeral(n)( xs => 0 < xs.length ? cons( maybe( 0, succ, elemIndex(xs[0], xs.slice(1)) ), xs ) : [0] )([]) );
// TEST ----------------------------------------------- const main = () => { console.log('VanEck series:\n') showLog('First 10 terms', vanEck(10)) showLog('Terms 991-1000', vanEck(1000).slice(990)) };
// GENERIC FUNCTIONS ----------------------------------
// Just :: a -> Maybe a const Just = x => ({ type: 'Maybe', Nothing: false, Just: x });
// Nothing :: Maybe a const Nothing = () => ({ type: 'Maybe', Nothing: true, });
// churchNumeral :: Int -> (a -> a) -> a -> a const churchNumeral = n => f => x => Array.from({ length: n }, () => f) .reduce((a, g) => g(a), x)
// cons :: a -> [a] -> [a] const cons = (x, xs) => [x].concat(xs)
// elemIndex :: Eq a => a -> [a] -> Maybe Int const elemIndex = (x, xs) => { const i = xs.indexOf(x); return -1 === i ? ( Nothing() ) : Just(i); };
// maybe :: b -> (a -> b) -> Maybe a -> b const maybe = (v, f, m) => m.Nothing ? v : f(m.Just);
// reverse :: [a] -> [a] const reverse = xs => 'string' !== typeof xs ? ( xs.slice(0).reverse() ) : xs.split().reverse().join();
// showLog :: a -> IO () const showLog = (...args) => console.log( args .map(JSON.stringify) .join(' -> ') );
// succ :: Int -> Int const succ = x => 1 + x;
// MAIN --- return main();
})();</lang>
- Output:
VanEck series: "First 10 terms" -> [0,0,1,0,2,0,2,2,1,6] "Terms 991-1000" -> [4,7,30,25,67,225,488,0,10,136]
or as a map-accumulation, building a look-up table:
<lang javascript>(() => {
'use strict';
// vanEck :: Int -> [Int] const vanEck = n => // First n terms of the vanEck series. [0].concat(mapAccumL( ([x, seen], i) => { const prev = seen[x], v = 0 !== prev ? ( i - prev ) : 0; return [ [v, (seen[x] = i, seen)], v ]; }, [0, replicate(n - 1, 0)],
enumFromTo(1, n - 1) )[1]);
// TEST ----------------------------------------------- const main = () => console.log(fTable( 'Terms of the VanEck series:\n', n => str(n - 10) + '-' + str(n), xs => JSON.stringify(xs.slice(-10)), vanEck, [10, 1000, 10000] ))
// GENERIC FUNCTIONS ----------------------------------
// enumFromTo :: Int -> Int -> [Int] const enumFromTo = (m, n) => Array.from({ length: 1 + n - m }, (_, i) => m + i);
// fTable :: String -> (a -> String) -> (b -> String) -> // (a -> b) -> [a] -> String const fTable = (s, xShow, fxShow, f, xs) => { // Heading -> x display function -> // fx display function -> // f -> values -> tabular string const ys = xs.map(xShow), w = Math.max(...ys.map(x => x.length)); return s + '\n' + zipWith( (a, b) => a.padStart(w, ' ') + ' -> ' + b, ys, xs.map(x => fxShow(f(x))) ).join('\n'); };
// Map-accumulation is a combination of map and a catamorphism; // it applies a function to each element of a list, passing an accumulating // parameter from left to right, and returning a final value of this // accumulator together with the new list.
// mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y]) const mapAccumL = (f, acc, xs) => xs.reduce((a, x, i) => { const pair = f(a[0], x, i); return [pair[0], a[1].concat(pair[1])]; }, [acc, []]);
// replicate :: Int -> a -> [a] const replicate = (n, x) => Array.from({ length: n }, () => x);
// str :: a -> String const str = x => x.toString();
// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] const zipWith = (f, xs, ys) => { const lng = Math.min(xs.length, ys.length), as = xs.slice(0, lng), bs = ys.slice(0, lng); return Array.from({ length: lng }, (_, i) => f(as[i], bs[i], i)); };
// MAIN --- return main();
})();</lang>
- Output:
Terms of the VanEck series: 0-10 -> [0,0,1,0,2,0,2,2,1,6] 990-1000 -> [4,7,30,25,67,225,488,0,10,136] 9990-10000 -> [7,43,190,396,2576,3142,0,7,7,1]
Julia
<lang julia>function vanecksequence(N, startval=0)
ret = zeros(Int, N) ret[1] = startval for i in 1:N-1 lastseen = findlast(x -> x == ret[i], ret[1:i-1]) if lastseen != nothing ret[i + 1] = i - lastseen end end ret
end
println(vanecksequence(10)) println(vanecksequence(1000)[991:1000])
</lang>
- Output:
[0, 0, 1, 0, 2, 0, 2, 2, 1, 6] [4, 7, 30, 25, 67, 225, 488, 0, 10, 136]
Alternate version, with a Dict for memoization (output is the same): <lang julia>function vanecksequence(N, startval=0)
ret = zeros(Int, N) ret[1] = startval lastseen = Dict{Int, Int}() for i in 1:N-1 if haskey(lastseen, ret[i]) ret[i + 1] = i - lastseen[ret[i]] end lastseen[ret[i]] = i end ret
end </lang>
Kotlin
<lang scala>fun main() {
println("First 10 terms of Van Eck's sequence:") vanEck(1, 10) println("") println("Terms 991 to 1000 of Van Eck's sequence:") vanEck(991, 1000)
}
private fun vanEck(firstIndex: Int, lastIndex: Int) {
val vanEckMap = mutableMapOf<Int, Int>() var last = 0 if (firstIndex == 1) { println("VanEck[1] = 0") } for (n in 2..lastIndex) { val vanEck = if (vanEckMap.containsKey(last)) n - vanEckMap[last]!! else 0 vanEckMap[last] = n last = vanEck if (n >= firstIndex) { println("VanEck[$n] = $vanEck") } }
}</lang>
- Output:
First 10 terms of Van Eck's sequence: VanEck[1] = 0 VanEck[2] = 0 VanEck[3] = 1 VanEck[4] = 0 VanEck[5] = 2 VanEck[6] = 0 VanEck[7] = 2 VanEck[8] = 2 VanEck[9] = 1 VanEck[10] = 6 Terms 991 to 1000 of Van Eck's sequence: VanEck[991] = 4 VanEck[992] = 7 VanEck[993] = 30 VanEck[994] = 25 VanEck[995] = 67 VanEck[996] = 225 VanEck[997] = 488 VanEck[998] = 0 VanEck[999] = 10 VanEck[1000] = 136
Lua
<lang Lua>-- Return a table of the first n values of the Van Eck sequence function vanEck (n)
local seq, foundAt = {0} while #seq < n do foundAt = nil for pos = #seq - 1, 1, -1 do if seq[pos] == seq[#seq] then foundAt = pos break end end if foundAt then table.insert(seq, #seq - foundAt) else table.insert(seq, 0) end end return seq
end
-- Show the set of values in table t from key numbers lo to hi function showValues (t, lo, hi)
for i = lo, hi do io.write(t[i] .. " ") end print()
end
-- Main procedure local sequence = vanEck(1000) showValues(sequence, 1, 10) showValues(sequence, 991, 1000)</lang>
- Output:
0 0 1 0 2 0 2 2 1 6 4 7 30 25 67 225 488 0 10 136
Nim
<lang nim>const max = 1000 var a: array[max, int] for n in countup(0, max - 2):
for m in countdown(n - 1, 0): if a[m] == a[n]: a[n + 1] = n - m break
echo "The first ten terms of the Van Eck sequence are:" echo $a[..9] echo "\nTerms 991 to 1000 of the sequence are:" echo $a[990..^1]</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]
Pascal
I memorize the last position of each number that occured and use a circular buffer to remember last values. Running once through the list of last positions maybe faster Try it online! takes only 1.4 s for 32,381,775 <lang pascal>program VanEck; {
- 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.} uses
sysutils;
const
MAXNUM = 32381775;//1000*1000*1000; MAXSEENIDX = (1 shl 7)-1;
var
PosBefore : array of UInt32; LastSeen : array[0..MAXSEENIDX]of UInt32;// circular buffer SeenIdx,HaveSeen : Uint32;
procedure OutSeen(Cnt:NativeInt); var
I,S_Idx : NativeInt;
Begin
IF Cnt > MAXSEENIDX then Cnt := MAXSEENIDX; If Cnt > HaveSeen then Cnt := HaveSeen; S_Idx := SeenIdx; S_Idx := (S_Idx-Cnt); IF S_Idx < 0 then inc(S_Idx,MAXSEENIDX); For i := 1 to Cnt do Begin write(' ',LastSeen[S_Idx]); S_Idx:= (S_Idx+1) AND MAXSEENIDX; end; writeln;
end;
procedure Test(MaxTestCnt:Uint32); var
i,actnum,Posi,S_Idx: Uint32; pPosBef,pSeen :pUint32;
Begin
Fillchar(LastSeen,SizeOf(LastSeen),#0); HaveSeen := 0; IF MaxTestCnt> MAXNUM then EXIT; //setlength and clear setlength(PosBefore,0); setlength(PosBefore,MaxTestCnt);
pPosBef := @PosBefore[0]; pSeen := @LastSeen[0]; S_Idx := 0; i := 1; actnum := 0; repeat // save value pSeen[S_Idx] := actnum; S_Idx:= (S_Idx+1) AND MAXSEENIDX; //examine new value often out of cache Posi := pPosBef[actnum]; pPosBef[actnum] := i;
// if Posi=0 ? actnum = 0:actnum = i-Posi
IF Posi = 0 then actnum := 0 else actnum := i-Posi; inc(i); until i > MaxTestCnt; HaveSeen := i-1; SeenIdx := S_Idx;
end;
Begin
Test(10) ; OutSeen(10000); Test(1000); OutSeen(10); Test(MAXNUM); OutSeen(28); setlength(PosBefore,0);
end.</lang>
- Output:
0 0 1 0 2 0 2 2 1 6 4 7 30 25 67 225 488 0 10 136 0 9 47 47 1 10 33 27 548 548 1 6 33 6 2 154 15657 695734 270964 235721 238076 4896139 655158 7901804 146089 977945 21475977 0
Perl
<lang perl>use strict; use warnings; use feature 'say';
sub van_eck {
my($init,$max) = @_; my(%v,$k); my @V = my $i = $init; for (1..$max) { $k++; my $t = $v{$i} ? $k - $v{$i} : 0; $v{$i} = $k; push @V, $i = $t; } @V;
}
for (
['A181391', 0], ['A171911', 1], ['A171912', 2], ['A171913', 3], ['A171914', 4], ['A171915', 5], ['A171916', 6], ['A171917', 7], ['A171918', 8],
) {
my($seq, $start) = @$_; my @seq = van_eck($start,1000); say <<~"END"; Van Eck sequence OEIS:$seq; with the first term: $start First 10 terms: @{[@seq[0 .. 9]]} Terms 991 through 1000: @{[@seq[990..999]]} END
}</lang>
- Output:
Van Eck sequence OEIS:A181391; with the first term: 0 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 Van Eck sequence OEIS:A171911; with the first term: 1 First 10 terms: 1 0 0 1 3 0 3 2 0 3 Terms 991 through 1000: 0 6 53 114 302 0 5 9 22 71 Van Eck sequence OEIS:A171912; with the first term: 2 First 10 terms: 2 0 0 1 0 2 5 0 3 0 Terms 991 through 1000: 8 92 186 0 5 19 41 413 0 5 Van Eck sequence OEIS:A171913; with the first term: 3 First 10 terms: 3 0 0 1 0 2 0 2 2 1 Terms 991 through 1000: 5 5 1 17 192 0 6 34 38 179 Van Eck sequence OEIS:A171914; with the first term: 4 First 10 terms: 4 0 0 1 0 2 0 2 2 1 Terms 991 through 1000: 33 410 0 6 149 0 3 267 0 3 Van Eck sequence OEIS:A171915; with the first term: 5 First 10 terms: 5 0 0 1 0 2 0 2 2 1 Terms 991 through 1000: 60 459 0 7 13 243 0 4 10 211 Van Eck sequence OEIS:A171916; with the first term: 6 First 10 terms: 6 0 0 1 0 2 0 2 2 1 Terms 991 through 1000: 6 19 11 59 292 0 6 6 1 12 Van Eck sequence OEIS:A171917; with the first term: 7 First 10 terms: 7 0 0 1 0 2 0 2 2 1 Terms 991 through 1000: 11 7 2 7 2 2 1 34 24 238 Van Eck sequence OEIS:A171918; with the first term: 8 First 10 terms: 8 0 0 1 0 2 0 2 2 1 Terms 991 through 1000: 16 183 0 6 21 10 249 0 5 48
Phix
Just like the pascal entry, instead of searching/dictionaries use a fast direct/parallel lookup table,
and likewise this can easily create a 32-million-long table in under 2s.
While dictionaries are pretty fast, there is a huge overhead adding/updating millions of entries compared to a flat list of int.
<lang Phix>constant lim = 1000
sequence van_eck = repeat(0,lim),
pos_before = repeat(0,lim)
for n=1 to lim-1 do
integer vn = van_eck[n]+1, prev = pos_before[vn] if prev!=0 then van_eck[n+1] = n - prev end if pos_before[vn] = n
end for printf(1,"The first ten terms of the Van Eck sequence are:%v\n",{van_eck[1..10]}) printf(1,"Terms 991 to 1000 of the sequence are:%v\n",{van_eck[991..1000]})</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}
Prolog
<lang prolog>van_eck_init(v(0, 0, _assoc)):-
empty_assoc(_assoc).
van_eck_next(v(Index, Last_term, Last_pos), v(Index1, Next_term, Last_pos1)):-
(get_assoc(Last_term, Last_pos, V) -> Next_term is Index - V ; Next_term = 0 ), Index1 is Index + 1, put_assoc(Last_term, Last_pos, Index, Last_pos1).
van_eck_sequence(N, Seq):-
van_eck_init(V), van_eck_sequence(N, V, Seq).
van_eck_sequence(0, _, []):-!. van_eck_sequence(N, V, [Term|Rest]):-
V = v(_, Term, _), van_eck_next(V, V1), N1 is N - 1, van_eck_sequence(N1, V1, Rest).
write_list(From, To, _, _):-
To < From, !.
write_list(_, _, _, []):-!. write_list(From, To, N, [_|Rest]):-
From > N, !, N1 is N + 1, write_list(From, To, N1, Rest).
write_list(From, To, N, [E|Rest]):-
writef('%t ', [E]), F1 is From + 1, N1 is N + 1, write_list(F1, To, N1, Rest).
write_list(From, To, List):-
write_list(From, To, 1, List), nl.
main:-
van_eck_sequence(1000, Seq), writeln('First 10 terms of the Van Eck sequence:'), write_list(1, 10, Seq), writeln('Terms 991 to 1000 of the Van Eck sequence:'), write_list(991, 1000, Seq).</lang>
- Output:
First 10 terms of the Van Eck sequence: 0 0 1 0 2 0 2 2 1 6 Terms 991 to 1000 of the Van Eck sequence: 4 7 30 25 67 225 488 0 10 136
Python
Python: Using a dict
<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: List based
The following alternative 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.
Python: Composition of pure functions
As an alternative to the use of generators, a declarative definition in terms of a Church numeral function:
<lang python>Van Eck sequence
from functools import reduce from itertools import repeat
- vanEck :: Int -> [Int]
def vanEck(n):
First n terms of the van Eck sequence.
return churchNumeral(n)( lambda xs: cons( maybe(0)(succ)( elemIndex(xs[0])(xs[1:]) ) )(xs) if xs else [0] )([])[::-1]
- TEST ----------------------------------------------------
def main():
Terms of the Van Eck sequence print( main.__doc__ + ':\n\n' + 'First 10: '.rjust(18, ' ') + repr(vanEck(10)) + '\n' + '991 - 1000: '.rjust(18, ' ') + repr(vanEck(1000)[990:]) )
- GENERIC -------------------------------------------------
- Just :: a -> Maybe a
def Just(x):
Constructor for an inhabited Maybe (option type) value. Wrapper containing the result of a computation. return {'type': 'Maybe', 'Nothing': False, 'Just': x}
- Nothing :: Maybe a
def Nothing():
Constructor for an empty Maybe (option type) value. Empty wrapper returned where a computation is not possible. return {'type': 'Maybe', 'Nothing': True}
- churchNumeral :: Int -> (a -> a) -> a -> a
def churchNumeral(n):
n applications of a function return lambda f: lambda x: reduce( lambda a, g: g(a), repeat(f, n), x )
- cons :: a -> [a] -> [a]
def cons(x):
Construction of a list from a head and a tail. return lambda xs: [x] + xs
- elemIndex :: Eq a => a -> [a] -> Maybe Int
def elemIndex(x):
Just the index of the first element in xs which is equal to x, or Nothing if there is no such element. def go(xs): try: return Just(xs.index(x)) except ValueError: return Nothing() return go
- maybe :: b -> (a -> b) -> Maybe a -> b
def maybe(v):
Either the default value v, if m is Nothing, or the application of f to x, where m is Just(x). return lambda f: lambda m: v if None is m or m.get('Nothing') else ( f(m.get('Just')) )
- succ :: Enum a => a -> a
def succ(x):
The successor of a value. For numeric types, (1 +). return 1 + x
- MAIN ---
if __name__ == '__main__':
main()</lang>
- Output:
Terms of the Van Eck sequence: First 10: [0, 0, 1, 0, 2, 0, 2, 2, 1, 6] 991 - 1000: [4, 7, 30, 25, 67, 225, 488, 0, 10, 136]
Or if we lose sight, for a moment, of the good advice of Donald Knuth, and fall into optimising more than is needed for the first 1000 terms, then we can define the vanEck series as a map accumulation over a range, with an array of positions as the accumulator.
<lang python>Van Eck series by map-accumulation
from functools import reduce from itertools import repeat
- vanEck :: Int -> [Int]
def vanEck(n):
First n terms of the vanEck sequence. def go(xns, i): x, ns = xns
prev = ns[x] v = i - prev if 0 is not prev else 0 return ( (v, insert(ns, x, i)), v )
return [0] + mapAccumL(go)((0, list(repeat(0, n))))( range(1, n) )[1]
- -------------------------- TEST --------------------------
- main :: IO ()
def main():
The last 10 of the first N vanEck terms print( fTable(main.__doc__ + ':\n')( lambda m: 'N=' + str(m), repr, lambda n: vanEck(n)[-10:], [10, 1000, 10000] ) )
- ----------------------- FORMATTING -----------------------
- fTable :: String -> (a -> String) ->
- (b -> String) -> (a -> b) -> [a] -> String
def fTable(s):
Heading -> x display function -> fx display function -> f -> xs -> tabular string. def go(xShow, fxShow, f, xs): ys = [xShow(x) for x in xs] w = max(map(len, ys)) return s + '\n' + '\n'.join(map( lambda x, y: y.rjust(w, ' ') + ' -> ' + fxShow(f(x)), xs, ys )) return go
- ------------------------ GENERIC -------------------------
- insert :: Array Int -> Int -> Int -> Array Int
def insert(xs, i, v):
An array updated at position i with value v. xs[i] = v return xs
- mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])
def mapAccumL(f):
A tuple of an accumulation and a list derived by a combined map and fold, with accumulation from left to right. def go(a, x): tpl = f(a[0], x) return (tpl[0], a[1] + [tpl[1]]) return lambda acc: lambda xs: ( reduce(go, xs, (acc, [])) )
- MAIN ---
if __name__ == '__main__':
main()</lang>
- Output:
The last 10 of the first N vanEck terms: N=10 -> [0, 0, 1, 0, 2, 0, 2, 2, 1, 6] N=1000 -> [4, 7, 30, 25, 67, 225, 488, 0, 10, 136] N=10000 -> [7, 43, 190, 396, 2576, 3142, 0, 7, 7, 1]
Racket
<lang racket>#lang racket (require racket/stream)
(define (van-eck)
(define (next val n seen) (define val1 (- n (hash-ref seen val n))) (stream-cons val (next val1 (+ n 1) (hash-set seen val n)))) (next 0 0 (hash)))
(define (get m n s)
(stream->list (stream-take (stream-tail s m) (- n m))))
"First 10 terms:" (get 0 10 (van-eck)) "Terms 991 to 1000 terms:" (get 990 1000 (van-eck)) ; counting from 0</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)
Raku
(formerly Perl 6) There is not a Van Eck sequence, rather a series of related sequences that differ in their starting value. This task is nominally for the sequence starting with the value 0. This Raku implementation will handle any integer starting value.
Specifically handles:
- OEIS:A181391 - Van Eck sequence starting with 0
- OEIS:A171911 - Van Eck sequence starting with 1
- OEIS:A171912 - Van Eck sequence starting with 2
- OEIS:A171913 - Van Eck sequence starting with 3
- OEIS:A171914 - Van Eck sequence starting with 4
- OEIS:A171915 - Van Eck sequence starting with 5
- OEIS:A171916 - Van Eck sequence starting with 6
- OEIS:A171917 - Van Eck sequence starting with 7
- OEIS:A171918 - Van Eck sequence starting with 8
among others.
Implemented as lazy, extendable lists.
<lang perl6>sub n-van-ecks ($init) {
$init, -> $i, { state %v; state $k; $k++; my $t = %v{$i}.defined ?? $k - %v{$i} !! 0; %v{$i} = $k; $t } ... *
}
for <
A181391 0 A171911 1 A171912 2 A171913 3 A171914 4 A171915 5 A171916 6 A171917 7 A171918 8
> -> $seq, $start {
my @seq = n-van-ecks($start);
# The task put qq:to/END/
Van Eck sequence OEIS:$seq; with the first term: $start First 10 terms: {@seq[^10]} Terms 991 through 1000: {@seq[990..999]} END
}</lang>
- Output:
Van Eck sequence OEIS:A181391; with the first term: 0 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 Van Eck sequence OEIS:A171911; with the first term: 1 First 10 terms: 1 0 0 1 3 0 3 2 0 3 Terms 991 through 1000: 0 6 53 114 302 0 5 9 22 71 Van Eck sequence OEIS:A171912; with the first term: 2 First 10 terms: 2 0 0 1 0 2 5 0 3 0 Terms 991 through 1000: 8 92 186 0 5 19 41 413 0 5 Van Eck sequence OEIS:A171913; with the first term: 3 First 10 terms: 3 0 0 1 0 2 0 2 2 1 Terms 991 through 1000: 5 5 1 17 192 0 6 34 38 179 Van Eck sequence OEIS:A171914; with the first term: 4 First 10 terms: 4 0 0 1 0 2 0 2 2 1 Terms 991 through 1000: 33 410 0 6 149 0 3 267 0 3 Van Eck sequence OEIS:A171915; with the first term: 5 First 10 terms: 5 0 0 1 0 2 0 2 2 1 Terms 991 through 1000: 60 459 0 7 13 243 0 4 10 211 Van Eck sequence OEIS:A171916; with the first term: 6 First 10 terms: 6 0 0 1 0 2 0 2 2 1 Terms 991 through 1000: 6 19 11 59 292 0 6 6 1 12 Van Eck sequence OEIS:A171917; with the first term: 7 First 10 terms: 7 0 0 1 0 2 0 2 2 1 Terms 991 through 1000: 11 7 2 7 2 2 1 34 24 238 Van Eck sequence OEIS:A171918; with the first term: 8 First 10 terms: 8 0 0 1 0 2 0 2 2 1 Terms 991 through 1000: 16 183 0 6 21 10 249 0 5 48
REXX
using a list
This REXX version allows the specification of the start and end of the Van Eck sequence (to be displayed) as
well as the initial starting element (the default is zero).
<lang rexx>/*REXX pgm generates/displays the 'start ──► end' elements of the Van Eck sequence.*/
parse arg LO HI $ . /*obtain optional arguments from the CL*/
if LO== | LO=="," then LO= 1 /*Not specified? Then use the default.*/
if HI== | HI=="," then HI= 10 /* " " " " " " */
if $== | $=="," then $= 0 /* " " " " " " */
$$=; z= $ /*$$: old seq: $: initial value of seq*/
do HI-1; z= wordpos( reverse(z), reverse($$) ); $$= $; $= $ z end /*HI-1*/ /*REVERSE allows backwards search in $.*/ /*stick a fork in it, we're all done. */
say 'terms ' LO " through " HI ' of the Van Eck sequence are: ' subword($,LO,HI-LO+1)</lang>
- output when using the default inputs:
terms 1 through 10 of the Van Eck sequence are: 0 0 1 0 2 0 2 2 1 6
- output when using the inputs of: 991 1000
terms 991 through 1000 of the Van Eck sequence are: 4 7 30 25 67 225 488 0 10 136
- output when using the inputs of: 1 20 6
terms 1 through 20 of the Van Eck sequence are: 6 0 0 1 0 2 0 2 2 1 6 10 0 6 3 0 3 2 9 0
using a dictionary
This REXX version (which uses a dictionary) is about 20,000 times faster (when using larger numbers) than
using a list (in finding the previous location of an "old" number (term).
<lang rexx>/*REXX pgm generates/displays the 'start ──► end' elements of the Van Eck sequence.*/
parse arg LO HI sta . /*obtain optional arguments from the CL*/
if LO== | LO=="," then LO= 1 /*Not specified? Then use the default.*/
if HI== | HI=="," then HI= 10 /* " " " " " " */
if sta== | sta=="," then sta= 0 /* " " " " " " */
$.0= sta; x= sta; @.=. /*$.: the Van Eck sequence as a list.*/
do #=1 for HI-1 /*X: is the last term being examined. */ if @.x==. then do; @.x= #; $.#= 0; x= 0; end /*new term.*/ else do; z= # - @.x; $.#= z; @.x= #; x= z; end /*old term.*/ end /*#*/ /*Z: the new term being added to list.*/ LOw= LO - 1; out= $.LOw /*initialize the output value. */ do j=LO to HI-1; out= out $.j /*build a list for the output display. */ end /*j*/ /*stick a fork in it, we're all done. */
say 'terms ' LO " through " HI ' of the Van Eck sequence are: ' out</lang>
- output is identical to the 1st REXX version.
Ruby
<lang ruby>van_eck = Enumerator.new do |y|
ar = [0] loop do y << (term = ar.last) # yield ar << (ar.count(term)==1 ? 0 : ar.size - 1 - ar[0..-2].rindex(term)) end
end
ve = van_eck.take(1000) p ve.first(10), ve.last(10) </lang>
- Output:
[0, 0, 1, 0, 2, 0, 2, 2, 1, 6] [4, 7, 30, 25, 67, 225, 488, 0, 10, 136]
Rust
<lang rust>fn van_eck_sequence() -> impl std::iter::Iterator<Item = i32> {
let mut index = 0; let mut last_term = 0; let mut last_pos = std::collections::HashMap::new(); std::iter::from_fn(move || { let result = last_term; let mut next_term = 0; if let Some(v) = last_pos.get_mut(&last_term) { next_term = index - *v; *v = index; } else { last_pos.insert(last_term, index); } last_term = next_term; index += 1; Some(result) })
}
fn main() {
let mut v = van_eck_sequence().take(1000); println!("First 10 terms of the Van Eck sequence:"); for n in v.by_ref().take(10) { print!("{} ", n); } println!("\nTerms 991 to 1000 of the Van Eck sequence:"); for n in v.skip(980) { print!("{} ", n); } println!();
}</lang>
- Output:
First 10 terms of the Van Eck sequence: 0 0 1 0 2 0 2 2 1 6 Terms 991 to 1000 of the Van Eck sequence: 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).
Sidef
<lang ruby>func van_eck(n) {
var seen = Hash() var seq = [0] var prev = seq[-1]
for k in (1 ..^ n) { seq << (seen.has(prev) ? (k - seen{prev}) : 0) seen{prev} = k prev = seq[-1] }
seq
}
say van_eck(10) say van_eck(1000).slice(991-1, 1000-1)</lang>
- Output:
[0, 0, 1, 0, 2, 0, 2, 2, 1, 6] [4, 7, 30, 25, 67, 225, 488, 0, 10, 136]
Swift
<lang swift>struct VanEckSequence: Sequence, IteratorProtocol {
private var index = 0 private var lastTerm = 0 private var lastPos = Dictionary<Int, Int>() mutating func next() -> Int? { let result = lastTerm var nextTerm = 0 if let v = lastPos[lastTerm] { nextTerm = index - v } lastPos[lastTerm] = index lastTerm = nextTerm index += 1 return result }
}
let seq = VanEckSequence().prefix(1000)
print("First 10 terms of the Van Eck sequence:") for n in seq.prefix(10) {
print(n, terminator: " ")
} print("\nTerms 991 to 1000 of the Van Eck sequence:") for n in seq.dropFirst(990) {
print(n, terminator: " ")
} print()</lang>
- Output:
First 10 terms of the Van Eck sequence: 0 0 1 0 2 0 2 2 1 6 Terms 991 to 1000 of the Van Eck sequence: 4 7 30 25 67 225 488 0 10 136
Tcl
<lang Tcl>## Mathematically, the first term has index "0", not "1". We do that, also.
set ::vE 0
proc vanEck {n} {
global vE vEocc while {$n >= [set k [expr {[llength $vE] - 1}]]} { set kv [lindex $vE $k] ## value $kv @ $k is not yet stuffed into vEocc() lappend vE [expr {[info exists vEocc($kv)] ? $k - $vEocc($kv) : 0}] set vEocc($kv) $k } return [lindex $vE $n]
}
proc show {func from to} {
for {set n $from} {$n <= $to} {incr n} { append r " " [$func $n] } puts "${func}($from..$to) =$r"
}
show vanEck 0 9 show vanEck 990 999</lang>
- Output:
vanEck(0..9) = 0 0 1 0 2 0 2 2 1 6 vanEck(990..999) = 4 7 30 25 67 225 488 0 10 136
Wren
<lang javascript>var max = 1000 var a = List.filled(max, 0) var seen = {} for (n in 0...max-1) {
var m = seen[a[n]] if (m != null) a[n+1] = n - m seen[a[n]] = n
} System.print("The first ten terms of the Van Eck sequence are:") System.print(a[0...10]) System.print("\nTerms 991 to 1000 of the sequence are:") System.print(a[990..-1])</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]
zkl
<lang zkl>fcn vanEck(startAt=0){ // --> iterator
(startAt).walker(*).tweak(fcn(n,seen,rprev){ prev,t := rprev.value, n - seen.find(prev,n); seen[prev] = n; rprev.set(t); t }.fp1(Dictionary(),Ref(startAt))).push(startAt)
}</lang> <lang zkl>foreach n in (9){
ve:=vanEck(n); println("The first ten terms of the Van Eck (%d) sequence are:".fmt(n)); println("\t",ve.walk(10).concat(",")); println(" Terms 991 to 1000 of the sequence are:"); println("\t",ve.drop(990-10).walk(10).concat(","));
}</lang>
- Output:
The first ten terms of the Van Eck (0) 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 The first ten terms of the Van Eck (1) sequence are: 1,0,0,1,3,0,3,2,0,3 Terms 991 to 1000 of the sequence are: 0,6,53,114,302,0,5,9,22,71 The first ten terms of the Van Eck (2) sequence are: 2,0,0,1,0,2,5,0,3,0 Terms 991 to 1000 of the sequence are: 8,92,186,0,5,19,41,413,0,5 The first ten terms of the Van Eck (3) sequence are: 3,0,0,1,0,2,0,2,2,1 Terms 991 to 1000 of the sequence are: 5,5,1,17,192,0,6,34,38,179 The first ten terms of the Van Eck (4) sequence are: 4,0,0,1,0,2,0,2,2,1 Terms 991 to 1000 of the sequence are: 33,410,0,6,149,0,3,267,0,3 The first ten terms of the Van Eck (5) sequence are: 5,0,0,1,0,2,0,2,2,1 Terms 991 to 1000 of the sequence are: 60,459,0,7,13,243,0,4,10,211 The first ten terms of the Van Eck (6) sequence are: 6,0,0,1,0,2,0,2,2,1 Terms 991 to 1000 of the sequence are: 6,19,11,59,292,0,6,6,1,12 The first ten terms of the Van Eck (7) sequence are: 7,0,0,1,0,2,0,2,2,1 Terms 991 to 1000 of the sequence are: 11,7,2,7,2,2,1,34,24,238 The first ten terms of the Van Eck (8) sequence are: 8,0,0,1,0,2,0,2,2,1 Terms 991 to 1000 of the sequence are: 16,183,0,6,21,10,249,0,5,48