|
%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
|
