login
A128630
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.
2
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, 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, 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
OFFSET
0,3
LINKS
Reinhard Zumkeller and Alois P. Heinz, Table of n, a(n) for n = 0..10000
EXAMPLE
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.
MAPLE
b:= proc(n, i) option remember; `if`(n=0 or i=1, n,
min(b(n, i-1), `if`(i>n, infinity, b(n-i, i)+
max(map(h-> h[1], ifactors(i)[2])[]))))
end:
a:= n-> b(n$2):
seq(a(n), n=0..120); # Alois P. Heinz, Apr 15 2015
MATHEMATICA
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 *)
PROG
(Haskell)
a128630 n = a128630_list !! (n-1)
a128630_list = map (minimum . map (sum . map (gpfs !!))) $ tail pss where
pss = [] : map parts [1..] :: [[[Int]]] where
parts u = [u] : [v : ps | v <- [1..u],
ps <- pss !! (u - v), v < head ps]
gpfs = map fromInteger (0 : map a006530 [1..])
-- Reinhard Zumkeller, Apr 13 2015
CROSSREFS
Cf. A128631.
Cf. A006530.
Sequence in context: A261461 A078627 A106370 * A273040 A319982 A304331
KEYWORD
nonn
AUTHOR
Logan Kleinwaks (kleinwaks(AT)alumni.princeton.edu), Mar 15 2007
STATUS
approved