Van Eck sequence: Difference between revisions

From Rosetta Code
Content added Content deleted
m (→‎{{header|REXX}}: added highlighting to the REXX section header.)
m (→‎{{header|REXX}}: added whitespace.)
Line 452: Line 452:


=={{header|REXX}}==
=={{header|REXX}}==
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).
This REXX version allows the specification of the   ''start''   and   ''end''   of the   ''Van Eck''   sequence   (to be displayed)   as
<br>well as the initial starting element &nbsp; (the default is zero).
<lang rexx>/*REXX pgm generates/displays the 'start ──► end' elements of the Van Eck sequence.*/
<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*/
parse arg LO HI $ . /*obtain optional arguments from the CL*/
Line 459: Line 460:
if $=='' | $=="," then $= 0 /* " " " " " " */
if $=='' | $=="," then $= 0 /* " " " " " " */
$$=; z= $ /*$$: old seq: $: initial value of seq*/
$$=; z= $ /*$$: old seq: $: initial value of seq*/
do j=1 for HI-1; z= wordpos( reverse(z), reverse($$) ); $$=$; $= $ z
do j=1 for HI-1; z= wordpos( reverse(z), reverse($$) ); $$= $; $= $ z
end /*j*/ /*REVERSE allows backwards search in $.*/
end /*j*/ /*REVERSE allows backwards search in $.*/
/*stick a fork in it, we're all done. */
/*stick a fork in it, we're all done. */

Revision as of 11:17, 5 July 2019

Task
Van Eck sequence
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
  1. Create a function/proceedure/method/subroutine/... to generate the Van Eck sequence of numbers.
  2. Use it to display here, on this page:
  1. The first ten terms of the sequence.
  2. Terms 991 - to - 1000 of the sequence.
References


AWK

<lang AWK>

  1. syntax: GAWK -f VAN_ECK_SEQUENCE.AWK
  2. 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

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)

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

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 }

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>

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>

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 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 Perl 6 implementation will handle any integer starting value.

Specifically handles:

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

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
  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 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 j=1  for HI-1;   z= wordpos( reverse(z), reverse($$) );       $$= $;       $= $ z
    end   /*j*/                                 /*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

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).

zkl

Translation of: Perl6

<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
Retrieved from "https://rosettacode.org/wiki/Van_Eck_sequence?oldid=291210"