A045779 -id:A045779 - cp's OEIS frontend

A045780 Least value with A045779(n) factorizations into distinct factors.

1, 6, 12, 64, 24, 256, 48, 512, 60, 96, 2048, 144, 210, 120, 216, 180, 384, 288, 16384, 240, 432, 420, 65536, 1536, 360, 480, 900, 864, 3072, 1152, 1296, 2310, 524288, 6144, 960, 720, 840, 2304, 1728, 1080, 1260, 2592, 2097152, 1800, 4608, 24576, 4194304, 1440, 3456

Offset: 1

David W. Wilson

nonn

			From _Gus Wiseman_, Jan 11 2020: (Start)
The strict factorizations of a(n) for n = 1..9:
  ()  (6)    (12)   (64)     (24)     (256)     (48)     (512)     (60)
      (2*3)  (2*6)  (2*32)   (3*8)    (4*64)    (6*8)    (8*64)    (2*30)
             (3*4)  (4*16)   (4*6)    (8*32)    (2*24)   (16*32)   (3*20)
                    (2*4*8)  (2*12)   (2*128)   (3*16)   (2*256)   (4*15)
                             (2*3*4)  (2*4*32)  (4*12)   (4*128)   (5*12)
                                      (2*8*16)  (2*3*8)  (2*4*64)  (6*10)
                                                (2*4*6)  (2*8*32)  (2*5*6)
                                                         (4*8*16)  (3*4*5)
                                                                   (2*3*10)
(End)
30 is not in the sequence even though A045779(30) = 5. As 24 is the smallest k such that A045779(k) = 5 we have a(m) = 24 where m is such that A045779(m) = 5 which turns out to be m = 5 (not every positive integer is in A045779). So a(5) = 24. - _David A. Corneth_, Oct 24 2024

David A. Corneth, Table of n, a(n) for n = 1..953

All terms belong to A025487.
The non-strict version is A045783.
The sorted version is A330997.
Factorizations are A001055 with image A045782 and complement A330976.
Strict factorizations are A045778 with image A045779 and complement A330975.
The least number with exactly n strict factorizations is A330974(n).
Cf. A033833, A318286, A330972, A330973, A330989.

More terms from David A. Corneth, Oct 24 2024

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

Original entry on oeis.org

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

David W. Wilson

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

			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.

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

Cf. A001055, A045779, A045780, A050323. a(p^k) = A000009. a(A002110) = A000110.
Cf. A036469, A114591, A114592, A316441 (Dirichlet inverse).
Cf. A156648 (2*Dgf at s=2), A073017 (2*Dgf at s=3), A258870 (2*Dgf at s=4).
Cf. also A069626 (Number of sets of integers > 1 whose least common multiple is n).
Cf. A287549 (partial sums).

⍝ 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

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

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 *)

