A330935 -id:A330935

A330972

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

+10
38

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

This is the sorted list of positions of first appearances in A001055 of each element of the range (A045782).

LINKS

Table of n, a(n) for n=1..51.

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

EXAMPLE

Factorizations of n for n = 4, 8, 12, 16, 24, 36, 48, 60:

4 8 12 16 24 36 48 60

2*2 2*4 2*6 2*8 3*8 4*9 6*8 2*30

2*2*2 3*4 4*4 4*6 6*6 2*24 3*20

2*2*3 2*2*4 2*12 2*18 3*16 4*15

2*2*2*2 2*2*6 3*12 4*12 5*12

2*3*4 2*2*9 2*3*8 6*10

2*2*2*3 2*3*6 2*4*6 2*5*6

3*3*4 3*4*4 3*4*5

2*2*3*3 2*2*12 2*2*15

2*2*2*6 2*3*10

2*2*3*4 2*2*3*5

2*2*2*2*3

MATHEMATICA

nn=1000;

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

nds=Length/@Array[facs, nn];

Table[Position[nds, i][[1, 1]], {i, First/@Gather[nds]}]

CROSSREFS

All terms belong to A025487

Includes all highly factorable numbers A033833.

Factorizations are A001055, with image A045782.

The least number with A045782(n) factorizations is A045783(n).

The least number with n factorizations is A330973(n).

The strict version is A330997.

Cf. A001222, A002033, A007716, A045778, A318284, A325238, A330935, A330936, A330976, A330977, A330989, A330991, A330992.

KEYWORD

nonn

AUTHOR

Gus Wiseman, Jan 06 2020

STATUS

approved

A045782

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

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

LINKS

Table of n, a(n) for n=1..61.

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

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];

seq[m] (* Jean-François Alcover, Oct 04 2018 *)

CROSSREFS

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.

KEYWORD

nonn

AUTHOR

David W. Wilson

EXTENSIONS

Name edited by Gus Wiseman, Jan 11 2020

STATUS

approved

A330973

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

LINKS

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.

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.

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.

KEYWORD

nonn

AUTHOR

Gus Wiseman, Jan 06 2020

EXTENSIONS

More terms from Jinyuan Wang, Jul 07 2021

STATUS

approved

A330976

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

COMMENTS

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

LINKS

Table of n, a(n) for n=1..65.

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

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

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.

KEYWORD

nonn

AUTHOR

Gus Wiseman, Jan 07 2020

STATUS

approved

A330997

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

LINKS

Table of n, a(n) for n=1..49.

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

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.

KEYWORD

nonn

AUTHOR

Gus Wiseman, Jan 06 2020

STATUS

approved

A330989

Least positive integer with exactly 2^n factorizations into factors > 1, or 0 if no such integer exists.

+10
11

1, 4, 12, 0, 72, 0, 480

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

LINKS

Table of n, a(n) for n=0..6.

EXAMPLE

The A001055(n) factorizations for n = 1, 4, 12, 72:

() (4) (12) (72)

(2*2) (2*6) (8*9)

(3*4) (2*36)

(2*2*3) (3*24)

(4*18)

(6*12)

(2*4*9)

(2*6*6)

(3*3*8)

(3*4*6)

(2*2*18)

(2*3*12)

(2*2*2*9)

(2*2*3*6)

(2*3*3*4)

(2*2*2*3*3)

CROSSREFS

All nonzero terms belong to A025487 and also A033833.

Factorizations are A001055, with image A045782.

The least number with exactly n factorizations is A330973(n).

Numbers whose number of factorizations is a power of 2 are A330977.

The least number with exactly prime(n) factorizations is A330992(n).

Cf. A002033, A045778, A045783, A318284, A330935, A330972, A330976, A330990, A330991, A331022.

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Jan 07 2020

STATUS

approved

A330727

Irregular triangle read by rows where T(n,k) is the number of balanced reduced multisystems of depth k whose degrees (atom multiplicities) are the prime indices of n.

+10
5

1, 1, 1, 1, 2, 1, 3, 2, 1, 3, 1, 7, 7, 1, 5, 5, 1, 5, 9, 5, 1, 9, 11, 1, 9, 28, 36, 16, 1, 10, 24, 16, 1, 14, 38, 27, 1, 13, 18, 1, 13, 69, 160, 164, 61, 1, 24, 79, 62, 1, 20, 160, 580, 1022, 855, 272, 1, 19, 59, 45, 1, 27, 138, 232, 123, 1, 17, 77, 121, 61

(list; graph; refs; listen; history; text; internal format)

OFFSET

2,5

COMMENTS

