extra/project-euler/188/188.factor

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