rindolf_euler_618.p6

# The Expat License
#
# Copyright (c) 2018, Shlomi Fish
#
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.


my int $BASE = 1000000000;

my int @PRIMES = (2, 3);

sub calc_S(int $n, $token='foo')
{
    my int @primes = grep { $_ <= $n }, @PRIMES;

    return 0 if !@primes;

    my int @d;
    my int $r = 1;
    for 0..$n -> int $m
    {
        if $m +& 1 == 0
        {
            @d.push($r);
            $r = ($r +< 1) % $BASE;
        }
        else
        {
            @d.push(0);
        }
    }
    for @primes[1..*] -> int $p {
        say $token, ' ', $p;
        for $p .. $n -> int $m {
            my int $a = @d[$m];
            my int $b = @d[$m-$p];
            @d[$m] = ($a + $p * $b) % $BASE;
        }
    }
    return @d;
}

my int $a = 1;
my int $b = 1;
my int @Fk;
for 2..24 -> int $i
{
    @Fk.push($b);
    ($a, $b) = ($b, $a+$b);
}
my int @ret = calc_S($a, "$a");
# assert ret[8] == 49
# assert ret[1] == 0
# assert ret[2] == 2
# assert ret[3] == 3
# assert ret[5] == 11
my int $r = sum(@ret[@Fk]);
printf("ret = %d ; %09d\n",  $r, $r % $BASE); # answer should be `ret = 7634212216 ; 634212216`