A balanced reduced multisystem is either a finite multiset, or a multiset partition with at least two parts, not all of which are singletons, of a balanced reduced multisystem.

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798. A multiset whose multiplicities are the prime indices of n (such as row n of A305936) is generally not the same as the multiset of prime indices of n. For example, the prime indices of 12 are {1,1,2}, while a multiset whose multiplicities are {1,1,2} is {1,1,2,3}.

LINKS

Table of n, a(n) for n=2..71.

FORMULA

T(2^n,k) = A008826(n,k).

EXAMPLE

Triangle begins:

{}

1

1 1

1 2

1 3 2

1 3

1 7 7

1 5 5

1 5 9 5

1 9 11

1 9 28 36 16

1 10 24 16

1 14 38 27

1 13 18

1 13 69 160 164 61

1 24 79 62

For example, row n = 12 counts the following multisystems:

{1,1,2,3} {{1},{1,2,3}} {{{1}},{{1},{2,3}}}

{{1,1},{2,3}} {{{1,1}},{{2},{3}}}

{{1,2},{1,3}} {{{1}},{{2},{1,3}}}

{{2},{1,1,3}} {{{1,2}},{{1},{3}}}

{{3},{1,1,2}} {{{1}},{{3},{1,2}}}

{{1},{1},{2,3}} {{{1,3}},{{1},{2}}}

{{1},{2},{1,3}} {{{2}},{{1},{1,3}}}

{{1},{3},{1,2}} {{{2}},{{3},{1,1}}}

{{2},{3},{1,1}} {{{2,3}},{{1},{1}}}

{{{3}},{{1},{1,2}}}

{{{3}},{{2},{1,1}}}

MATHEMATICA

nrmptn[n_]:=Join@@MapIndexed[Table[#2[[1]], {#1}]&, If[n==1, {}, Flatten[Cases[Reverse[FactorInteger[n]], {p_, k_}:>Table[PrimePi[p], {k}]]]]];

sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];

mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];

