extra/project-euler/463/463.factor

   1 ! Copyright (c) 2023 Cecilia Knaebchen.
   2 ! See https://factorcode.org/license.txt for BSD license.
   3 USING: combinators kernel locals math math.functions
   4 project-euler.common ;
   5 IN: project-euler.463
   6
   7 ! https://projecteuler.net/problem=463
   8
   9 ! DESCRIPTION
  10 ! -----------
  11
  12 ! The function f is defined for all positive integers as
  13 ! follows:
  14
  15 ! f(1) = 1
  16 ! f(3) = 3
  17 ! f(2n) = f(n)
  18 ! f(4n+1) = 2f(2n+1) - f(n)
  19 ! f(4n+3) = 3f(2n+1) - 2f(n)
  20
  21 ! The function S(n) is defined as Σ_{i=1}^n f(i)
  22
  23 ! S(8) = 22 and S(100) = 3604
  24
  25 ! Find S(3^37). Give the last 9 digits of your answer.
  26
  27
  28 ! SOLUTION
  29 ! --------
  30
  31 ! Recursion for S(n):
  32 ! S(n) = S([n/2]) + 2S([(n+1)/2]) + 3S([(n-1)/2]) -
  33 !        2S([(n+1)/4]) - 4S([(n-1)/4]) - 2S([(n-3)/4]) - 1
  34
  35 MEMO:: S ( n -- Sn )
  36     n {
  37         { -1 [ 0 ] }
  38         { 0 [ 0 ] }
  39         { 1 [ 1 ] }
  40         [
  41             drop n 2 /i S
  42             n 1 + 2 /i S 2 * +
  43             n 1 - 2 /i S 3 * +
  44             n 1 + 4 /i S 2 * -
  45             n 1 - 4 /i S 4 * -
  46             n 3 - 4 /i S 2 * - 1 -
  47         ]
  48     } case ;
  49
  50 : euler463 ( -- answer )
  51     3 37 ^ S 1000000000 mod ;
  52
  53 ! [ euler463 ] time
  54 ! 0.14 ms
  55
  56 SOLUTION: euler463