A056170 -id:A056170 - cp's OEIS frontend

A081386 Number of unitary prime divisors of central binomial coefficient, C(2n,n) = A000984(n), i.e., number of those prime factors in C(2n,n), whose exponent equals one.

1, 2, 1, 3, 1, 3, 3, 4, 4, 4, 5, 5, 4, 3, 5, 7, 6, 7, 7, 8, 9, 9, 6, 7, 7, 7, 8, 11, 12, 11, 11, 11, 12, 12, 12, 13, 13, 13, 11, 13, 12, 14, 13, 13, 15, 14, 14, 14, 15, 16, 16, 16, 17, 19, 18, 17, 18, 19, 18, 19, 18, 18, 18, 20, 18, 21, 22, 20, 20, 20, 20, 20, 20, 19, 21, 21, 24, 23

Offset: 1

Labos Elemer, Mar 27 2003

nonn

			n=10: C(20,10) = 184756 = 2*2*11*13*17*19; unitary-p-divisors = {11,13,17,19}, so a(10)=4.

T. D. Noe, Table of n, a(n) for n=1..2000

Cf. A000984, A067434, A081387-A081389, A034444, A048105, A056170, A056169.

Table[Function[m, Count[Divisors@ m, k_ /; And[PrimeQ@ k, GCD[k, m/k] == 1]]]@ Binomial[2 n, n], {n, 50}] (* Michael De Vlieger, Dec 17 2016 *)

