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.

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

Adjacent sequences: A128627 A128628 A128629 * A128631 A128632 A128633

Keyword

nonn

Author

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

Status

approved