A045778 Number of factorizations of n into distinct factors greater than 1.

1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 2, 2, 1, 3, 1, 3, 2, 2, 1, 5, 1, 2, 2, 3, 1, 5, 1, 3, 2, 2, 2, 5, 1, 2, 2, 5, 1, 5, 1, 3, 3, 2, 1, 7, 1, 3, 2, 3, 1, 5, 2, 5, 2, 2, 1, 9, 1, 2, 3, 4, 2, 5, 1, 3, 2, 5, 1, 9, 1, 2, 3, 3, 2, 5, 1, 7, 2, 2, 1, 9, 2, 2, 2, 5, 1, 9, 2, 3, 2, 2, 2, 10, 1, 3, 3, 5, 1, 5, 1, 5

Offset

1,6

Comments

This sequence depends only on the prime signature of n and not on the actual value of n.

Also the number of strict multiset partitions (sets of multisets) of the prime factors of n. - Gus Wiseman, Dec 03 2016

Number of sets of integers greater than 1 whose product is n. - Antti Karttunen, Feb 20 2024

Links

David W. Wilson, Table of n, a(n) for n = 1..10000

Philippe A. J. G. Chevalier, On the discrete geometry of physical quantities, Preprint, 2012.

P. A. J. G. Chevalier, On a Mathematical Method for Discovering Relations Between Physical Quantities: a Photonics Case Study, Slides from a talk presented at ICOL2014.

P. A. J. G. Chevalier, A "table of Mendeleev" for physical quantities?, Slides from a talk, May 14 2014, Leuven, Belgium.

A. Knopfmacher, M. Mays, Ordered and Unordered Factorizations of Integers: Unordered Factorizations with Distinct Parts, The Mathematica Journal 10(1), 2006.

R. J. Mathar, Factorizations of n = 1..1500

Eric Weisstein's World of Mathematics, Unordered Factorization

Index entries for sequences computed from exponents in factorization of n

Formula

Dirichlet g.f.: Product_{n>=2}(1 + 1/n^s).

Let p and q be two distinct prime numbers and k a natural number. Then a(p^k) = A000009(k) and a(p^k*q) = A036469(k). - Alexander Adam, Dec 28 2012

Let p_i with 1<=i<=k k distinct prime numbers. Then a(Product_{i=1..k} p_i) = A000110(k). - Alexander Adam, Dec 28 2012

Example

24 can be factored as 24, 2*12, 3*8, 4*6, or 2*3*4, so a(24) = 5. The factorization 2*2*6 is not permitted because the factor 2 is present twice. a(1) = 1 represents the empty factorization.

Maple

with(numtheory):
b:= proc(n, k) option remember;
      `if`(n>k, 0, 1) +`if`(isprime(n), 0,
      add(`if`(d>k, 0, b(n/d, d-1)), d=divisors(n) minus {1, n}))
    end:
a:= n-> b(n$2):
seq(a(n), n=1..120);  # Alois P. Heinz, May 26 2013

Mathematica

gd[m_, 1] := 1; gd[1, n_] := 0; gd[1, 1] := 1; gd[0, n_] := 0; gd[m_, n_] := gd[m, n] = Total[gd[# - 1, n/#] & /@ Select[Divisors[n], # <= m &]]; Array[ gd[#, #] &, 100]  (* Alexander Adam, Dec 28 2012 *)

Prog

(PARI) v=vector(100, k, k==1); for(n=2, #v, v+=dirmul(v, vector(#v, k, k==n)) ); v /* Max Alekseyev, Jul 16 2014 */
(PARI) A045778(n, k=n) = ((n<=k) + sumdiv(n, d, if(d > 1 && d <= k && d < n, A045778(n/d, d-1)))); \\ After Alois P. Heinz's Maple-code by Antti Karttunen, Jul 23 2017, edited Feb 20 2024
(PARI) A045778(n, m=n) = if(1==n, 1, sumdiv(n, d, if((d>1)&&(d<=m), A045778(n/d, d-1)))); \\ Antti Karttunen, Feb 20 2024
(PARI)
(Python)
from sympy.core.cache import cacheit
from sympy import divisors, isprime
@cacheit
def b(n, k): return (0 if n>k else 1) + (0 if isprime(n) else sum(0 if d>k else b(n//d, d - 1) for d in divisors(n)[1:-1]))
def a(n): return b(n, n)
print([a(n) for n in range(1, 121)]) # Indranil Ghosh, Aug 19 2017, after Maple code
(APL, Dyalog dialect)
divisors ← {ð←⍵{(0=⍵|⍺)/⍵}⍳⌊⍵*÷2 ⋄ 1=⍵:ð ⋄ ð, (⍵∘÷)¨(⍵=(⌊⍵*÷2)*2)↓⌽ð}
A045778 ← { D←1↓divisors(⍵) ⋄ T←(⍴D)⍴2 ⋄ +/⍵⍷{×/D/⍨T⊤⍵}¨(-∘1)⍳2*⍴D } ⍝ (simple, but a memory hog)
A045778 ← { ⍺←⌽divisors(⍵) ⋄ 1=⍵:1 ⋄ 0=≢⍺:0 ⋄ R←⍺↓⍨⍺⍳⍵∘÷ ⋄ Ð←{⍺/⍨0=⍺|⍵} ⋄ +/(((R)Ð⊢)∇⊢)¨(⍵∘÷)¨⍺ } ⍝ (more efficient) - Antti Karttunen, Feb 20 2024

Crossrefs

Cf. A001055, A045779, A045780, A050323. a(p^k)=A000009. a(A002110) = A000110.

Cf. A036469, A114591, A114592, A316441 (Dirichlet inverse).

Cf. A156648 (2*Dgf at s=2), A073017 (2*Dgf at s=3), A258870 (2*Dgf at s=4).

Cf. also A069626 (Number of sets of integers > 1 whose least common multiple is n).

Sequence in context: A316364 A318357 A323091 * A320889 A296133 A338649

Adjacent sequences: A045775 A045776 A045777 * A045779 A045780 A045781

Keyword

nonn,easy,nice

Author

David W. Wilson

Extensions

Edited by Franklin T. Adams-Watters, Jun 04 2009

Status

approved