Displaying 1-10 of 18 results found.
Least value with A045779(n) factorizations into distinct factors.
+20
16
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
EXAMPLE
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
CROSSREFS
The least number with exactly n strict factorizations is A330974(n).
Number of factorizations of n into distinct factors greater than 1.
+10
278
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
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
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):
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)
(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
Cf. also A069626 (Number of sets of integers > 1 whose least common multiple is n).
Number of factorizations of n for some n (image of A001055).
+10
33
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
FORMULA
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
MATHEMATICA
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];
CROSSREFS
Factorizations are A001055 with image this sequence and complement A330976. 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.
Least value with A045782(n) factorizations.
+10
28
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
EXAMPLE
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)
CROSSREFS
Includes all highly factorable numbers A033833. The least number with exactly n factorizations is A330973(n).
Least positive integer with exactly n factorizations into factors > 1, and 0 if no such number exists.
+10
26
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
MATHEMATICA
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}]
CROSSREFS
All nonzero terms belong to A025487. Includes all highly factorable numbers A033833. The version without zeros is A045783. Cf. A001055, A001222, A002033, A007716, A045778, A045779, A330935, A330992, A330997, A330998, A346426.
Numbers that are not the number of factorizations into factors > 1 of any positive integer.
+10
23
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
COMMENTS
Warning: I have only confirmed the first eight terms. The rest are derived from A045782. - Gus Wiseman, Jan 07 2020
MATHEMATICA
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]
CROSSREFS
The least number with n factorizations is A330973(n).
Least positive integer with n factorizations into distinct factors > 1, and 0 if no such number exists.
+10
14
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
MATHEMATICA
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}]
CROSSREFS
All nonzero terms belong to A025487. The version with zeros removed is A045780.
Sorted list containing the least number with each possible nonzero number of factorizations into distinct factors > 1.
+10
13
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
EXAMPLE
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
MATHEMATICA
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]}]
CROSSREFS
The least number with n strict factorizations is A330974.
Numbers that are not the number of factorizations of n into distinct factors > 1 for any n.
+10
12
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
COMMENTS
Warning: I have only confirmed the first three terms. The rest are derived from A045779. - Gus Wiseman, Jan 07 2020
MATHEMATICA
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]
CROSSREFS
The least positive integer with n strict factorizations is A330974(n). Cf. A001222, A002033, A025487, A033833, A045780, A045783, A318286, A328966, A330972, A330973, A330997.
Numerator: factorizations divided by strict factorizations A001055(n)/ A045778(n).
+10
9
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
COMMENTS
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.
MATHEMATICA
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
PROG
(PARI)
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)&&(d<n), A045778(n/d, d-1))));
CROSSREFS
Positions of 2's appear to be A001248. The same for integer partitions is A330994. Cf. A001055, A001222, A002033, A045778, A045779, A045780, A045782, A045783, A325755, A326028, A326622, A328966, A330972, A330977, A330991.
Search completed in 0.012 seconds
|