v=vector(100,k,k==1); for(n=2,#v, v+=dirmul(v,vector(#v,k,k==n)) ); v /* Max Alekseyev, Jul 16 2014 */

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

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

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

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

Edited by Franklin T. Adams-Watters, Jun 04 2009

A045782 Number of factorizations of n for some n (image of A001055).

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 9, 11, 12, 15, 16, 19, 21, 22, 26, 29, 30, 31, 36, 38, 42, 45, 47, 52, 56, 57, 64, 66, 67, 74, 77, 92, 97, 98, 101, 105, 109, 118, 135, 137, 139, 141, 162, 165, 171, 176, 181, 189, 195, 198, 203, 212, 231, 249, 250, 254, 257, 267, 269, 272, 289

Offset: 1

David W. Wilson

nonn

Also the image of A318284. - Gus Wiseman, Jan 11 2020

Florian Luca, Anirban Mukhopadhyay and Kotyada Srinivas, On the Oppenheim's "factorisatio numerorum" function, arXiv:0807.0986 [math.NT], 2008.

Factorizations are A001055 with image this sequence and complement A330976.
Strict factorizations are A045778 with image A045779 and complement A330975.
The least number with exactly a(n) factorizations is A045783(n).
The least number with exactly n factorizations is A330973(n).
Cf. A002033, A007716, A033833, A318284, A325238, A330935, A330936, A330977, A330989, A330991, A330992, A330997.

terms = 61; m0 = 10^5; dm = 10^4;
f[1, ] = 1; f[n, k_] := f[n, k] = Sum[f[n/d, d], {d, Select[Divisors[n], 1 < # <= k &]}];
Clear[seq]; seq[m_] := seq[m] = Sort[Tally[Table[f[n, n], {n, 1, m}]][[All, 1]]][[1 ;; terms]]; seq[m = m0]; seq[m += dm]; While[Print[m]; seq[m] != seq[m - dm], m += dm];
seq[m] (* Jean-François Alcover, Oct 04 2018 *)

The Luca et al. paper shows that the number of terms with a(n) <= x is x^{ O( log log log x / log log x )}. - N. J. A. Sloane, Jun 12 2009

Name edited by Gus Wiseman, Jan 11 2020

A045783 Least value with A045782(n) factorizations.

Original entry on oeis.org

1, 4, 8, 12, 16, 24, 36, 60, 48, 128, 72, 96, 120, 256, 180, 144, 192, 216, 420, 240, 1024, 384, 288, 360, 2048, 432, 480, 900, 768, 840, 576, 1260, 864, 720, 8192, 960, 1080, 1152, 4620, 1800, 3072, 1680, 1728, 1920, 1440, 32768, 2304, 2592, 6144

Offset: 1

David W. Wilson

nonn

			From _Gus Wiseman_, Jan 11 2020: (Start)
Factorizations of n = 1, 4, 8, 12, 16, 24, 36, 60, 48:
  {}  4    8      12     16       24       36       60       48
      2*2  2*4    2*6    2*8      3*8      4*9      2*30     6*8
           2*2*2  3*4    4*4      4*6      6*6      3*20     2*24
                  2*2*3  2*2*4    2*12     2*18     4*15     3*16
                         2*2*2*2  2*2*6    3*12     5*12     4*12
                                  2*3*4    2*2*9    6*10     2*3*8
                                  2*2*2*3  2*3*6    2*5*6    2*4*6
                                           3*3*4    3*4*5    3*4*4
                                           2*2*3*3  2*2*15   2*2*12
                                                    2*3*10   2*2*2*6
                                                    2*2*3*5  2*2*3*4
                                                             2*2*2*2*3
(End)

Wikipedia, Multiplicative partition
R. E. Canfield, P. Erdős and C. Pomerance, On a Problem of Oppenheim concerning "Factorisatio Numerorum", J. Number Theory 17 (1983), 1-28.

All terms belong to A025487.
The strict version is A045780.
The sorted version is A330972.
Includes all highly factorable numbers A033833.
The least number with exactly n factorizations is A330973(n).
Factorizations are A001055 with image A045782 and complement A330976.
Strict factorizations are A045778 with image A045779 and complement A330975.
Cf. A070175, A318284, A325238, A330974, A330989, A330992, A330998.

A330973 Least positive integer with exactly n factorizations into factors > 1, and 0 if no such number exists.

Original entry on oeis.org

1, 4, 8, 12, 16, 0, 24, 0, 36, 0, 60, 48, 0, 0, 128, 72, 0, 0, 96, 0, 120, 256, 0, 0, 0, 180, 0, 0, 144, 192, 216, 0, 0, 0, 0, 420, 0, 240, 0, 0, 0, 1024, 0, 0, 384, 0, 288, 0, 0, 0, 0, 360, 0, 0, 0, 2048, 432, 0, 0, 0, 0, 0, 0, 480, 0, 900, 768, 0, 0, 0, 0, 0

Offset: 1

Gus Wiseman, Jan 06 2020

nonn

Robert G. Wilson v, Table of n, a(n) for n = 1..10000
R. E. Canfield, P. Erdős and C. Pomerance, On a Problem of Oppenheim concerning "Factorisatio Numerorum", J. Number Theory 17 (1983), 1-28.

All nonzero terms belong to A025487.
Includes all highly factorable numbers A033833.
Factorizations are A001055, with image A045782.
The version without zeros is A045783.
The sorted version is A330972.
The strict version is A330974.
Positions of zeros are A330976.
Cf. A001055, A001222, A002033, A007716, A045778, A045779, A330935, A330992, A330997, A330998, A346426.

nn=10;
fam[n_]:=fam[n]=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[fam[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
nds=Length/@Array[fam[#]&,2^nn];
Table[If[#=={},0,#[[1,1]]]&[Position[nds,i]],{i,nn}]

More terms from Jinyuan Wang, Jul 07 2021

A330976 Numbers that are not the number of factorizations into factors > 1 of any positive integer.

Original entry on oeis.org

6, 8, 10, 13, 14, 17, 18, 20, 23, 24, 25, 27, 28, 32, 33, 34, 35, 37, 39, 40, 41, 43, 44, 46, 48, 49, 50, 51, 53, 54, 55, 58, 59, 60, 61, 62, 63, 65, 68, 69, 70, 71, 72, 73, 75, 76, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 93, 94, 95, 96, 99

Offset: 1

Gus Wiseman, Jan 07 2020

nonn

Warning: I have only confirmed the first eight terms. The rest are derived from A045782. - Gus Wiseman, Jan 07 2020

R. E. Canfield, P. Erdős and C. Pomerance, On a Problem of Oppenheim concerning "Factorisatio Numerorum", J. Number Theory 17 (1983), 1-28.

Complement of A045782.
The strict version is A330975.
Factorizations are A001055, with image A045782.
Strict factorizations are A045778, with image A045779.
The least number with n factorizations is A330973(n).
Cf. A033833, A045779, A045783, A317145, A330935, A330972, A330974, A330977, A330991.

nn=15;
fam[n_]:=fam[n]=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[fam[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
nds=Length/@Array[fam[#]&,2^nn];
Complement[Range[nn],nds]

A330974 Least positive integer with n factorizations into distinct factors > 1, and 0 if no such number exists.

Original entry on oeis.org

1, 6, 12, 64, 24, 256, 48, 512, 60, 96, 0, 2048, 0, 144, 210, 120, 216, 180, 384, 0, 288, 16384, 0, 0, 240, 0, 432, 0, 0, 0, 420, 65536, 1536, 360, 0, 0, 0, 480, 0, 900, 0, 864, 3072, 1152, 0, 1296, 0, 0, 0, 0, 0, 2310, 0, 524288, 6144, 960, 720, 0, 840, 0, 2304

Offset: 1

Gus Wiseman, Jan 06 2020

nonn

All nonzero terms belong to A025487.
Strict factorizations are A045778, with image A045779.
The version with zeros removed is A045780.
The non-strict version is A330973.
Positions of zeros are A330975.
The sorted version is A330997.
Cf. A001055, A001222, A033833, A045782, A045783, A318286, A328966, A330972.

nn=10;
fam[n_]:=fam[n]=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[fam[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
nds=Length/@Array[Select[fam[#],UnsameQ@@#&]&,2^nn];
Table[If[#=={},0,#[[1,1]]]&[Position[nds,i]],{i,nn}]

More terms from Jinyuan Wang, Jul 07 2021

A330997 Sorted list containing the least number with each possible nonzero number of factorizations into distinct factors > 1.

Original entry on oeis.org

1, 6, 12, 24, 48, 60, 64, 96, 120, 144, 180, 210, 216, 240, 256, 288, 360, 384, 420, 432, 480, 512, 720, 840, 864, 900, 960, 1080, 1152, 1260, 1296, 1440, 1536, 1680, 1728, 1800, 2048, 2160, 2304, 2310, 2520, 2592, 2880, 3072, 3360, 3456, 3600, 3840, 4320

Offset: 1

Gus Wiseman, Jan 06 2020

nonn

			The strict factorizations of a(n) for n = 1..9.
  {}  6    12   24     48     60      64     96      120
      2*3  2*6  3*8    6*8    2*30    2*32   2*48    2*60
           3*4  4*6    2*24   3*20    4*16   3*32    3*40
                2*12   3*16   4*15    2*4*8  4*24    4*30
                2*3*4  4*12   5*12           6*16    5*24
                       2*3*8  6*10           8*12    6*20
                       2*4*6  2*5*6          2*6*8   8*15
                              3*4*5          3*4*8   10*12
                              2*3*10         2*3*16  3*5*8
                                             2*4*12  4*5*6
                                                     2*3*20
                                                     2*4*15
                                                     2*5*12
                                                     2*6*10
                                                     3*4*10
                                                     2*3*4*5

All terms belong to A025487.
Strict factorizations are A045778, with image A045779.
The unsorted version is A045780.
The non-strict version is A330972.
The least number with n strict factorizations is A330974.
Cf. A001055, A001222, A033833, A045782, A318286, A325238, A330935, A330973, A330975.

nn=1000;
strfacs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[strfacs[n/d],Min@@#>d&]],{d,Rest[Divisors[n]]}]];
nds=Length/@Array[strfacs,nn];
Table[Position[nds,i][[1,1]],{i,First/@Gather[nds]}]

A330975 Numbers that are not the number of factorizations of n into distinct factors > 1 for any n.

Original entry on oeis.org

11, 13, 20, 23, 24, 26, 28, 29, 30, 35, 36, 37, 39, 41, 45, 47, 48, 49, 50, 51, 53, 58, 60, 62, 63, 65, 66, 68, 69, 71, 72, 73, 75, 77, 78, 79, 81, 82, 84, 85, 86, 87, 90, 92, 94, 95, 96, 97, 98, 99, 101, 102, 103, 105, 106, 107, 108, 109, 113, 114, 115, 118

Offset: 1

Gus Wiseman, Jan 07 2020

nonn

Warning: I have only confirmed the first three terms. The rest are derived from A045779. - Gus Wiseman, Jan 07 2020

R. E. Canfield, P. Erdős and C. Pomerance, On a Problem of Oppenheim concerning "Factorisatio Numerorum", J. Number Theory 17 (1983), 1-28.

Complement of A045779.
The non-strict version is A330976.
Factorizations are A001055, with image A045782, with complement A330976.
Strict factorizations are A045778, with image A045779.
The least positive integer with n strict factorizations is A330974(n).
Cf. A001222, A002033, A025487, A033833, A045780, A045783, A318286, A328966, A330972, A330973, A330997.

nn=20;
fam[n_]:=fam[n]=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[fam[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
nds=Length/@Array[Select[fam[#],UnsameQ@@#&]&,2^nn];
Complement[Range[nn],nds]

A331023 Numerator: factorizations divided by strict factorizations A001055(n)/A045778(n).

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 4, 1, 1, 1, 5, 1, 4, 1, 4, 1, 1, 1, 7, 2, 1, 3, 4, 1, 1, 1, 7, 1, 1, 1, 9, 1, 1, 1, 7, 1, 1, 1, 4, 4, 1, 1, 12, 2, 4, 1, 4, 1, 7, 1, 7, 1, 1, 1, 11, 1, 1, 4, 11, 1, 1, 1, 4, 1, 1, 1, 16, 1, 1, 4, 4, 1, 1, 1, 12, 5, 1, 1, 11, 1, 1, 1, 7, 1, 11, 1, 4, 1, 1, 1, 19, 1, 4, 4, 9, 1, 1, 1, 7, 1

Offset: 1

Gus Wiseman, Jan 08 2020

A factorization of n is a finite, nondecreasing sequence of positive integers > 1 with product n. It is strict if the factors are all different. Factorizations and strict factorizations are counted by A001055 and A045778 respectively.

Antti Karttunen, Table of n, a(n) for n = 1..65537
Index entries for sequences computed from exponents in factorization of n

Positions of 1's are A005117.
Positions of 2's appear to be A001248.
The denominators are A331024.
The rounded quotients are A331048.
The same for integer partitions is A330994.
Cf. A001055, A001222, A002033, A045778, A045779, A045780, A045782, A045783, A325755, A326028, A326622, A328966, A330972, A330977, A330991.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Length[facs[n]]/Length[Select[facs[n],UnsameQ@@#&]],{n,100}]//Numerator

A001055(n, m=n) = if(1==n, 1, my(s=0); fordiv(n, d, if((d>1)&&(d<=m), s += A001055(n/d, d))); (s));
A045778(n, m=n) = ((n<=m) + sumdiv(n, d, if((d>1)&&(d<=m)&&(dA045778(n/d, d-1))));
A331023(n) = numerator(A001055(n)/A045778(n)); \\ Antti Karttunen, May 27 2021

a(2^n) = A330994(n).

More terms from Antti Karttunen, May 27 2021

cp's OEIS Frontend

A045780 Least value with A045779(n) factorizations into distinct factors.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

APL

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

Extensions

A045782 Number of factorizations of n for some n (image of A001055).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A045783 Least value with A045782(n) factorizations.

Views

Author

Keywords

Examples

Links

Crossrefs

A330973 Least positive integer with exactly n factorizations into factors > 1, and 0 if no such number exists.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A330976 Numbers that are not the number of factorizations into factors > 1 of any positive integer.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A330974 Least positive integer with n factorizations into distinct factors > 1, and 0 if no such number exists.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Extensions

A330997 Sorted list containing the least number with each possible nonzero number of factorizations into distinct factors > 1.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A330975 Numbers that are not the number of factorizations of n into distinct factors > 1 for any n.