A162247 -id:A162247 - cp's OEIS frontend

A316978 Number of factorizations of n into factors > 1 with no equivalent primes.

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, 7, 1, 1, 1, 7, 1, 1, 1, 4, 4, 1, 1, 12, 2, 4, 1, 4, 1, 7, 1, 7, 1, 1, 1, 7, 1, 1, 4, 11, 1, 1, 1, 4, 1, 1, 1, 16, 1, 1, 4, 4, 1, 1, 1, 12, 5, 1, 1, 7, 1, 1

Offset: 1

Gus Wiseman, Jul 18 2018

nonn

In a factorization, two primes are equivalent if each factor has in its prime factorization the same multiplicity of both primes.

			The a(36) = 7 factorizations are (2*2*3*3), (2*2*9), (2*3*6), (3*3*4), (2*18), (3*12), (4*9). Missing from this list are (6*6) and (36).

Cf. A001055, A007716, A007717, A020555, A045778, A162247, A281116, A303386.

Cf. A316974, A316979, A316980, A316981.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
Table[Length[Select[facs[n],UnsameQ@@dual[primeMS/@#]&]],{n,100}]

a(prime^n) = A000041(n).

a(squarefree) = 1.

A319057 Minimum sum of a strict factorization of n into factors > 1.

Original entry on oeis.org

0, 2, 3, 4, 5, 5, 7, 6, 9, 7, 11, 7, 13, 9, 8, 10, 17, 9, 19, 9, 10, 13, 23, 9, 25, 15, 12, 11, 29, 10, 31, 12, 14, 19, 12, 11, 37, 21, 16, 11, 41, 12, 43, 15, 14, 25, 47, 12, 49, 15, 20, 17, 53, 14, 16, 13, 22, 31, 59, 12, 61, 33, 16, 14, 18, 16, 67, 21, 26

Offset: 1

Gus Wiseman, Sep 09 2018

nonn

a(n) >= A001414(n), with equality iff n is squarefree or four times a squarefree number (i.e., A000188(n) <= 2). - Charlie Neder, Sep 10 2018

			The strict factorizations of 48 are (48), (2*24), (3*16), (4*12), (6*8), (2*3*8), (2*4*6), with sums 48, 26, 19, 16, 14, 13, 12 respectively, so a(48) = 12.

Charlie Neder, Table of n, a(n) for n = 1..1000

Cf. A001055, A007716, A045778, A056239, A162247, A215366, A246868, A318871, A318953, A318954.

strfacs[n_]:=If[n<=1,{{}},Join@@Table[(Prepend[#,d]&)/@Select[strfacs[n/d],Min@@#>d&],{d,Rest[Divisors[n]]}]];
Table[Min[Total/@strfacs[n]],{n,100}]

A317145 Number of maximal chains of factorizations of n into factors > 1, ordered by refinement.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 1, 5, 1, 1, 1, 2, 1, 3, 1, 4, 1, 1, 1, 7, 1, 1, 1, 5, 1, 3, 1, 2, 2, 1, 1, 15, 1, 2, 1, 2, 1, 5, 1, 5, 1, 1, 1, 11, 1, 1, 2, 11, 1, 3, 1, 2, 1, 3, 1, 26, 1, 1, 2, 2, 1, 3, 1, 15, 2, 1, 1, 11, 1, 1, 1, 5, 1, 11, 1, 2, 1, 1, 1, 52, 1, 2, 2, 7, 1, 3, 1, 5, 3

Offset: 1

Gus Wiseman, Jul 22 2018

nonn

If x and y are factorizations of the same integer and it is possible to produce x by further factoring the factors of y, flattening, and sorting, then x <= y.

a(n) depends only on prime signature of n (cf. A025487). - Antti Karttunen, Oct 08 2018

			The a(36) = 7 maximal chains:
  (2*2*3*3) < (2*2*9) < (2*18) < (36)
  (2*2*3*3) < (2*2*9) < (4*9)  < (36)
  (2*2*3*3) < (2*3*6) < (2*18) < (36)
  (2*2*3*3) < (2*3*6) < (3*12) < (36)
  (2*2*3*3) < (2*3*6) < (6*6)  < (36)
  (2*2*3*3) < (3*3*4) < (3*12) < (36)
  (2*2*3*3) < (3*3*4) < (4*9)  < (36)

Antti Karttunen, Table of n, a(n) for n = 1..11520
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..100000
Index entries for sequences computed from exponents in factorization of n

Cf. A001055, A002846, A007716, A045778, A064988, A162247, A213427, A275024, A281113, A299202, A300385, A317144, A317146, A320105.

A064988(n) = { my(f = factor(n)); for (k=1, #f~, f[k, 1] = prime(f[k, 1]); ); factorback(f); }; \\ From A064988
memoA320105 = Map();
A320105(n) = if(bigomega(n)<=2,1,if(mapisdefined(memoA320105,n), mapget(memoA320105,n), my(f=factor(n), u = #f~, s = 0); for(i=1,u,for(j=i+(1==f[i,2]),u, s += A320105(prime(primepi(f[i,1])*primepi(f[j,1]))*(n/(f[i,1]*f[j,1]))))); mapput(memoA320105,n,s); (s)));
A317145(n) = A320105(A064988(n)); \\ Antti Karttunen, Oct 08 2018

a(prime^n) = A002846(n).

a(n) = A320105(A064988(n)). - Antti Karttunen, Oct 08 2018

Data section extended to 105 terms by Antti Karttunen, Oct 08 2018

A114592 Sum_{n>=1} a(n)/n^s = Product_{k>=2} (1 - 1/k^s).

Original entry on oeis.org

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

Offset: 1

Leroy Quet, Dec 11 2005

sign

For n >= 2, Sum_{k|n} A001055(n/k) * a(k) = 0. A114591(n) = Sum_{k|n} a(k).

First entry greater than 1 in absolute value is a(360) = -2. - Gus Wiseman, Sep 15 2018

			24 can be factored into distinct integers (each >= 2) as 24; as 4*6, 3*8 and 2*12; and as 2*3*4. (A045778(24) = 5).
So a(24) = (-1)^1 + 3*(-1)^2 + (-1)^3 = 1, where the 1 exponent is due to the 1 factor of the 24 = 24 factorization and the 2 exponent is due to the 3 cases of 2 factors each of the 24 = 4*6 = 3*8 = 2*12 factorizations and the 3 exponent is due to the 24 = 2*3*4 factorization.

Antti Karttunen, Table of n, a(n) for n = 1..10000

Cf. A001055, A045778, A114591.

Cf. A001222, A162247, A190938, A259936, A281116, A303386, A316441, A319237, A319238.

strfacs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[strfacs[n/d],Min@@#>d&]],{d,Rest[Divisors[n]]}]];
Table[Sum[(-1)^Length[f],{f,strfacs[n]}],{n,100}] (* Gus Wiseman, Sep 15 2018 *)

A114592aux(n, k) = if(1==n, 1, sumdiv(n, d, if(d > 1 && d <= k && d < n, (-1)*A114592aux(n/d, d-1))) - (n<=k)); \\ After code in A045778.
A114592(n) = A114592aux(n,n); \\ Antti Karttunen, Jul 23 2017

a(1) = 1; for n>= 2, a(n) = sum, over ways to factor n into any number of distinct integers >= 2, of (-1)^(number of integers in a factorization). (See example.)

More terms from Antti Karttunen, Jul 23 2017

A316441 a(n) = Sum (-1)^k where the sum is over all factorizations of n into factors > 1 and k is the number of factors.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Jul 03 2018

sign

First term greater than 1 in absolute value is a(256) = 2.

			The factorizations of 24 are (2*2*2*3), (2*2*6), (2*3*4), (2*12), (3*8), (4*6), (24); so a(24) = 1 - 2 + 3 - 1 = 1.

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

Cf. A001222, A001055, A045778, A114592, A162247, A190938, A259936, A281116, A303386.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Sum[(-1)^Length[f],{f,facs[n]}],{n,200}]

A316441(n, m=n, k=0) = if(1==n, (-1)^k, my(s=0); fordiv(n, d, if((d>1)&&(d<=m), s += A316441(n/d, d, k+1))); (s)); \\ Antti Karttunen, Sep 08 2018, after Michael B. Porter's code for A001055

Dirichlet g.f.: Product_{n > 1} 1/(1 + 1/n^s).

Secondary offset added by Antti Karttunen, Sep 08 2018

A317144 Number of refinement-ordered pairs of factorizations of n into factors > 1.

Original entry on oeis.org

1, 1, 1, 3, 1, 3, 1, 6, 3, 3, 1, 9, 1, 3, 3, 14, 1, 9, 1, 9, 3, 3, 1, 23, 3, 3, 6, 9, 1, 12, 1, 26, 3, 3, 3, 31, 1, 3, 3, 23, 1, 12, 1, 9, 9, 3, 1, 56, 3, 9, 3, 9, 1, 23, 3, 23, 3, 3, 1, 41, 1, 3, 9, 55, 3, 12, 1, 9, 3, 12, 1, 82, 1, 3, 9, 9, 3, 12, 1, 56, 14

Offset: 1

Gus Wiseman, Jul 22 2018

nonn

If x and y are factorizations of the same integer and it is possible to produce x by further factoring the factors of y, flattening, and sorting, then x <= y.

As this is a sequence computed from exponents in factorization of n, distinct values of a(n) in this sequence can be found by computing a(A025487(k)) for k >= 0. - David A. Corneth, Jul 30 2018

			The a(12) = 9 ordered pairs:
  (2*2*3) <= (12)
  (2*2*3) <= (2*6)
  (2*2*3) <= (3*4)
  (2*2*3) <= (2*2*3)
    (2*6) <= (12)
    (2*6) <= (2*6)
    (3*4) <= (12)
    (3*4) <= (3*4)
     (12) <= (12)

Cf. A000005, A001055, A007716, A025487, A045778, A162247, A281113, A317142, A317145, A317146.

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]]]];
facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
faccaps[fac_]:=Union[Sort/@Apply[Times,mps[fac],{2}]];
Table[Sum[Length[faccaps[fac]],{fac,facs[n]}],{n,100}]

a(n) >= A001055(n) + floor(A000005(n) / 2) - 1. - David A. Corneth, Jul 30 2018

A339564 Number of ways to choose a distinct factor in a factorization of n (pointed factorizations).

Original entry on oeis.org

0, 1, 1, 2, 1, 3, 1, 4, 2, 3, 1, 7, 1, 3, 3, 7, 1, 7, 1, 7, 3, 3, 1, 14, 2, 3, 4, 7, 1, 10, 1, 12, 3, 3, 3, 17, 1, 3, 3, 14, 1, 10, 1, 7, 7, 3, 1, 26, 2, 7, 3, 7, 1, 14, 3, 14, 3, 3, 1, 25, 1, 3, 7, 19, 3, 10, 1, 7, 3, 10, 1, 36, 1, 3, 7, 7, 3, 10, 1, 26, 7, 3

Offset: 1

Gus Wiseman, Apr 10 2021

nonn

			The pointed factorizations of n for n = 2, 4, 6, 8, 12, 24, 30:
  ((2))  ((4))    ((6))    ((8))      ((12))     ((24))       ((30))
         ((2)*2)  ((2)*3)  ((2)*4)    ((2)*6)    ((3)*8)      ((5)*6)
                  (2*(3))  (2*(4))    (2*(6))    (3*(8))      (5*(6))
                           ((2)*2*2)  ((3)*4)    ((4)*6)      ((2)*15)
                                      (3*(4))    (4*(6))      (2*(15))
                                      ((2)*2*3)  ((2)*12)     ((3)*10)
                                      (2*2*(3))  (2*(12))     (3*(10))
                                                 ((2)*2*6)    ((2)*3*5)
                                                 (2*2*(6))    (2*(3)*5)
                                                 ((2)*3*4)    (2*3*(5))
                                                 (2*(3)*4)
                                                 (2*3*(4))
                                                 ((2)*2*2*3)
                                                 (2*2*2*(3))

The additive version is A000070 (strict: A015723).
The unpointed version is A001055 (strict: A045778, ordered: A074206, listed: A162247).
Allowing point (1) gives A057567.
Choosing a position instead of value gives A066637.
The ordered additive version is A336875.
A000005 counts divisors.
A001787 count normal multisets with a selected position.
A001792 counts compositions with a selected position.
A006128 counts partitions with a selected position.
A066186 count strongly normal multisets with a selected position.
A254577 counts ordered factorizations with a selected position.
Cf. A007716, A050336, A281113, A281116, A292886, A293627.

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

a(n) = A057567(n) - A001055(n).

a(n) = Sum_{d|n, d>1} A001055(n/d).

A318871 Minimum Heinz number of a factorization of n into factors > 1.

Original entry on oeis.org

1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 35, 41, 43, 47, 49, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271

Offset: 1

Gus Wiseman, Sep 05 2018

nonn

The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k).

			a(1) = 1 = the empty product.
a(12) = 35 = 5 * 7 = prime(3) * prime(4).
a(16) = 49 = 7^2 = prime(4)^2.
a(23) = 83 = prime(23).

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Cf. A000040, A001055, A007716, A056239, A064988, A162247, A215366, A246868.

a:= proc(n) option remember; `if`(n=1, 1, min(seq(a(d)*
      ithprime(n/d), d=numtheory[divisors](n) minus {n})))
    end:
seq(a(n), n=1..60);  # Alois P. Heinz, Sep 05 2018

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

A301957 Number of distinct subset-products of the integer partition with Heinz number n.

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 2, 1, 3, 2, 2, 2, 2, 2, 4, 1, 2, 3, 2, 2, 4, 2, 2, 2, 3, 2, 4, 2, 2, 4, 2, 1, 4, 2, 4, 3, 2, 2, 4, 2, 2, 4, 2, 2, 6, 2, 2, 2, 3, 3, 4, 2, 2, 4, 4, 2, 4, 2, 2, 4, 2, 2, 5, 1, 4, 4, 2, 2, 4, 4, 2, 3, 2, 2, 6, 2, 4, 4, 2, 2, 5, 2, 2, 4, 4, 2, 4, 2, 2, 6, 4, 2, 4, 2, 4, 2, 2, 3, 6, 3, 2, 4, 2, 2, 8

Offset: 1

Gus Wiseman, Mar 29 2018

nonn

A subset-product of an integer partition y is a product of some submultiset of y. The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

Number of distinct values obtained when A003963 is applied to all divisors of n. - Antti Karttunen, Sep 05 2018

			The distinct subset-products of (4,2,1,1) are 1, 2, 4, and 8, so a(84) = 4.
The distinct subset-products of (6,3,2) are 1, 2, 3, 6, 12, 18, and 36, so a(195) = 7.

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

Cf. A000712, A001055, A001227, A002865, A003963, A108917, A162247, A276024, A292886, A301854, A301855, A301856, A301970, A301979, A304793.

Table[If[n===1,1,Length[Union[Times@@@Subsets[Join@@Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]]]],{n,100}]

up_to = 65537;
A003963(n) = { n=factor(n); n[, 1]=apply(primepi, n[, 1]); factorback(n) }; \\ From A003963
v003963 = vector(up_to,n,A003963(n));
A301957(n) = { my(m=Map(),s,k=0,c); fordiv(n,d,if(!mapisdefined(m,s = v003963[d],&c), mapput(m,s,s); k++)); (k); }; \\ Antti Karttunen, Sep 05 2018

More terms from Antti Karttunen, Sep 05 2018

A250071 Smallest number k such that the symmetric representation of sigma(k) has maximum width n for those k whose representation has nondecreasing width up to the diagonal.

Original entry on oeis.org

1, 6, 72, 120, 5184, 1440, 373248, 6720, 28800, 103680, 1934917632, 80640, 278628139008, 7464960, 2073600, 483840, 1444408272617472, 1612800, 103997395628457984, 5806080, 298598400, 77396705280, 539122498937926189056, 7096320, 1658880000, 5572562780160, 90316800, 418037760, 402452788967166148425547776, 116121600

Offset: 1

Hartmut F. W. Hoft, Nov 11 2014

nonn

The symmetric representation of sigma(k) has nondecreasing width to the diagonal precisely when all odd divisors counted in the k-th row of A237048 occur at odd indices. If we write k = 2^m * q with m >= 0 and q odd, this property is equivalent to q < 2^(m+1).
The values for a(11), a(13), a(17) and a(19) were computed directly using the formula k = 2^m * 3^(p-1) where p is one of the four primes and m the smallest exponent so that 3^(p-1) < 2^(m+1). Each of these numbers has a symmetric representation of nondecreasing width ending in a prime number width, and they are the first such numbers since the number of divisors of an odd number is a prime precisely when the number is a power of a prime.
The other numbers listed whose symmetric representations of sigma(k) have nondecreasing width are smaller than 7500000. The only additional numbers k <= 100000000 are a(24) = 7096320, a(27) = 90316800 and a(32) = 85155840.
See A340506 for another way to look at this data. - N. J. A. Sloane, Jan 23 2021

			a(6) = 1440 = 2^5 * 3^2 * 5 has 6 odd divisors. It is the smallest number of the form 2^m * q with m > 0, q odd and such that q < 2^(m+1).

Cf. A000203, A237048, A237270, A237271, A237593, A241008, A241010, A246955, A247687, A249223, A250068, A250070.
Cf. also A340506.
Cf. A162247.

(* function a2[ ] is defined in A249223 *)
smallQ[n_] := Module[{x=2^IntegerExponent[n,2]}, n/x<2x]
ndWidth[{m_,n_}] := Select[Range[m, n], smallQ]
a250071[x_List] := Module[{i, max, acc={{1, 1}}}, For[i=1, i<=Length[x], i++, max={Max[a2[x[[i]]]], x[[i]]}; If[!MemberQ[Transpose[acc][[1]], max[[1]]], AppendTo[acc, max]]]; acc]
(* returns (argument,result) data pairs since sequence is non-monotonic *)
Sort[a250071[ndWidth[{1,100000000}]]] (* computed in steps *)
(* alternate implementation using function f[ ] by T. D. Noe in A162247 *)
sF[n_] := Min[Map[Apply[Times, Prime[Range[2, Length[#]+1]]^#]&, Map[Reverse[#-1]&, f[n]]]]
f1U[n_] := Module[{s=sF[n], k}, k=Floor[Log[2, s]]; 2^k s]
a250071[n_] := Map[f1U, Range[n]]
a250071[30] (* Hartmut F. W. Hoft, Nov 27 2024 *)

a(n) = min(2^m * q, m >= 0 & q odd & sigma_0(q) = n & q < 2^(m+1)) where sigma_0 is the number of divisors.

a(p) = 2^ceiling((p-1)*(log_2(3)) - 1) * 3^(p-1) for primes p.

a(21)-a(30) from Hartmut F. W. Hoft, Nov 27 2024

cp's OEIS Frontend

A316978 Number of factorizations of n into factors > 1 with no equivalent primes.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A319057 Minimum sum of a strict factorization of n into factors > 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A317145 Number of maximal chains of factorizations of n into factors > 1, ordered by refinement.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A114592 Sum_{n>=1} a(n)/n^s = Product_{k>=2} (1 - 1/k^s).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A316441 a(n) = Sum (-1)^k where the sum is over all factorizations of n into factors > 1 and k is the number of factors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A317144 Number of refinement-ordered pairs of factorizations of n into factors > 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A339564 Number of ways to choose a distinct factor in a factorization of n (pointed factorizations).

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A318871 Minimum Heinz number of a factorization of n into factors > 1.