extra/project-euler/190/190.factor

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