login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A045778 Number of factorizations of n into distinct factors greater than 1. 23
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 (list; graph; refs; listen; history; text; internal format)
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

The absolute values of the Dirichlet inverse seem to be A190938. - R. J. Mathar, May 25 2017

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)

A045778aux(n, k) = ((n<=k) + sumdiv(n, d, if(d > 1 && d <= k && d < n, A045778aux(n/d, d-1))));

A045778(n) = A045778aux(n, n); \\ After Alois P. Heinz's Maple-code by Antti Karttunen, Jul 23 2017

(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 map(a, xrange(1, 121)) # Indranil Ghosh, Aug 19 2017, after Maple code

CROSSREFS

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

Cf. A036469, A114591, A114592.

Sequence in context: A099042 A140774 A056924 * A033103 A245661 A060775

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 25 18:20 EDT 2017. Contains 292499 sequences.