cp's OEIS Frontend

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

%I A045778 #96 Apr 22 2025 03:30:10
%S A045778 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,
%T A045778 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,
%U A045778 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
%N A045778 Number of factorizations of n into distinct factors greater than 1.
%C A045778 This sequence depends only on the prime signature of n and not on the actual value of n.
%C A045778 Also the number of strict multiset partitions (sets of multisets) of the prime factors of n. - _Gus Wiseman_, Dec 03 2016
%C A045778 Number of sets of integers greater than 1 whose product is n. - _Antti Karttunen_, Feb 20 2024
%H A045778 David W. Wilson, <a href="/A045778/b045778.txt">Table of n, a(n) for n = 1..10000</a>
%H A045778 Philippe A. J. G. Chevalier, <a href="https://biblio.ugent.be/publication/8049761/file/8049762">On the discrete geometry of physical quantities</a>, Preprint, 2012.
%H A045778 P. A. J. G. Chevalier, <a href="https://www.researchgate.net/profile/Philippe_Chevalier2/publication/260598331_On_a_Mathematical_Method_for_Discovering_Relations_Between_Physical_Quantities_a_Photonics_Case_Study/links/00b7d531be7b837626000000.pdf">On a Mathematical Method for Discovering Relations Between Physical Quantities: a Photonics Case Study</a>, Slides from a talk presented at ICOL2014.
%H A045778 P. A. J. G. Chevalier, <a href="http://www.researchgate.net/profile/Philippe_Chevalier2/publication/262067273_A_table_of_Mendeleev_for_physical_quantities/links/0c9605368f6d191478000000.pdf">A "table of Mendeleev" for physical quantities?</a>, Slides from a talk, May 14 2014, Leuven, Belgium.
%H A045778 Arnold Knopfmacher and Michael Mays, <a href="https://web.archive.org/web/20140119155532/http://www.mathematica-journal.com/issue/v10i1/contents/Factorizations/Factorizations_3.html">Ordered and Unordered Factorizations of Integers</a>, The Mathematica Journal, Vol 10 (1), 2006.
%H A045778 R. J. Mathar, <a href="/A045778/a045778.txt">Factorizations of n = 1..1500</a>
%H A045778 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/UnorderedFactorization.html">Unordered Factorization</a>
%H A045778 <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>
%F A045778 Dirichlet g.f.: Product_{n>=2} (1 + 1/n^s).
%F A045778 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
%F A045778 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
%e A045778 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.
%p A045778 with(numtheory):
%p A045778 b:= proc(n, k) option remember;
%p A045778       `if`(n>k, 0, 1) +`if`(isprime(n), 0,
%p A045778       add(`if`(d>k, 0, b(n/d, d-1)), d=divisors(n) minus {1, n}))
%p A045778     end:
%p A045778 a:= n-> b(n$2):
%p A045778 seq(a(n), n=1..120);  # _Alois P. Heinz_, May 26 2013
%t A045778 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 *)
%o A045778 (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 */
%o A045778 (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
%o A045778 (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
%o A045778 (Python)
%o A045778 from sympy.core.cache import cacheit
%o A045778 from sympy import divisors, isprime
%o A045778 @cacheit
%o A045778 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]))
%o A045778 def a(n): return b(n, n)
%o A045778 print([a(n) for n in range(1, 121)]) # _Indranil Ghosh_, Aug 19 2017, after Maple code
%o A045778 (APL) ⍝ Dyalog dialect
%o A045778 divisors ← {ð←⍵{(0=⍵|⍺)/⍵}⍳⌊⍵*÷2 ⋄ 1=⍵:ð ⋄ ð, (⍵∘÷)¨(⍵=(⌊⍵*÷2)*2)↓⌽ð}
%o A045778 A045778 ← { D←1↓divisors(⍵) ⋄ T←(⍴D)⍴2 ⋄ +/⍵⍷{×/D/⍨T⊤⍵}¨(-∘1)⍳2*⍴D } ⍝ (simple, but a memory hog)
%o A045778 A045778 ← { ⍺←⌽divisors(⍵) ⋄ 1=⍵:1 ⋄ 0=≢⍺:0 ⋄ R←⍺↓⍨⍺⍳⍵∘÷ ⋄ Ð←{⍺/⍨0=⍺|⍵} ⋄ +/(((R)Ð⊢)∇⊢)¨(⍵∘÷)¨⍺ } ⍝ (more efficient) - _Antti Karttunen_, Feb 20 2024
%Y A045778 Cf. A001055, A045779, A045780, A050323. a(p^k) = A000009. a(A002110) = A000110.
%Y A045778 Cf. A036469, A114591, A114592, A316441 (Dirichlet inverse).
%Y A045778 Cf. A156648 (2*Dgf at s=2), A073017 (2*Dgf at s=3), A258870 (2*Dgf at s=4).
%Y A045778 Cf. also A069626 (Number of sets of integers > 1 whose least common multiple is n).
%Y A045778 Cf. A287549 (partial sums).
%K A045778 nonn,easy,nice
%O A045778 1,6
%A A045778 _David W. Wilson_
%E A045778 Edited by _Franklin T. Adams-Watters_, Jun 04 2009