A033273 -id:A033273 - cp's OEIS frontend

A347709 Number of distinct rational numbers of the form x * z / y for some factorization x * y * z = n, 1 < x <= y <= z.

0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 2, 0, 0, 1, 1, 0, 1, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 1, 0, 1, 1, 0, 0, 3, 0, 1, 0, 1, 0, 1, 0, 2, 0, 0, 0, 4, 0, 0, 1, 2, 0, 1, 0, 1, 0, 1, 0, 4, 0, 0, 1, 1, 0, 1, 0, 3, 1, 0, 0, 4, 0, 0, 0, 2, 0, 2, 0, 1, 0, 0, 0, 4, 0, 1, 1, 2, 0, 1, 0, 2, 1, 0, 0, 4, 0, 1, 0, 3, 0, 1, 0, 1, 1, 0, 0, 5

Offset: 1

Gus Wiseman, Oct 14 2021

nonn

This is also the number of distinct possible alternating products of length-3 factorizations of n, where we define the alternating product of a sequence (y_1,...,y_k) to be Product_i y_i^((-1)^(i-1)), and where a factorization of n is a weakly increasing sequence of positive integers > 1 with product n.

			Representative factorizations for each of the a(360) = 9 alternating products:
   (2,2,90) -> 90
   (2,3,60) -> 40
   (2,4,45) -> 45/2
   (2,5,36) -> 72/5
   (2,6,30) -> 10
   (2,9,20) -> 40/9
  (2,10,18) -> 18/5
  (2,12,15) -> 5/2
   (3,8,15) -> 45/8

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

