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; }