A066637 Total number of elements in all factorizations of n with all factors > 1.

0, 1, 1, 3, 1, 3, 1, 6, 3, 3, 1, 8, 1, 3, 3, 12, 1, 8, 1, 8, 3, 3, 1, 17, 3, 3, 6, 8, 1, 10, 1, 20, 3, 3, 3, 22, 1, 3, 3, 17, 1, 10, 1, 8, 8, 3, 1, 34, 3, 8, 3, 8, 1, 17, 3, 17, 3, 3, 1, 27, 1, 3, 8, 35, 3, 10, 1, 8, 3, 10, 1, 46, 1, 3, 8, 8, 3, 10, 1, 34, 12, 3, 1, 27, 3, 3, 3, 17, 1, 27, 3, 8, 3, 3, 3

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.

The version for partitions is A006128 (strict: A015723).

Choosing a value instead of position gives A339564.

A000070 counts partitions with a selected part.

A001055 counts factorizations.

A002033 and A074206 count ordered factorizations.

A067824 counts strict chains of divisors starting with n.

A336875 counts compositions with a selected part.

Cf. A000005, A000041, A045778, A050336, A066186, A162247, A264401, A281116, A292504, A292886, A322794.

Sequence in context: A367628 A126212 A357858 * A317144 A050336 A281113

Adjacent sequences: A066634 A066635 A066636 * A066638 A066639 A066640

Keyword

nonn

Author

Amarnath Murthy, Dec 28 2001

Status

approved