|
%I #87 Feb 20 2024 18:37:43
%S 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 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 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 Number of factorizations of n into distinct factors greater than 1.
%C This sequence depends only on the prime signature of n and not on the actual value of n.
%C Also the number of strict multiset partitions (sets of multisets) of the prime factors of n. - _Gus Wiseman_, Dec 03 2016
%C Number of sets of integers greater than 1 whose product is n. - _Antti Karttunen_, Feb 20 2024
%H David W. Wilson, <a href="/A045778/b045778.txt">Table of n, a(n) for n = 1..10000</a>
%H 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 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 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 A. Knopfmacher, M. Mays, Ordered and Unordered Factorizations of Integers: <a href="http://www.mathematica-journal.com/issue/v10i1/contents/Factorizations/Factorizations_3.html">Unordered Factorizations with Distinct Parts</a>, The Mathematica Journal 10(1), 2006.
%H R. J. Mathar, <a href="/A045778/a045778.txt">Factorizations of n = 1..1500</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/UnorderedFactorization.html">Unordered Factorization</a>
%H <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>
%F Dirichlet g.f.: Product_{n>=2}(1 + 1/n^s).
%F 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 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 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 with(numtheory):
%p b:= proc(n, k) option remember;
%p `if`(n>k, 0, 1) +`if`(isprime(n), 0,
%p add(`if`(d>k, 0, b(n/d, d-1)), d=divisors(n) minus {1, n}))
%p end:
%p a:= n-> b(n$2):
%p seq(a(n), n=1..120); # _Alois P. Heinz_, May 26 2013
%t 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 (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 (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 (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 (PARI)
%o (Python)
%o from sympy.core.cache import cacheit
%o from sympy import divisors, isprime
%o @cacheit
%o 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 def a(n): return b(n, n)
%o print([a(n) for n in range(1, 121)]) # _Indranil Ghosh_, Aug 19 2017, after Maple code
%o (APL, Dyalog dialect)
%o divisors ← {ð←⍵{(0=⍵|⍺)/⍵}⍳⌊⍵*÷2 ⋄ 1=⍵:ð ⋄ ð, (⍵∘÷)¨(⍵=(⌊⍵*÷2)*2)↓⌽ð}
%o A045778 ← { D←1↓divisors(⍵) ⋄ T←(⍴D)⍴2 ⋄ +/⍵⍷{×/D/⍨T⊤⍵}¨(-∘1)⍳2*⍴D } ⍝ (simple, but a memory hog)
%o A045778 ← { ⍺←⌽divisors(⍵) ⋄ 1=⍵:1 ⋄ 0=≢⍺:0 ⋄ R←⍺↓⍨⍺⍳⍵∘÷ ⋄ Ð←{⍺/⍨0=⍺|⍵} ⋄ +/(((R)Ð⊢)∇⊢)¨(⍵∘÷)¨⍺ } ⍝ (more efficient) - _Antti Karttunen_, Feb 20 2024
%Y Cf. A001055, A045779, A045780, A050323. a(p^k)=A000009. a(A002110) = A000110.
%Y Cf. A036469, A114591, A114592, A316441 (Dirichlet inverse).
%Y Cf. A156648 (2*Dgf at s=2), A073017 (2*Dgf at s=3), A258870 (2*Dgf at s=4).
%Y Cf. also A069626 (Number of sets of integers > 1 whose least common multiple is n).
%K nonn,easy,nice
%O 1,6
%A _David W. Wilson_
%E Edited by _Franklin T. Adams-Watters_, Jun 04 2009
|
