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
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
KEYWORD
nonn,easy,nice
AUTHOR
EXTENSIONS
Edited by Franklin T. Adams-Watters, Jun 04 2009
STATUS
approved