A128630 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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.