extra/project-euler/190/190.factor

   1 ! Copyright (c) 2008 Eric Mertens
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel sequences sequences.lib math math.functions math.ranges locals ;
   4 IN: project-euler.190
   5
   6 ! PROBLEM
   7 ! -------
   8
   9 ! http://projecteuler.net/index.php?section=problems&id=190
  10
  11 ! Let Sm = (x1, x2, ... , xm) be the m-tuple of positive real numbers
  12 ! with x1 + x2 + ... + xm = m for which Pm = x1 * x22 * ... * xmm is
  13 ! maximised.
  14
  15 ! For example, it can be verified that [P10] = 4112 ([ ] is the integer
  16 ! part function).
  17
  18 ! Find Σ[Pm] for 2 ≤ m ≤ 15.
  19
  20 ! SOLUTION
  21 ! --------
  22
  23 ! Pm = x1 * x2^2 * x3^3 * ... * xm^m
  24 ! fm = x1 + x2 + x3 + ... + xm - m = 0
  25 ! Gm === Pm - L * fm
  26 ! dG/dx_i = 0 = i * Pm / xi - L
  27 ! xi = i * Pm / L
  28
  29 ! Sum(i=1 to m) xi = m
  30 ! Sum(i=1 to m) i * Pm / L = m
  31 ! Pm / L * Sum(i=1 to m) i = m
  32 ! Pm / L * m*(m+1)/2 = m
  33 ! Pm / L = 2 / (m+1)
  34
  35 ! xi = i * (2 / (m+1)) = 2*i/(m+1)
  36
  37 <PRIVATE
  38
  39 : PI ( seq quot -- n )
  40     [ * ] compose 1 swap reduce ; inline
  41
  42 PRIVATE>
  43
  44 :: P_m ( m -- P_m )
  45     m [1,b] [| i | 2 i * m 1+ / i ^ ] PI ;
  46
  47 : euler190 ( -- n )
  48     2 15 [a,b] [ P_m truncate ] sigma ;