totm[m_]:=Prepend[Join@@Table[totm[p], {p, Select[mps[m], 1<Length[#]<Length[m]&]}], m];

Table[Length[Select[totm[nrmptn[n]], Depth[#]==k&]], {n, 2, 10}, {k, 2, Length[nrmptn[n]]}]

CROSSREFS

Row sums are A318846.

Final terms in each row are A330728.

Row prime(n) is row n of A330784.

Row 2^n is row n of A008826.

Row n is row A181821(n) of A330667.

Column k = 3 is A318284(n) - 2 for n > 2.

Cf. A000111, A002846, A005121, A292504, A318812, A318813, A318847, A318848, A318849, A330475, A330666, A330935.

KEYWORD

nonn,tabf

AUTHOR

Gus Wiseman, Jan 04 2020

STATUS

approved

A330936

Number of nontrivial factorizations of n into factors > 1.

+10
3

0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 3, 0, 2, 0, 2, 0, 0, 0, 5, 0, 0, 1, 2, 0, 3, 0, 5, 0, 0, 0, 7, 0, 0, 0, 5, 0, 3, 0, 2, 2, 0, 0, 10, 0, 2, 0, 2, 0, 5, 0, 5, 0, 0, 0, 9, 0, 0, 2, 9, 0, 3, 0, 2, 0, 3, 0, 14, 0, 0, 2, 2, 0, 3, 0, 10, 3, 0, 0, 9, 0, 0

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,12

COMMENTS

The trivial factorizations of a number are (1) the case with only one factor, and (2) the factorization into prime numbers.

LINKS

Table of n, a(n) for n=1..86.

FORMULA

For prime n, a(n) = 0; for nonprime n, a(n) = A001055(n) - 2.

EXAMPLE

The a(n) nontrivial factorizations of n = 8, 12, 16, 24, 36, 48, 60, 72:

(2*4) (2*6) (2*8) (3*8) (4*9) (6*8) (2*30) (8*9)

(3*4) (4*4) (4*6) (6*6) (2*24) (3*20) (2*36)

(2*2*4) (2*12) (2*18) (3*16) (4*15) (3*24)

(2*2*6) (3*12) (4*12) (5*12) (4*18)

(2*3*4) (2*2*9) (2*3*8) (6*10) (6*12)

(2*3*6) (2*4*6) (2*5*6) (2*4*9)

(3*3*4) (3*4*4) (3*4*5) (2*6*6)

(2*2*12) (2*2*15) (3*3*8)

(2*2*2*6) (2*3*10) (3*4*6)

(2*2*3*4) (2*2*18)

(2*3*12)

(2*2*2*9)

(2*2*3*6)

(2*3*3*4)

MATHEMATICA

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

Table[Length[DeleteCases[Rest[facs[n]], {_}]], {n, 100}]

CROSSREFS

Positions of nonzero terms are A033942.

Positions of 1's are A030078.

Positions of 2's are A054753.

Nontrivial integer partitions are A007042.

Nontrivial set partitions are A008827.

Nontrivial divisors are A070824.

Cf. A001055, A003238, A005121, A317145, A317176, A318812, A330665, A330935.

KEYWORD

nonn

AUTHOR

Gus Wiseman, Jan 04 2020

STATUS

approved

A330785

Triangle read by rows where T(n,k) is the number of chains of length k from minimum to maximum in the poset of integer partitions of n ordered by refinement.

+10
1

1, 0, 1, 0, 1, 1, 0, 1, 3, 2, 0, 1, 5, 8, 4, 0, 1, 9, 25, 28, 11, 0, 1, 13, 57, 111, 99, 33, 0, 1, 20, 129, 379, 561, 408, 116, 0, 1, 28, 253, 1057, 2332, 2805, 1739, 435, 0, 1, 40, 496, 2833, 8695, 15271, 15373, 8253, 1832, 0, 1, 54, 898, 6824, 28071, 67790, 98946, 85870, 40789, 8167

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,9

LINKS

Table of n, a(n) for n=1..66.

FORMULA

T(n,k) = A330935(2^n,k).

EXAMPLE

Triangle begins:

1

0 1

0 1 1

0 1 3 2

0 1 5 8 4

0 1 9 25 28 11

0 1 13 57 111 99 33

0 1 20 129 379 561 408 116

Row n = 5 counts the following chains (minimum and maximum not shown):

() (14) (113)->(14) (1112)->(113)->(14)

(23) (113)->(23) (1112)->(113)->(23)

(113) (122)->(14) (1112)->(122)->(14)

(122) (122)->(23) (1112)->(122)->(23)

(1112) (1112)->(14)

(1112)->(23)

(1112)->(113)

(1112)->(122)

MATHEMATICA

sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];

mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];

upr[q_]:=Union[Sort/@Apply[Plus, mps[q], {2}]];

paths[eds_, start_, end_]:=If[start==end, Prepend[#, {}], #]&[Join@@Table[Prepend[#, e]&/@paths[eds, Last[e], end], {e, Select[eds, First[#]==start&]}]];

Table[Length[Select[paths[Join@@Table[{y, #}&/@DeleteCases[upr[y], y], {y, Sort/@IntegerPartitions[n]}], ConstantArray[1, n], {n}], Length[#]==k-1&]], {n, 8}, {k, n}]

CROSSREFS

Row sums are A213427.

Main diagonal is A002846.

Column k=3 is A007042.

Dominated by A330784.

The version for set partitions is A008826.

The version for factorizations is A330935.

Cf. A000111, A000258, A000311, A005121, A141268, A196545, A265947, A300383, A306186, A317141, A317176, A318813, A320160, A330679.

KEYWORD

nonn,tabl

AUTHOR

Gus Wiseman, Jan 03 2020

STATUS

approved

A320167

Regular triangle where T(n,k) = Sum (-1)^i, where the sum is over all factorizations of n into i factors that are all > 1 and <= k.

+10
0

1, 0, -1, 0, 0, -1, 0, 1, 1, 0, 0, 0, 0, 0, -1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, -1, 0, -1, -1, 0, 0, 0, 0, -1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, -1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1

LINKS

Table of n, a(n) for n=1..84.

FORMULA

T(1,k) = 1, T(n,k) = -Sum_{d|n, 1 < d <= k} T(n/d,d).

EXAMPLE

Triangle begins:

1

0 -1

0 0 -1

0 1 1 0

0 0 0 0 -1

0 0 1 1 1 0

0 0 0 0 0 0 -1

0 -1 -1 0 0 0 0 -1

0 0 1 1 1 1 1 1 0

0 0 0 0 1 1 1 1 1 0

0 0 0 0 0 0 0 0 0 0 -1

0 0 -1 0 0 1 1 1 1 1 1 0

0 0 0 0 0 0 0 0 0 0 0 0 -1

0 0 0 0 0 0 1 1 1 1 1 1 1 0

0 0 0 0 1 1 1 1 1 1 1 1 1 1 0

0 1 1 1 1 1 1 2 2 2 2 2 2 2 2 1

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1

0 0 -1 -1 -1 0 0 0 1 1 1 1 1 1 1 1 1 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1

0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0

MATHEMATICA

u[n_, k_]:=If[n==1, 1, -Sum[u[n/d, d], {d, Select[Rest[Divisors[n]], #<=k&]}]]

Table[u[n, k], {n, 20}, {k, n}]

CROSSREFS

Cf. A001055, A045778, A066032, A114592, A162247, A316441, A319237, A319238, A320835, A320836.

Cf. A195017, A281118, A317145, A317176, A330935.

KEYWORD

sign,tabl

AUTHOR

Gus Wiseman, Oct 22 2018

STATUS

approved