extra/project-euler/097/097.factor

   1 ! Copyright (c) 2008 Aaron Schaefer.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: math math.functions ;
   4 IN: project-euler.097
   5
   6 ! http://projecteuler.net/index.php?section=problems&id=97
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  11 ! The first known prime found to exceed one million digits was discovered in
  12 ! 1999, and is a Mersenne prime of the form 2^6972593 − 1; it contains exactly
  13 ! 2,098,960 digits. Subsequently other Mersenne primes, of the form 2p − 1,
  14 ! have been found which contain more digits.
  15
  16 ! However, in 2004 there was found a massive non-Mersenne prime which contains
  17 ! 2,357,207 digits: 28433 * 2^7830457 + 1.
  18
  19 ! Find the last ten digits of this prime number.
  20
  21
  22 ! SOLUTION
  23 ! --------
  24
  25 : euler097 ( -- answer )
  26      2 7830457 10 10 ^ ^mod 28433 * 10 10 ^ mod 1+ ;
  27
  28 ! [ euler097 ] 100 ave-time
  29 ! 0 ms ave run timen - 0.22 SD (100 trials)
  30
  31 MAIN: euler097