a(n) = my(f=factor(binomial(2*n, n))); sum(k=1, #f~, f[k,2] == 1); \\ Michel Marcus, Dec 18 2016

a(n) = A056169(A000984(n)).

A290095 a(n) = A275725(A060126(n)); prime factorization encodings of cycle-polynomials computed for finite permutations listed in reversed colexicographic ordering.

Original entry on oeis.org

2, 4, 18, 8, 8, 12, 150, 100, 54, 16, 16, 24, 54, 16, 90, 40, 36, 16, 16, 24, 40, 60, 16, 36, 1470, 980, 882, 392, 392, 588, 750, 500, 162, 32, 32, 48, 162, 32, 270, 80, 108, 32, 32, 48, 80, 120, 32, 72, 750, 500, 162, 32, 32, 48, 1050, 700, 378, 112, 112, 168, 450, 200, 162, 32, 32, 72, 200, 300, 32, 48, 108, 32, 162, 32, 270, 80, 108, 32, 378, 112, 630, 280

Offset: 0

Antti Karttunen, Aug 17 2017

nonn

In this context "cycle-polynomials" are single-variable polynomials where the coefficients (encoded with the exponents of prime factorization of n) are equal to the lengths of cycles in the permutation listed with index n in table A055089 (A195663). See the examples.

			Consider the first eight permutations (indices 0-7) listed in A055089:
  1 [Only the first 1-cycle explicitly listed thus a(0) = 2^1 = 2]
  2,1 [One transposition (2-cycle) in beginning, thus a(1) = 2^2 = 4]
  1,3,2 [One fixed element in beginning, then transposition, thus a(2) = 2^1 * 3^2 = 18]
  3,1,2 [One 3-cycle, thus a(3) = 2^3 = 8]
  2,3,1 [One 3-cycle, thus a(4) = 2^3 = 8]
  3,2,1 [One transposition jumping over a fixed element, a(5) = 2^2 * 3^1 = 12]
  1,2,4,3 [Two 1-cycles, then a 2-cycle, thus a(6) = 2^1 * 3^1 * 5^2 = 150].
  2,1,4,3 [Two 2-cycles, not crossed, thus a(7) = 2^2 * 5^2 = 100].

Antti Karttunen, Table of n, a(n) for n = 0..40319
Index entries for sequences related to factorial base representation

Cf. A055090, A055091, A055092, A055093, A060126, A290096, A290097.

Cf. also A275725, A275734, A275735, A276076 and tables A055089, A195663.

a(n) = A275725(A060126(n)).
Other identities:
A046523(a(n)) = A290096(n).
A056170(a(n)) = A055090(n).
A046660(a(n)) = A055091(n).
A072411(a(n)) = A055092(n).
A275812(a(n)) = A055093(n).

A318720 Numbers k such that there exists a strict relatively prime factorization of k in which no pair of factors is relatively prime.

Original entry on oeis.org

900, 1764, 1800, 2700, 3528, 3600, 4356, 4500, 4900, 5292, 5400, 6084, 6300, 7056, 7200, 8100, 8712, 8820, 9000, 9800, 9900, 10404, 10584, 10800, 11025, 11700, 12100, 12168, 12348, 12600, 12996, 13068, 13500, 14112, 14400, 14700, 15300, 15876, 16200, 16900

Offset: 1

Gus Wiseman, Sep 02 2018

nonn

From Amiram Eldar, Nov 01 2020: (Start)
Also, numbers with more than two non-unitary prime divisors, i.e., numbers k such that A056170(k) > 2, or equivalently, numbers divisible by the squares of three distinct primes.
The complement of the union of A005117, A190641 and A338539.
The asymptotic density of this sequence is 1 - 6/Pi^2 - (6/Pi^2)*A154945 - (3/Pi^2)*(A154945^2 - A324833) = 0.0033907041... (End)

			900 is in the sequence because the factorization 900 = (6*10*15) is relatively prime (since the GCD of (6,10,15) is 1) but each of the pairs (6,10), (6,15), (10,15) has a common divisor > 1. Larger examples are:
1800 = (6*15*20) = (10*12*15).
9900 = (6*10*165) = (6*15*110) = (10*15*66).
5400 = (6*20*45) = (10*12*45) = (10*15*36) = (15*18*20).
60 is not in the sequence because all its possible factorizations (4 * 15, 3 * 4 * 5, etc.) contain at least one pair that is coprime, if not more than one prime.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A001055, A001221, A001222, A007716, A045778, A051185, A078374, A281116, A303140, A303283, A305843, A305854, A317748, A318715, A318717, A318721.

Cf. A005117, A036785, A056170, A154945, A190641, A324833, A338539.

strfacs[n_] := If[n <= 1, {{}}, Join@@Table[(Prepend[#1, d] &)/@Select[strfacs[n/d], Min@@#1 > d &], {d, Rest[Divisors[n]]}]]; Select[Range[10000], Function[n, Select[strfacs[n], And[GCD@@# == 1, And@@(GCD[##] > 1 &)@@@Select[Tuples[#, 2], Less@@# &]] &] != {}]]
Select[Range[20000], Count[FactorInteger[#][[;;,2]], ?(#1 > 1 &)] > 2 &] (* _Amiram Eldar, Nov 01 2020 *)

A338539 Numbers having exactly two non-unitary prime factors.

Original entry on oeis.org

36, 72, 100, 108, 144, 180, 196, 200, 216, 225, 252, 288, 300, 324, 360, 392, 396, 400, 432, 441, 450, 468, 484, 500, 504, 540, 576, 588, 600, 612, 648, 675, 676, 684, 700, 720, 756, 784, 792, 800, 828, 864, 882, 936, 968, 972, 980, 1000, 1008, 1044, 1080, 1089

Offset: 1

Amiram Eldar, Nov 01 2020

nonn

Numbers k such that A056170(k) = A001221(A057521(k)) = 2.
Numbers divisible by the squares of exactly two distinct primes.
Subsequence of A036785 and first differs from it at n = 44.
The asymptotic density of this sequence is (3/Pi^2)*(eta_1^2 - eta_2) = 0.0532928864..., where eta_j = Sum_{p prime} 1/(p^2-1)^j (Pomerance and Schinzel, 2011).

			36 = 2^2 * 3^2 is a term since it has exactly 2 prime factors, 2 and 3, that are non-unitary.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Carl Pomerance and Andrzej Schinzel, Multiplicative Properties of Sets of Residues, Moscow Journal of Combinatorics and Number Theory, Vol. 1, No. 1 (2011), pp. 52-66. See pp. 61-62.

Subsequence of A013929 and A036785.
Cf. A001221, A056170, A057521, A190641, A338540, A338541, A338542, A347892 (subsequence).
Cf. A154945 (eta_1), A324833 (eta_2).

Select[Range[1000], Count[FactorInteger[#][[;;,2]], _?(#1 > 1 &)] == 2 &]

A367096 Irregular triangle read by rows where row n lists the semiprime divisors of n. Alternatively, row n lists the semiprime divisors of A002808(n).

Original entry on oeis.org

4, 6, 4, 9, 10, 4, 6, 14, 15, 4, 6, 9, 4, 10, 21, 22, 4, 6, 25, 26, 9, 4, 14, 6, 10, 15, 4, 33, 34, 35, 4, 6, 9, 38, 39, 4, 10, 6, 14, 21, 4, 22, 9, 15, 46, 4, 6, 49, 10, 25, 51, 4, 26, 6, 9, 55, 4, 14, 57, 58, 4, 6, 10, 15, 62, 9, 21, 4, 65, 6, 22, 33, 4, 34

Offset: 1

Gus Wiseman, Nov 08 2023

On the first interpretation, the first three rows are empty. On the second, the first row is (4).

			The semiprime divisors of 30 are {6,10,15}, so row 30 is (6,10,15). Without empty rows, this is row 19.
Triangle begins (empty rows indicated by dots):
   1: .
   2: .
   3: .
   4: 4
   5: .
   6: 6
   7: .
   8: 4
   9: 9
  10: 10
  11: .
  12: 4,6
Without empty rows:
   1: 4
   2: 6
   3: 4
   4: 9
   5: 10
   6: 4,6
   7: 14
   8: 15
   9: 4
  10: 6,9
  11: 4,10
  12: 21

For all divisors we have A027750.
Square terms are counted by A056170.
Row sums are A076290.
Squarefree terms are counted by A079275.
Row lengths are A086971, firsts A220264.
A000005 counts divisors.
A001222 counts prime factors (or prime indices), distinct A001221.
A001358 lists semiprimes, squarefree A006881, complement A100959.
Cf. A008967, A365829, A366738, A366739, A366740, A367093, A367098.

Table[Select[Divisors[n],PrimeOmega[#]==2&],{n,100}]

row(n) = select(x -> bigomega(x) == 2, divisors(n)); \\ Amiram Eldar, May 02 2025

A063956 Sum of unitary prime divisors of n.

Original entry on oeis.org

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

Offset: 1

Labos Elemer, Sep 04 2001

			The prime divisors of 420 = 2^2 * 3 * 5 * 7. Among them, those that have exponent 1 (i.e., unitary prime divisors) are {3, 5, 7}, so a(420) = 3 + 5 + 7 = 15.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Harry J. Smith)

Cf. A008472, A034387, A034444, A056169, A056170, A056171, A056172, A063958.

Table[DivisorSum[n, # &, And[PrimeQ@ #, GCD[#, n/#] == 1] &], {n, 81}] (* Michael De Vlieger, Feb 17 2019 *)
f[p_, e_] := If[e == 1, p, 0]; a[1] = 0; a[n_] := Plus @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Jul 24 2024 *)
Join[{0},Table[Total[Select[FactorInteger[n],#[[2]]==1&][[;;,1]]],{n,2,100}]] (* Harvey P. Dale, Jan 26 2025 *)

{ for (n=1, 1000, f=factor(n)~; a=0; for (i=1, length(f), if (f[2, i]==1, a+=f[1, i])); write("b063956.txt", n, " ", a) ) } \\ Harry J. Smith, Sep 04 2009

a(n*m) = a(n) + a(m) - a(gcd(n^2, m)) - a(gcd(n, m^2)) for all n and m > 0 (conjecture). - Velin Yanev, Feb 17 2019
From Amiram Eldar, Jul 24 2024: (Start)
a(n) = A008472(n) - A063958(n).
Additive with a(p^e) = p is e = 1, and 0 otherwise. (End)

Example clarified by Harvey P. Dale, Jan 26 2025

A063958 Sum of the non-unitary prime divisors of n: sum of those prime divisors for which the exponent in the prime factorization exceeds 1.

Original entry on oeis.org

0, 0, 0, 2, 0, 0, 0, 2, 3, 0, 0, 2, 0, 0, 0, 2, 0, 3, 0, 2, 0, 0, 0, 2, 5, 0, 3, 2, 0, 0, 0, 2, 0, 0, 0, 5, 0, 0, 0, 2, 0, 0, 0, 2, 3, 0, 0, 2, 7, 5, 0, 2, 0, 3, 0, 2, 0, 0, 0, 2, 0, 0, 3, 2, 0, 0, 0, 2, 0, 0, 0, 5, 0, 0, 5, 2, 0, 0, 0, 2, 3, 0, 0, 2, 0, 0, 0, 2, 0, 3, 0, 2, 0, 0, 0, 2, 0, 7, 3, 7, 0, 0, 0, 2, 0

Offset: 1

Labos Elemer, Sep 04 2001

Alois P. Heinz, Table of n, a(n) for n = 1..20000 (first 1000 terms from Harry J. Smith)

Cf. A034444, A048105, A056169, A056170, A063956.

Cf. A007947 (rad), A008472 (sopf).

a:= proc(n) option remember; add(`if`(i[2]>1, i[1], 0), i=ifactors(n)[2]) end:
seq(a(n), n=1..100);  # Alois P. Heinz, Jun 24 2018

Array[Total@ Select[FactorInteger@ #, Last@ # > 1 &][[All, 1]] &, 105] (* Michael De Vlieger, Dec 06 2018 *)

{ for (n=1, 1000, f=factor(n)~; a=0; for (i=1, length(f), if (f[2, i]>1, a+=f[1, i])); write("b063958.txt", n, " ", a) ) } \\ Harry J. Smith, Sep 04 2009

G.f.: Sum_{k>=1} prime(k) * x^(prime(k)^2) / (1 - x^(prime(k)^2)). - Ilya Gutkovskiy, Apr 06 2020
a(n) = sopf(rad(n/rad(n))). - Wesley Ivan Hurt, Nov 21 2021
a(n) = Sum_{p^2|n} p. - Wesley Ivan Hurt, Feb 21 2022
From Amiram Eldar, Jul 24 2024: (Start)
a(n) = A008472(n) - A063956(n).
Additive with a(p^e) = p if e >= 2, and 0 otherwise. (End)

A081389 Number of non-unitary prime divisors of Catalan numbers, i.e., number of those prime factors whose exponent is greater than one.

Original entry on oeis.org

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

Offset: 1

Labos Elemer, Mar 27 2003

nonn

			For n=25: Catalan(25) = binomial(50,25)/26 = 4861946401452 =(2*2*3*3*7*7)*29*31*37*41*43*47;
unitary prime divisors: {29,31,37,41,43,47};
non-unitary prime divisors: {2,3,7}, so a(25) = 3.

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A000108, A034444, A048105, A056169, A056170, A080405, A081386, A081387, A081388.

Table[Boole[n == 1] + PrimeNu@ # - Count[Transpose[FactorInteger@ #][[2]], 1] &@ CatalanNumber@ n, {n, 105}] (* Michael De Vlieger, Feb 25 2017, after Harvey P. Dale at A056169 *)

catalan(n) = binomial(2*n, n)/(n+1);
nbud(n) = #select(x->x!=1, factor(n)[,2]);
a(n) = nbud(catalan(n)); \\ Michel Marcus, Feb 26 2017

a(n) = A056170(A000108(n)).

A238949 Degree of divisor lattice D(n).

Original entry on oeis.org

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

Offset: 1

Sung-Hyuk Cha, Mar 07 2014

Antti Karttunen, Table of n, a(n) for n = 1..10000 (terms 1..200 from Sung-Hyuk Cha)
Sung-Hyuk Cha, Edgar G. DuCasse, and Louis V. Quintas, Graph Invariants Based on the Divides Relation and Ordered by Prime Signatures, arXiv:1405.5283 [math.NT], 2014.
Index entries for sequences computed from exponents in factorization of n.

Cf. A001221, A056170, A057427, A077761, A085548.

Prepend[Table[Total[FactorInteger[n][[All, 2]] /. x_ /; x > 1 -> 2], {n, 2, 85}], 0] (* Geoffrey Critzer, Mar 02 2015 *)

a(n) = {my(f = factor(n)); sum(i=1, #f~, 1 + (f[i,2] > 1));} \\ Michel Marcus, Mar 03 2015

(define (A238949 n) (if (= 1 n) 0 (+ 1 (A057427 (+ -1 (A067029 n))) (A238949 (A028234 n))))) ;; Antti Karttunen, Jul 23 2017

a(n) = A001221(n) + A056170(n) as given in the Cha, DuCasse, Quintas reference. - Geoffrey Critzer, Mar 02 2015
Additive with a(p^e) = 1+A057427(e-1). - Antti Karttunen, Jul 23 2017
Sum_{k=1..n} a(k) ~ n * (log(log(n)) + B + C), where B is Mertens's constant (A077761) and C = Sum_{p prime} 1/p^2 (A085548). - Amiram Eldar, Feb 13 2024

More terms from Antti Karttunen, Jul 23 2017

A295666 a(n) = Product_{d|n, gcd(d,n/d) is prime} gcd(d,n/d).

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 4, 3, 1, 1, 4, 1, 1, 1, 4, 1, 9, 1, 4, 1, 1, 1, 16, 5, 1, 9, 4, 1, 1, 1, 4, 1, 1, 1, 36, 1, 1, 1, 16, 1, 1, 1, 4, 9, 1, 1, 16, 7, 25, 1, 4, 1, 81, 1, 16, 1, 1, 1, 16, 1, 1, 9, 4, 1, 1, 1, 4, 1, 1, 1, 144, 1, 1, 25, 4, 1, 1, 1, 16, 9, 1, 1, 16, 1, 1, 1, 16, 1, 81, 1, 4, 1, 1, 1, 16, 1, 49, 9, 100, 1, 1, 1, 16, 1

Offset: 1

Antti Karttunen, Nov 26 2017

nonn

			For n = 12, with divisors 1, 2, 3, 4, 6, 12, we select from the sequence gcd(1,12/1), gcd(2,12/2), gcd(3,12/3), gcd(4,12/4), gcd(6,12/6), gcd(12,12/12) = 1, 2, 1, 1, 2, 1 only those that are primes, namely the two 2's, and form their product, thus a(12) = 2*2 = 4.
For n = 100, with divisors 1, 2, 4, 5, 10, 20, 25, 50, 100, we select from the sequence gcd(1,100/1), gcd(2,100/2), gcd(4,100/4), gcd(5,100/5), gcd(10,100/10), gcd(20,100/20), gcd(25,100/25), gcd(50,100/50), gcd(100,100/100) = 1, 2, 1, 5, 10, 5, 1, 2, 1, only those that are primes, namely 2, 5, 5 and 2, thus a(100) = 2*5*5*2 = 100.

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

Cf. A003557, A056170, A010051, A294876, A294895, A295665.

a[n_]:=Product[GCD[i,n/i]^Boole[PrimeQ[GCD[i,n/i]]],{i,Divisors[n]}]; Array[a,105] (* Stefano Spezia, Feb 20 2024 *)

A295666(n) = { my(m=1,p); fordiv(n, d, p = gcd(d, n/d); if(isprime(p), m *= p)); m; };

a(n) = Product_{d|n} gcd(d,n/d)^A010051(gcd(d,n/d)).
a(n) = A295665(A294876(n)).
Other identities. For all n >= 1:
A001221(a(n)) = A056170(n) = A001221(A003557(n)).

cp's OEIS Frontend

A081386 Number of unitary prime divisors of central binomial coefficient, C(2n,n) = A000984(n), i.e., number of those prime factors in C(2n,n), whose exponent equals one.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A290095 a(n) = A275725(A060126(n)); prime factorization encodings of cycle-polynomials computed for finite permutations listed in reversed colexicographic ordering.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A318720 Numbers k such that there exists a strict relatively prime factorization of k in which no pair of factors is relatively prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A338539 Numbers having exactly two non-unitary prime factors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A367096 Irregular triangle read by rows where row n lists the semiprime divisors of n. Alternatively, row n lists the semiprime divisors of A002808(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

A063956 Sum of unitary prime divisors of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A063958 Sum of the non-unitary prime divisors of n: sum of those prime divisors for which the exponent in the prime factorization exceeds 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A081389 Number of non-unitary prime divisors of Catalan numbers, i.e., number of those prime factors whose exponent is greater than one.

Views

Author

Keywords

Examples

Links