loading...

Raku: Van Eck Sequence Generator

gugod profile image Kang-min Liu Updated on ・2 min read

One of the tasks from Perl Weekly Challenge #14.1 is to write a program to produce Van Eck sequence. I knew I've heard of it, and yes, it's from a Numberphile video: Numberphile -- Don't Know (the Van Eck Sequence) and OEIS/A181391.

To describe the Van Eck sequence: The first term is 0, and the following terms are defined to be the number of occurrences of the previous term, subtracted by the term index.

a[1] = 0
a[n+1] = 0, if a[n] is absent within a[0..n]
a[n+1] = n - m, Otherwise, where a[m] = a[n] and m < n and m is the largest of such.
Enter fullscreen mode Exit fullscreen mode

By definition, to compute a[n+1], we look backward the entire sequence for a[n].

~laurent_r offered a loop-based solution:

use v6;

my @a = 0,;
for ^20 -> $n {
    my $result = 0;
    for reverse ^$n -> $m {
        $result = $n - $m and last if @a[$m] == @a[$n];
            # Note: $m is always smaller than $n, so $n - $m > 0
    }
    push @a, $result;
}
say @a;
Enter fullscreen mode Exit fullscreen mode

Given the infinite nature of this sequence, I would like to make an object that represent this infinite sequence and, of course, lazily evaluated. Here's the result:

my $vaneck = Seq.new(
    class :: does Iterator {
        has %!seen is default(-1);
        has Int $!term = -1;
        has Int $!pos  = 0;
        method pull-one {
            my $next = %!seen{$!term} == -1 ?? 0 !! $!pos - %!seen{$!term};
            %!seen{$!term} = $!pos++;
            return $!term = $next;
        }
    }.new()
);
Enter fullscreen mode Exit fullscreen mode

Seq and Iterator are both builtin Types in Raku. %!seen is a private variable for recording the position of previous occurrence of numbers.

Here's how you print the beginning 200 terms:

$vaneck[^200].map({ .say });
Enter fullscreen mode Exit fullscreen mode

... or just keep it printing forever:

$vaneck.map({ .say });
Enter fullscreen mode Exit fullscreen mode

本文為 Perl6: Van Eck 數列產生器 之英文版。

Discussion

pic
Editor guide