A128630 - OEIS

%I #15 Feb 05 2017 09:33:32

%S 0,1,2,3,2,3,3,4,2,3,4,5,3,4,5,5,2,3,3,4,4,5,5,6,3,4,5,3,4,5,5,5,2,3,

%T 4,5,3,4,5,6,4,5,6,5,5,5,6,7,3,4,5,6,5,6,3,4,5,6,5,5,5,6,5,6,2,3,4,5,

%U 4,5,5,6,3,4,5,5,5,6,6,7,4,3,4,5,6,5,5,6,5,5,5,5,6,6,7,7,3,4,5,6,5,6,6,7,5,6

%N Let gpf(1)=1 and gpf(n)=greatest prime factor of n, n>1. Then a(n)=minimum sum of gpf of the parts of a partition of n.

%H Reinhard Zumkeller and Alois P. Heinz, <a href="/A128630/b128630.txt">Table of n, a(n) for n = 0..10000</a>

%e a(5)=3 because gpf(5)=5, gpf(4)+gpf(1)=3, gpf(3)+gpf(2)=5, gpf(3)+2*gpf(1)=5, 2*gpf(2)+gpf(1)=5, gpf(2)+3*gpf(1)=5, 5*gpf(1)=5.

%p b:= proc(n, i) option remember; `if`(n=0 or i=1, n,

%p        min(b(n, i-1), `if`(i>n, infinity, b(n-i, i)+

%p        max(map(h-> h[1], ifactors(i)[2])[]))))

%p     end:

%p a:= n-> b(n$2):

%p seq(a(n), n=0..120);  # _Alois P. Heinz_, Apr 15 2015

%t b[n_, i_] := b[n, i] = If[n==0 || i==1, n, Min[b[n, i-1], If[i>n, Infinity, b[n-i, i]+Max[FactorInteger[i][[All, 1]]]]]]; a[n_] := b[n, n]; Table[a[n], {n, 0, 120}] (* _Jean-François Alcover_, Feb 05 2017, after _Alois P. Heinz_ *)

%o (Haskell)

%o a128630 n = a128630_list !! (n-1)

%o a128630_list = map (minimum . map (sum . map (gpfs !!))) $ tail pss where

%o    pss = [] : map parts [1..] :: [[[Int]]] where

%o          parts u = [u] : [v : ps | v <- [1..u],

%o                                    ps <- pss !! (u - v), v < head ps]

%o    gpfs = map fromInteger (0 : map a006530 [1..])

%o -- _Reinhard Zumkeller_, Apr 13 2015

%Y Cf. A128631.

%Y Cf. A006530.

%K nonn

%O 0,3

%A Logan Kleinwaks (kleinwaks(AT)alumni.princeton.edu), Mar 15 2007