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
Examples
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.
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.
- Arnold Knopfmacher and Michael Mays, Ordered and Unordered Factorizations of Integers, The Mathematica Journal, Vol 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
Crossrefs
Programs
-
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 -
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 *)
-
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
-
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
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
Extensions
Edited by Franklin T. Adams-Watters, Jun 04 2009
Comments