Allowing factorizations of any length <= 3 gives A033273.
Positions of positive terms are A033942.
Positions of 0's are A037143.
The length-2 version is A072670.
Allowing any length gives A347460, reverse A038548.
Allowing any odd length gives A347708.
A001055 counts factorizations (strict A045778, ordered A074206).
A122179 counts length-3 factorizations.
A292886 counts knapsack factorizations, by sum A293627.
A301957 counts distinct subset-products of prime indices.
A304792 counts distinct subset-sums of partitions, positive A276024.
Cf. A000040, A001358, A002033, A046951, A339846, A339890, A347437, A347438, A347439, A347440, A347442, A347456, A347461.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
altprod[q_]:=Product[q[[i]]^(-1)^(i-1),{i,Length[q]}];
Table[Length[Union[altprod/@Select[facs[n],Length[#]==3&]]],{n,100}]

A347709(n) = { my(rats=List([])); fordiv(n,z,my(yx=n/z); fordiv(yx, y, my(x = yx/y); if((y <= z) && (x <= y) && (x > 1), listput(rats,x*z/y)))); #Set(rats); }; \\ Antti Karttunen, Jan 29 2025

More terms from Antti Karttunen, Jan 29 2025

A386992 Irregular triangle read by rows: T(n,k) is the number of nonprimes in the k-th 2-dense sublist of divisors of n, with n >= 1, k >= 1.

Original entry on oeis.org

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

Offset: 1

Omar E. Pol, Aug 23 2025

In a sublist of divisors of n the terms are in increasing order and two adjacent terms are the same two adjacent terms in the list of divisors of n.
The 2-dense sublists of divisors of n are the maximal sublists whose terms increase by a factor of at most 2.
It is conjectured that row lengths are given by A237271.

			Triangle begins:
  1;
  1;
  1, 0;
  2;
  1, 0;
  2;
  1, 0;
  3;
  1, 0, 1;
  1, 1;
  1, 0;
  4;
  1, 0;
  1, 1;
  1, 0, 1;
  ...
For n = 10 the list of divisors of 10 is [1, 2, 5, 10]. There are two 2-dense sublists of divisors of 10, they are [1, 2] and [5, 10]. There is a nonprime number in each sublist, so row 10 is [1, 1].
For n = 15 the list of divisors of 15 is [1, 3, 5, 15]. There are three 2-dense sublists of divisors of 15, they are [1], [3, 5], [15]. Only the first and the third sublists contain nonprimes, so row 15 is [1, 0, 1].

Paolo Xausa, Table of n, a(n) for n = 1..10607 (rows 1..3500 of triangle, flattened).

Row sums give A033273.

Cf. A018252, A174973 (2-dense numbers), A237271, A379288, A384149, A384222, A384225, A384226, A384928, A384930, A384931, A386984, A386993, A387030.

A386992row[n_] := Map[Count[#, _?(!PrimeQ[#] &)] &, Split[Divisors[n], #2 <= 2*# &]];
Array[A386992row, 50] (* Paolo Xausa, Aug 28 2025 *)

T(n,k) = A384222(n,k) - A387030(n,k).

A033272 Number of odd nonprimes dividing n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 1, 4, 1, 1, 1, 2, 2, 2, 1, 1, 3, 2, 1, 2, 1, 1, 2, 1, 1, 4, 1, 2, 2, 1, 1, 2, 2, 1, 2, 1, 1, 4, 1, 2, 2, 1, 1

Offset: 1

N. J. A. Sloane

nonn

G. C. Greubel, Table of n, a(n) for n = 1..1000

Cf. A001227 (with odd divisors), A005087, A033273 (with nonprime divisors).

Table[Length[Select[Divisors[n],OddQ[#]&&!PrimeQ[#]&]],{n,80}] (* Harvey P. Dale, May 06 2012 *)
a[n_] := DivisorSigma[0, n/2^IntegerExponent[n, 2]] - PrimeNu[n] + If[OddQ[n], 0, 1]; Array[a, 100] (* Amiram Eldar, Jul 01 2022 *)

a(n) = sumdiv(n, d, (d%2) && !isprime(d)); \\ Michel Marcus, May 05 2017

a(n) = A001227(n) - A005087(n). - Amiram Eldar, Jul 01 2022

A279455 Numbers n such that the number of nonprime divisors of n divides n.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 10, 11, 12, 13, 14, 16, 17, 19, 20, 22, 23, 24, 26, 27, 28, 29, 30, 31, 34, 37, 38, 41, 43, 44, 46, 47, 48, 52, 53, 54, 58, 59, 61, 62, 67, 68, 70, 71, 73, 74, 76, 79, 80, 82, 83, 86, 89, 90, 92, 94, 97, 101, 103, 105, 106, 107, 109, 110, 112, 113, 116, 118

Offset: 1

Ilya Gutkovskiy, Dec 12 2016

Numbers n such that A033273(n) divides n.
Fixed points of lcm(n, tau(n)-omega(n)), where tau(n) is the number of divisors of n (A000005) and omega(n) is the number of distinct primes dividing n (A001221).
All primes (A000040) are included in the sequence.
All even semiprimes (A100484) are included in the sequence.

			12 is in the sequence because 12 has 6 divisors {1,2,3,4,6,12} out of which 4 are nonprimes {1,4,6,12} and 4 divides 12.

G. C. Greubel, Table of n, a(n) for n = 1..5000

Cf. A000005, A000040, A001221, A033950, A033273, A054010, A075592.

Select[Range[150], Divisible[#1, DivisorSigma[0, #1] - PrimeNu[#1]] & ]

isok(n) = denominator(n/sumdiv(n, d, !isprime(d))) == 1; \\ Michel Marcus, Dec 17 2016

A327402 Quotient of n over the maximum stable divisor of n.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Sep 15 2019

nonn

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 number is stable if its distinct prime indices are pairwise indivisible. Stable numbers are listed in A316476.

			The stable divisors of 60 are {1, 2, 3, 4, 5, 15}, so a(60) = 60/15 = 4.

Antti Karttunen, Table of n, a(n) for n = 1..20000
Gus Wiseman, Sequences counting and encoding certain classes of multisets
Index entries for sequences related to prime indices in the factorization of n.

See link for additional cross-references.

Cf. A000005, A033273, A303362, A316476, A327403, A378442.

stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Table[n/Max[Select[Divisors[n],stableQ[PrimePi/@First/@FactorInteger[#],Divisible]&]],{n,100}]

A378442(n)={my(v=apply(primepi, factor(n)[, 1])); for(j=2, #v, for(i=1, j-1, if(v[j]%v[i]==0, return(0)))); 1}; \\ From the function "ok" in A316476 by Andrew Howroyd, Aug 26 2018
A327402(n) = fordiv(n,d,if(A378442(n/d),return(d))); \\ Antti Karttunen, Jan 28 2025

a(n) = n/A327393(n).

Data section extended to a(105) by Antti Karttunen, Jan 28 2025

A167688 Number of ways of factoring n with all factors greater than 1 (a(1)=1 by convention) minus number of nonprime divisors of n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 2, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 4, 1, 0, 0, 2, 0, 0, 0, 1, 0, 2, 0, 0, 0, 0, 0, 9, 0, 0, 0, 2, 0, 0, 0, 1, 0

Offset: 1

Juri-Stepan Gerasimov, Nov 09 2009

nonn

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

Cf. A001055, A033273.

c[1, r_] := c[1, r] = 1; c[n_, r_] := c[n, r] = Module[{d, i}, d = Select[Divisors@ n, 1 < # <= r &]; Sum[c[n/d[[i]], d[[i]]], {i, 1, Length@ d}]]; Array[c[#, #] - DivisorSum[#, 1 &, ! PrimeQ@ # &] &, 105] (* Michael De Vlieger, Jul 12 2017, after Dean Hickerson at A001055 *)

fcnt(n, m) = {local(s); s=0; if(n == 1, s=1, fordiv(n, d, if((d > 1) && (d <= m), s=s+fcnt(n/d, d)))); s};
A001055(n) = fcnt(n, n); \\ This function from Michael B. Porter, Oct 29 2009
A167688(n) = A001055(n) - (numdiv(n) - omega(n)); \\ Antti Karttunen, Jul 12 2017

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

a(64) and a(80) corrected by R. J. Mathar, May 30 2010

A279436 Number of nonprimes less than or equal to n that do not divide n.

Original entry on oeis.org

0, 0, 0, 0, 1, 1, 2, 1, 3, 4, 5, 3, 6, 6, 7, 6, 9, 7, 10, 8, 11, 12, 13, 9, 14, 15, 15, 15, 18, 15, 19, 16, 20, 21, 22, 18, 24, 24, 25, 22, 27, 24, 28, 26, 27, 30, 31, 25, 32, 31, 34, 33, 36, 32, 37, 34, 39, 40, 41, 34, 42, 42, 41, 40, 45, 43, 47, 45, 48, 46, 50, 42, 51, 51, 50, 51, 54, 52, 56, 50, 55, 58, 59, 52, 60, 61, 62, 59, 64, 57, 65, 64, 67, 68, 69, 62, 71, 69, 70, 68

Offset: 1

Ilya Gutkovskiy, Dec 12 2016

nonn

			a(10) = 4 because 10 has 4 divisors {1,2,5,10} therefore 6 non-divisors {3,4,6,7,8,9} out of which 4 are nonprimes {4,6,8,9}.

G. C. Greubel, Table of n, a(n) for n = 1..5000

Cf. A000005, A000040, A000720, A001221, A014689, A033273, A048865, A049820, A062298, A065890, A082514, A229109.

Table[n - PrimePi[n] - DivisorSigma[0, n] + PrimeNu[n], {n, 1, 100}]

for(n=1,50, print1(n - primepi(n) - numdiv(n) + omega(n), ", ")) \\ G. C. Greubel, May 22 2017

first(n)=my(v=vector(n),pp); forfactored(k=1,n, if(k[2][,2]==[1]~, pp++); v[k[1]]=k[1] - pp - numdiv(k) + omega(k)); v \\ Charles R Greathouse IV, May 23 2017

from sympy import primepi, divisor_count, primefactors
def a(n): return 0 if n==1 else n - primepi(n) - divisor_count(n) + len(primefactors(n)) # Indranil Ghosh, May 23 2017

G.f.: A(x) = B(x) + C(x) - D(x), where B(x) = Sum_{k>=1} x^(2*k+1)/((1 - x^k)*(1 - x^(k+1))), C(x) = Sum_{k>=1} x^prime(k)/(1 - x^prime(k)), D(x) = Sum_{k>=1} x^prime(k)/(1 - x).
a(n) = n - A000720(n) - A000005(n) + A001221(n).
a(n) = A062298(n) - A033273(n).
a(n) = A049820(n) - A048865(n).
a(n) = A229109(n) - A082514(n).
a(A000040(n)) = A065890(n).
a(A000040(n)) + 1 = A014689(n).
A000040(n) - a(A000040(n)) = n + 1.

A287661 Smallest odd number with exactly n nonprime divisors.

Original entry on oeis.org

1, 9, 27, 45, 105, 135, 225, 405, 315, 675, 177147, 1155, 945, 3375, 1575, 6075, 2835, 10125, 18225, 3465, 4725, 30375, 50625, 11025, 25515, 91125, 14175, 10395, 23625, 273375, 1476225, 17325, 33075, 759375, 50031545098999707, 31185, 70875, 1366875, 127575

Offset: 1

Ilya Gutkovskiy, May 29 2017

nonn

			a(5) = 105 because 105 has 8 divisors {1, 3, 5, 7, 15, 21, 35, 105} among which 5 are nonprime {1, 15, 21, 35, 105} and 105 is the smallest odd with exactly 5 nonprime divisors.

Giovanni Resta, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Divisor

Cf. A001221, A002110, A003680, A005179, A033273, A038547, A055079, A070826.

A033273(a(n)) = n.

a(35)-a(39) from Giovanni Resta, May 31 2017

A380447 Number of primes dividing n plus n times the number of nonprimes dividing n.

Original entry on oeis.org

1, 3, 4, 9, 6, 14, 8, 25, 19, 22, 12, 50, 14, 30, 32, 65, 18, 74, 20, 82, 44, 46, 24, 146, 51, 54, 82, 114, 30, 153, 32, 161, 68, 70, 72, 254, 38, 78, 80, 242, 42, 213, 44, 178, 182, 94, 48, 386, 99, 202, 104, 210, 54, 326, 112, 338, 116, 118, 60, 543, 62, 126, 254, 385, 132, 333, 68, 274, 140, 353, 72, 722, 74, 150, 302, 306, 156, 393, 80, 642, 325, 166

Offset: 1

Wesley Ivan Hurt, Jun 21 2025

For each divisor d of n, add 1 if d is prime, else add n.

Inverse Möbius transform of A385313(n).

			12 has 2 prime divisors and 4 nonprime divisors, so a(12) = (2) + 12*(4) = 50.

Cf. A000005 (tau), A001221 (omega), A005171, A033273.

Table[n*DivisorSigma[0, n] - (n - 1) PrimeNu[n], {n, 100}]

a(n) = n*tau(n) - (n-1)*omega(n).
a(n) = Sum_{d|n} n^c(d), where c = A005171.
a(n) = Sum_{d|n} A385313(d).
a(p^k) = 1 + k*p^k for p prime and k>=1. - Wesley Ivan Hurt, Jul 02 2025
a(n) = A001221(n) - n*A033273(n). - Wesley Ivan Hurt, Aug 31 2025

A380449 Sum of the divisors of n plus the number of nonprime divisors of n.

Original entry on oeis.org

2, 4, 5, 9, 7, 14, 9, 18, 15, 20, 13, 32, 15, 26, 26, 35, 19, 43, 21, 46, 34, 38, 25, 66, 33, 44, 43, 60, 31, 77, 33, 68, 50, 56, 50, 98, 39, 62, 58, 96, 43, 101, 45, 88, 82, 74, 49, 132, 59, 97, 74, 102, 55, 126, 74, 126, 82, 92, 61, 177, 63, 98, 108, 133, 86, 149, 69, 130, 98, 149, 73, 205, 75, 116, 128, 144, 98, 173, 81, 194, 125, 128, 85, 233, 110, 134, 122

Offset: 1

Wesley Ivan Hurt, Jun 21 2025

Inverse Möbius transform of A113636(n).

For each divisor d of n, add d if d is prime, else add d+1.

			The sum of the divisors of 12 = 1+2+3+4+6+12 = 28 and 12 has 4 nonprime divisors, so a(12) = 28 + 4 = 32.

Cf. A000005 (tau), A000203 (sigma), A001221 (omega), A033273, A113636.

Table[DivisorSigma[0, n] - PrimeNu[n] + DivisorSigma[1, n], {n, 100}]

a(n) = sigma(n) + tau(n) - omega(n).
a(n) = Sum_{d|n} A113636(d).
a(n) = A000203(n) + A033273(n).
a(p^k) = k + (p^(k+1)-1)/(p-1), p prime, k >= 1. - Wesley Ivan Hurt, Jul 02 2025

cp's OEIS Frontend

A347709 Number of distinct rational numbers of the form x * z / y for some factorization x * y * z = n, 1 < x <= y <= z.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A386992 Irregular triangle read by rows: T(n,k) is the number of nonprimes in the k-th 2-dense sublist of divisors of n, with n >= 1, k >= 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A033272 Number of odd nonprimes dividing n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A279455 Numbers n such that the number of nonprime divisors of n divides n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A327402 Quotient of n over the maximum stable divisor of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A167688 Number of ways of factoring n with all factors greater than 1 (a(1)=1 by convention) minus number of nonprime divisors of n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A279436 Number of nonprimes less than or equal to n that do not divide n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI