Van Eck sequence: Difference between revisions
(I thought the longest sequence of non zeroes in the first 100 million items might be interesting) |
(→{{header|REXX}}: fixed program to not raise the NOVALUE condition.) |
||
Line 324: | Line 324: | ||
if HI=='' | HI=="," then HI= 10 /* " " " " " " */ |
if HI=='' | HI=="," then HI= 10 /* " " " " " " */ |
||
if $=='' | $=="," then $= 0 /* " " " " " " */ |
if $=='' | $=="," then $= 0 /* " " " " " " */ |
||
$$=; 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 $.*/ |
Revision as of 15:19, 20 June 2019
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.
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]
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:
- 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
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 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
<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