OFFSET
1,4
COMMENTS
From Gus Wiseman, Apr 18 2021: (Start)
Number of ways to choose a factor index or position in a factorization of n. The version selecting a factor value is A339564. For example, the factorizations of n = 2, 4, 8, 12, 16, 24, 30 with a selected position (in parentheses) are:
((2)) ((4)) ((8)) ((12)) ((16)) ((24)) ((30))
((2)*2) ((2)*4) ((2)*6) ((2)*8) ((3)*8) ((5)*6)
(2*(2)) (2*(4)) (2*(6)) (2*(8)) (3*(8)) (5*(6))
((2)*2*2) ((3)*4) ((4)*4) ((4)*6) ((2)*15)
(2*(2)*2) (3*(4)) (4*(4)) (4*(6)) (2*(15))
(2*2*(2)) ((2)*2*3) ((2)*2*4) ((2)*12) ((3)*10)
(2*(2)*3) (2*(2)*4) (2*(12)) (3*(10))
(2*2*(3)) (2*2*(4)) ((2)*2*6) ((2)*3*5)
((2)*2*2*2) (2*(2)*6) (2*(3)*5)
(2*(2)*2*2) (2*2*(6)) (2*3*(5))
(2*2*(2)*2) ((2)*3*4)
(2*2*2*(2)) (2*(3)*4)
(2*3*(4))
((2)*2*2*3)
(2*(2)*2*3)
(2*2*(2)*3)
(2*2*2*(3))
(End)
REFERENCES
Amarnath Murthy, Generalization of Partition function, Introducing Smarandache Factor partitions, Smarandache Notions Journal, Vol. 11, 1-2-3, Spring 2000.
Amarnath Murthy, Length and extent of Smarandache Factor partitions, Smarandache Notions Journal, Vol. 11, 1-2-3, Spring 2000.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..20000 (first 1000 terms from T. D. Noe)
EXAMPLE
a(12) = 8: there are 4 factorizations of 12: (12), (6*2), (4*3), (3*2*2) having 1, 2, 2, 3 elements respectively, a total of 8.
MAPLE
# Return a list of lists which are factorizations (product representations)
# of n. Within each sublist, the factors are sorted. A minimum factor in
# each element of sublists returned can be specified with 'mincomp'.
# If mincomp=2, the number of sublists contained in the list returned is A001055(n).
# Example:
# n=8 and mincomp=2 return [[2, 2, 2], [4, 8], [8]]
listProdRep := proc(n, mincomp)
local dvs, resul, f, i, j, rli, tmp ;
resul := [] ;
# list returned is empty if n < mincomp
if n >= mincomp then
if n = 1 then
RETURN([1]) ;
else
# compute the divisors, and take each divisor
# as a head element (minimum element) of one of the
# sublists. Example: for n=8 use {1, 2, 4, 8}, and consider
# (for mincomp=2) sublists [2, ...], [4, ...] and [8].
dvs := numtheory[divisors](n) ;
for i from 1 to nops(dvs) do
# select the head element 'f' from the divisors
f := op(i, dvs) ;
# if this is already the maximum divisor n
# itself, this head element is the last in
# the sublist
if f =n and f >= mincomp then
resul := [op(resul), [f]] ;
elif f >= mincomp then
# if this is not the maximum element
# n itself, produce all factorizations
# of the remaining factor recursively.
rli := procname(n/f, f) ;
# Prepend all the results produced
# from the recursion with the head
# element for the result.
for j from 1 to nops(rli) do
tmp := [f, op(op(j, rli))] ;
resul := [op(resul), tmp] ;
od ;
fi ;
od ;
fi ;
fi ;
resul ;
end:
A066637 := proc(n)
local f, d;
a := 0 ;
for d in listProdRep(n, 2) do
a := a+nops(d) ;
end do:
a ;
end proc: # R. J. Mathar, Jul 11 2013
# second Maple program:
with(numtheory):
b:= proc(n, k) option remember; `if`(n>k, 0, [1$2])+
`if`(isprime(n), 0, (p-> p+[0, p[1]])(add(
`if`(d>k, 0, b(n/d, d)), d=divisors(n) minus {1, n})))
end:
a:= n-> `if`(n<2, 0, b(n$2)[2]):
seq(a(n), n=1..120); # Alois P. Heinz, Feb 12 2019
MATHEMATICA
g[1, r_] := g[1, r]={1, 0}; g[n_, r_] := g[n, r]=Module[{ds, i, val}, ds=Select[Divisors[n], 1<#<=r&]; val={0, 0}+Sum[g[n/ds[[i]], ds[[i]]], {i, 1, Length[ds]}]; val+{0, val[[1]]}]; a[n_] := g[n, n][[2]]; a/@Range[95] (* g[n, r] = {c, f}, where c is the number of factorizations of n with factors <= r and f is the total number of factors in them. - Dean Hickerson, Oct 28 2002 *)
facs[n_]:=If[n<=1, {{}}, Join@@Table[Map[Prepend[#, d]&, Select[facs[n/d], Min@@#>=d&]], {d, Rest[Divisors[n]]}]]; Table[Sum[Length[fac], {fac, facs[n]}], {n, 50}] (* Gus Wiseman, Apr 18 2021 *)
CROSSREFS
The version for normal multisets is A001787.
The version for compositions is A001792.
Choosing a value instead of position gives A339564.
A000070 counts partitions with a selected part.
A001055 counts factorizations.
A067824 counts strict chains of divisors starting with n.
A336875 counts compositions with a selected part.
KEYWORD
nonn
AUTHOR
Amarnath Murthy, Dec 28 2001
STATUS
approved