Sum of digits sequence

Author: Shlomi Fish

http://projecteuler.net/problem=551

Let a₀, a₁, a₂, ... be an integer sequence defined by:

  • a₀ = 1;

  • for n ≥ 1, an is the sum of the digits of all preceding terms.

The sequence starts with 1, 1, 2, 4, 8, 16, 23, 28, 38, 49, ... You are given a_{10^6} = 31054319.

Find a_{10^{15}}.

Usage

By default the code will only run up to a[1_000_000]; to run the full version, specify the --LIM option on the command line. For progress output, specify the --verbose option. E.g.

perl6 categories/euler/prob551-shlomif.p6 --LIM=1_000_000_000_000_000 --verbose

Source code: prob551-shlomif.p6

use v6;
use MONKEY-TYPING;

my $NUM_DIGITS = 30;

augment class Int
{
    method digits-sum() returns Int
    {
        [+] self.comb;
    }
}

my $A0 = 1;

class Point
{
    has Int $.n;
    # The digits sum.
    has Int $.s;
    # The index.
    has Int $.i;

    method _format() returns Str
    {
        0 x (30 - self.n.chars) ~ self.n;
    }
}

my @calced_arr;

my $a_n = Point.new(n => $A0, i => 1, s => $A0.digits-sum);

# Short for insert.
sub ins(-->Nil)
{
    @calced_arr.push($a_n.clone);
}

ins();


my @cache = [{} xx ($NUM_DIGITS+1)] xx ($NUM_DIGITS*9+1);

sub calc_next(-->Nil)
{
    my $new_n = $a_n.n + $a_n.s;
    $a_n = Point.new(n => $new_n, i => $a_n.i+1, s => $new_n.digits-sum);
}

sub _common_len(Str $s, Str $e)
{
    -1 + (0 .. $NUM_DIGITS).first: { $s.substr($^a, 1) ne $e.substr($^a, 1) };
}

sub cache_delta(-->Nil)
{
    # Start and end.
    my $i = @calced_arr-2;
    my $s = @calced_arr[*-2];
    my $e = @calced_arr[*-1];
    my $s_digits = $s._format;
    my $e_digits = $e._format;
    my $l = _common_len($s_digits, $e_digits);
    for 1 .. $l -> $ll
    {
        @cache[$s.s][$ll]{$s_digits.substr($ll)} = $i;
    }
}

calc_next;
ins;
cache_delta;

sub _print_me()
{
    say "a[%d] = %d".sprintf($a_n.i, $a_n.n);
}

sub MAIN(:$LIM = 1_000_000, Bool :$verbose = False) {
    while $a_n.i < $LIM
    {
        if ($verbose) {
            _print_me if $a_n.i %% 1_000;
        }
        my $a_s = $a_n._format;
        my $to_proc = sub {
            for 1 .. $NUM_DIGITS-1 -> $i
            {
                my $sub_s = $a_s.substr($i);
                my $lookup = @cache[$a_n.s][$i];
                if $lookup{$sub_s}:exists
                {
                    my $start_arr_i = $lookup{$sub_s};
                    my $get_prefix = sub ($idx) {
                        @calced_arr[$idx]._format().substr(0,$i);
                    };
                    my $prefix = $get_prefix.($start_arr_i);
                    my $base_idx = $a_n.i - @calced_arr[$start_arr_i].i;
                    my $end_arr_i = $start_arr_i + 1;
                    my $new_idx = sub () { $base_idx + @calced_arr[$end_arr_i].i; };
                    while $end_arr_i < @calced_arr and $get_prefix.($end_arr_i) eq $prefix and $new_idx.() <= $LIM
                    {
                        $end_arr_i++;
                    }
                    $end_arr_i--;
                    if $end_arr_i > $start_arr_i
                    {
                        $a_n = Point.new(
                            n => $a_n.n + @calced_arr[$end_arr_i].n - @calced_arr[$start_arr_i].n,
                            i => $new_idx.(),
                            s => @calced_arr[$end_arr_i].s
                        );
                        return False;
                    }
                }
            }
            True;
        }.();

        if $to_proc
        {
            calc_next;
        }

        ins;
        cache_delta;
    }

    _print_me;
}