extra/project-euler/188/188.factor

   1 ! Copyright (c) 2009 Guillaume Nargeot.
   2 ! See https://factorcode.org/license.txt for BSD license.
   3 USING: kernel math math.functions project-euler.common ;
   4 IN: project-euler.188
   5
   6 ! https://projecteuler.net/problem=188
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  11 ! The hyperexponentiation or tetration of a number a by a
  12 ! positive integer b, denoted by a↑↑b or ^(b)a, is recursively
  13 ! defined by:
  14
  15 ! a↑↑1 = a,
  16 ! a↑↑(k+1) = a^(a↑↑k).
  17
  18 ! Thus we have e.g. 3↑↑2 = 3^3 = 27, hence
  19 ! 3↑↑3 = 3^27 = 7625597484987 and
  20 ! 3↑↑4 is roughly 10^(3.6383346400240996*10^12).
  21
  22 ! Find the last 8 digits of 1777↑↑1855.
  23
  24
  25 ! SOLUTION
  26 ! --------
  27
  28 ! Using modular exponentiation.
  29 ! https://en.wikipedia.org/wiki/Modular_exponentiation
  30
  31 <PRIVATE
  32
  33 : hyper-exp-mod ( a b m -- e )
  34     1 rot [ [ 2dup ] dip swap ^mod ] times 2nip ;
  35
  36 PRIVATE>
  37
  38 : euler188 ( -- answer )
  39     1777 1855 10 8 ^ hyper-exp-mod ;
  40
  41 ! [ euler188 ] 100 ave-time
  42 ! 4 ms ave run time - 0.05 SD (100 trials)
  43
  44 SOLUTION: euler188