A133995 -id:A133995 - cp's OEIS frontend

A264441 Length of row n of the irregular triangle A133995 (positive integers <= n which are neither divisors of n nor coprime to n).

1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 3, 1, 5, 4, 4, 1, 7, 1, 7, 6, 9, 1, 9, 3, 11, 6, 11, 1, 15, 1, 11, 10, 15, 8, 16, 1, 17, 12, 17, 1, 23, 1, 19, 16, 21, 1, 23, 5, 25, 16, 23, 1, 29, 12, 25, 18, 27, 1, 33, 1, 29, 22, 26, 14, 39, 1, 31, 22, 39, 1

Offset: 1

Wolfdieter Lang, Jan 16 2016

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

Cf. A000040, A045763, A133995.

seq(max(1, n - numtheory:-tau(n) - numtheory:-phi(n) + 1), n=1..100); # Robert Israel, Jan 28 2016

a[1] = a[4] = 1; a[n_] := If[PrimeQ[n], 1, n + 1 - DivisorSigma[0, n] - EulerPhi[n]]; Array[a, 100] (* Jean-François Alcover, Jan 18 2016 *)

A264441(n) = max(1,n+1-numdiv(n)-eulerphi(n)); \\ Antti Karttunen, Mar 04 2018, after code in A045763.

a(1) = 1, a(4) = 1 and a(n) = 1 if n is a prime (n from A000040) else a(n) = A045763(n).

a(n) = max(1, A045763(n)). - Robert Israel, Jan 28 2016

A045763 Number of numbers "unrelated to n": m < n such that m is neither a divisor of n nor relatively prime to n.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 1, 1, 3, 0, 3, 0, 5, 4, 4, 0, 7, 0, 7, 6, 9, 0, 9, 3, 11, 6, 11, 0, 15, 0, 11, 10, 15, 8, 16, 0, 17, 12, 17, 0, 23, 0, 19, 16, 21, 0, 23, 5, 25, 16, 23, 0, 29, 12, 25, 18, 27, 0, 33, 0, 29, 22, 26, 14, 39, 0, 31, 22, 39, 0, 37, 0, 35, 30, 35, 14, 47, 0, 39, 23, 39, 0, 49

Offset: 1

N. J. A. Sloane

Suggested by Wouter Meeussen.
a(n) = 0 iff n is a prime or 1 or 4. - Robert G. Wilson v, Nov 02 2005
From Farideh Firoozbakht, Dec 23 2014: (Start)
1. a(p^k) = p^(k-1) - k where p is a prime and k is a positive integer. Hence if p is prime then a(p) = 0 which is a result of the previous comment.
2. If n = 2*p or n = 4*p and p is an odd prime then a(n) = phi(n) - 1.
3. If n = 3*p where p is a prime not equal to 3 then a(n) = (1/2)*phi(n). (End)

Michael De Vlieger, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
Martin Beumer, The Arithmetical Function tau_k(N), Amer. Math. Monthly, 69, Oct 1962, p. 780 (a(n)=ksi(N)).

Cf. A000005, A000010, A133995.

A045763 := proc(n)
    n+1-numtheory[tau](n)-numtheory[phi](n) ;
end proc:
seq(A045763(n),n=1..100);# Robert Israel, Dec 23 2014

f[n_] := n + 1 - DivisorSigma[0, n] - EulerPhi[n]; Array[f, 84] (* Robert G. Wilson v *)

a(n)=n+1-numdiv(n)-eulerphi(n) \\ Charles R Greathouse IV, Jul 15 2011

from sympy import divisor_count, totient
def A045763(n): return n+1-divisor_count(n)-totient(n) # Chai Wah Wu, Sep 02 2024

a(n) = n + 1 - d(n) - phi(n), where d(n) is the number of divisors of n and phi is Euler's totient function.
Dirichlet generating function: zeta(s-1) + zeta(s) - zeta(s)^2 - zeta(s-1)/zeta(s). - Robert Israel, Dec 23 2014
a(n) = Sum_{k=1..n} (1 - floor(1/gcd(n,k))) * (ceiling(n/k) - floor(n/k)). - Wesley Ivan Hurt, Jan 06 2024

More terms from Robert G. Wilson v, Nov 02 2005

A272618 Irregular array read by rows: n-th row contains (in ascending order) the nondivisors 1 <= k < n such that all the prime divisors p of k also divide n.

Original entry on oeis.org

0, 0, 0, 0, 0, 4, 0, 0, 0, 4, 8, 0, 8, 9, 0, 4, 8, 9, 0, 0, 4, 8, 12, 16, 0, 8, 16, 9, 4, 8, 16, 0, 9, 16, 18, 0, 4, 8, 16, 0, 8, 16, 0, 4, 8, 9, 12, 16, 18, 20, 24, 25, 27, 0, 0, 9, 27, 4, 8, 16, 32, 25, 8, 16, 24, 27, 32, 0, 4, 8, 16, 32, 9, 27, 16, 25, 32, 0, 4, 8, 9, 12, 16, 18, 24, 27, 28, 32

Offset: 1

Michael De Vlieger, May 03 2016

The k are the "semidivisors" or nondivisor regular numbers of n as counted by A243822(n).
All nonzero terms k are composite and pertain to composite rows n. This is because prime k must either divide or be coprime to n, and k = 1 is both a divisor of and coprime to n.
Row n for prime p contains zero, since numbers 1 <= k < p must either divide or be coprime to prime p.
Row n for prime powers p^e contains zero, since there is only one prime divisor p of p^e and every power 1 <= m <= e of p divides p^e.
Row n = 4 is a special case of composite n that contains zero. This is because 4 is the smallest composite number; there are no composites k < n.
Thus rows n for composite n > 4 contain at least 1 nonzero value.
In base n, 1/a(n) has a terminating expansion with at least 2 places.

			For n = 12, the numbers 1 <= k < n such that the prime divisors p of k also divide n are {2, 3, 4, 6, 8, 9}; {2, 3, 4, 6} divide n = 12, thus row n = 12 is {8, 9}.
n: k
1: 0
2: 0
3: 0
4: 0
5: 0
6: 4
7: 0
8: 0
9: 0
10: 4 8
11: 0
12: 8 9
13: 0
14: 4 8
15: 9
16: 0
17: 0
18: 4 8 12 16
19: 0
20: 8 16

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, pp. 144-145, Theorem 136.

Michael De Vlieger, Table of n, a(n) for n = 1..10814 (rows 1 to 1000, flattened).
M. De Vlieger, Exploring Number Bases as Tools, ACM Inroads, March 2012, Vol. 3, No. 1, pp. 4-12.
M. De Vlieger, Neutral Numbers.
M. De Vlieger, Sequence page.

Union of A027750 and nonzero terms of a(n) = A162306, thus A000005(n) + A243822(n) = A010846(n).

The union of nonzero terms of a(n) and A272619 = A133995, thus A243822(n) + A243823(n) = A045763(n).

Table[With[{r = First /@ FactorInteger@ n}, Select[Range@ n,
And[SubsetQ[r, Map[First, FactorInteger@ #]], ! Divisible[n, #]] &]], {n, 30}] /. {} -> 0 // Flatten (* Michael De Vlieger, May 03 2016 *)

A272619 Irregular array read by rows: n-th row contains (in ascending order) the numbers 1 <= k < n such that at least one prime divisor p of k also divides n and at least one prime divisor q of k is coprime to n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 6, 6, 6, 0, 10, 0, 6, 10, 12, 6, 10, 12, 6, 10, 12, 14, 0, 10, 14, 15, 0, 6, 12, 14, 15, 18, 6, 12, 14, 15, 18, 6, 10, 12, 14, 18, 20, 0, 10, 14, 15, 20, 21, 22, 10, 15, 20, 6, 10, 12, 14, 18, 20, 22, 24, 6, 12, 15, 18, 21, 24, 6, 10, 12, 18, 20, 21, 22, 24, 26, 0, 14, 21, 22

Offset: 1

Michael De Vlieger, May 03 2016

The k are the "semitotatives" of n as counted by A243823(n).
All nonzero terms k are composite and pertain to composite rows n. This is because prime k must either divide or be coprime to n, and k = 1 is both a divisor of and coprime to n. Further, the terms k must have at least two distinct prime divisors p and q.
Row n for prime p contains zero, since numbers 1 <= k < p must either divide or be coprime to prime p.
Row n for prime powers p^e contains all the numbers k in the corresponding row of A133995. There is only one prime divisor p of p^e and every power 1 <= m <= e of p divides p^e, thus none of the terms of the corresponding row of A133995 are in A272618(n).
Rows n = 4 and 6 are special cases of composite n that contains zero. 4 is the smallest composite number; there are no composites k < n. 6 has the prime divisors 2 and 3, thus 5 is the smallest prime coprime to 6; the product of the minimum prime divisor and minimum prime coprime to 6 is 10, which exceeds 6 and falls outside the considered range. The situation is not so for composite n > 6. Thus rows n for composite n > 6 contain at least 1 nonzero value.
The smallest k of row n = A096014(n) < n, i.e., those values of A096014(n) pertaining to composite n > 6, a product of the smallest prime divisor p of n and the smallest prime q coprime to n. The smallest k of n are even squarefree semiprimes since 2 either divides n or is coprime to n and k is by definition a number with at least two distinct primes. The smallest k = 2p for p^2 sets record values for A096014(n) when we ignore values pertaining to prime n, n = 4, and n = 6.
In base n, 1/a(n) has a mixed recurrent expansion.

			For n = 12, the numbers 1 <= k < n such that the prime divisors p of k also divide n are {2, 3, 4, 6, 8, 9}; {2, 3, 4, 6} divide n = 12, thus row n = 12 is {8, 9}.
n:   k
1:   0
2:   0
3:   0
4:   0
5:   0
6:   0
7:   0
8:   6
9:   6
10:  6
11:  0
12: 10
13:  0
14:  6 10 12
15:  6 10 12
16:  6 10 12 14
17:  0
18: 10 14 15
19:  0
20:  6 12 14 15 18

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, pp. 144-5, Theorem 136.

Michael De Vlieger, Table of n, a(n) for n = 1..10447 (rows 1 to 256, flattened).
M. De Vlieger, Exploring Number Bases as Tools, ACM Inroads, March 2012, Vol. 3, No. 1, pp. 4-12.
M. De Vlieger, Neutral Numbers.
M. De Vlieger, Sequence page.

The union of nonzero terms of a(n) and A272618 = A133995, thus A243822(n) + A243823(n) = A045763(n).

Table[With[{r = First /@ FactorInteger@ n}, Select[Range@ n, Function[m, And[! SubsetQ[r, First /@ FactorInteger@ m], 1 < GCD[m, n] < n]]]], {n, 30}] /. {} -> {0} // Flatten (* Michael De Vlieger, May 03 2016 *)

A121998 Table, n-th row gives numbers between 1 and n that have a common factor with n.

Original entry on oeis.org

2, 3, 2, 4, 5, 2, 3, 4, 6, 7, 2, 4, 6, 8, 3, 6, 9, 2, 4, 5, 6, 8, 10, 11, 2, 3, 4, 6, 8, 9, 10, 12, 13, 2, 4, 6, 7, 8, 10, 12, 14, 3, 5, 6, 9, 10, 12, 15, 2, 4, 6, 8, 10, 12, 14, 16, 17, 2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 19, 2, 4, 5, 6, 8, 10, 12, 14, 15, 16, 18, 20, 3, 6, 7, 9, 12, 14, 15

Offset: 2

Franklin T. Adams-Watters, Sep 11 2006

Row n contains numbers m <= n such that gcd(m,n) > 1, i.e., numbers m in the cototient of n. - Michael De Vlieger, Mar 13 2018

			2;
3;
2,4;
5;
2,3,4,6;
7;
...

Michael De Vlieger, Table of n, a(n) for n = 2..12949 (rows 2 <= n <= 256).

Cf. A051953 (row lengths), A038566, A081520, A133995 (nondivisors in the cototient of n).

Table[Select[Range@ n, ! CoprimeQ[#, n] &], {n, 20}] // Flatten (* Michael De Vlieger, Mar 13 2018 *)

A381094 Triangle read by rows where row n contains k < n that are neither coprime to n nor have the same squarefree kernel as n, or 0 if there are no such k.

Original entry on oeis.org

0, 0, 0, 0, 0, 2, 3, 4, 0, 6, 6, 2, 4, 5, 6, 8, 0, 2, 3, 4, 8, 9, 10, 0, 2, 4, 6, 7, 8, 10, 12, 3, 5, 6, 9, 10, 12, 6, 10, 12, 14, 0, 2, 3, 4, 8, 9, 10, 14, 15, 16, 0, 2, 4, 5, 6, 8, 12, 14, 15, 16, 18, 3, 6, 7, 9, 12, 14, 15, 18, 2, 4, 6, 8, 10, 11, 12, 14, 16, 18, 20

Offset: 1

Michael De Vlieger, Feb 14 2025

Let rad(k) = A007947(k), the squarefree kernel of k.
Let T(n) be row n of this sequence and let S(n) be row n of A133995.
T(n) contains numbers k < n such that k and n share at least one prime factor p, but not all distinct prime p | n.
T(n) is a superset of S(n), since S(n) does not contain any divisor d | n, while T(n) allows d | n such that rad(d) != rad(n).

			Table begins:
   n   row n
  ---------------------------
   1:  0;
   2:  0;
   3:  0;
   4:  0;
   5:  0;
   6:  2, 3, 4;
   7:  0;
   8:  6;
   9:  6;
  10:  2, 4, 5, 6, 8;
  11:  0;
  12:  2, 3, 4, 8, 9, 10;
  13:  0;
  14:  2, 4, 6, 7, 8, 10, 12;
  15:  3, 5, 6, 9, 10, 12;
  16:  6, 10, 12, 14;
From _Michael De Vlieger_, Mar 03 2025: (Start)
Row 10 is the union of {2, 4, 6, 8, 10} and {5, 10} without 10.
Row 12 is the union of {2, 4, 6, 8, 10, 12} and {3, 6, 9, 12} without {6, 12}.
Row 30 is the union of {2, 4, ..., 30}, {3, 6, ..., 30}, and {5, 10, ..., 30} without 30.
Row 84 is the union of {2, 4, ..., 84}, {3, 6, ..., 84}, and {7, 14, ..., 84} without {42, 84}, etc. (End)

Michael De Vlieger, Table of n, a(n) for n = 1..11873 (rows n = 1..250, flattened)

Cf. A007947, A121998, A133995, A369609, A381096.

rad[x_] := rad[x] = Times @@ FactorInteger[x][[All, 1]]; Table[r = rad[n]; Select[Range[n], Nor[CoprimeQ[#, n], rad[#] == r] &], {n, 120}]

T(n) = { k < n : 1 < gcd(k,n), rad(k) != rad(n) }.
T(n) = S(n) \ { k : k | n, rad(k) = rad(n) }.
For prime p, T(p) = {}, but we write 0 to signify the empty set.
T(4) = 0, since k < 4 is either coprime to 4 or rad(k) = 2.
Let U(n) be row n of A121998 and let R(n) be row n of A369609. T(n) = U(n) \ R(n). - Michael De Vlieger, Mar 03 2025

A300858 a(n) = A243823(n) - A243822(n).

Original entry on oeis.org

0, 0, 0, 0, 0, -1, 0, 1, 1, -1, 0, -1, 0, 1, 2, 4, 0, -1, 0, 3, 4, 3, 0, 3, 3, 5, 6, 7, 0, -5, 0, 11, 6, 7, 6, 6, 0, 9, 8, 11, 0, 1, 0, 13, 12, 13, 0, 13, 5, 13, 12, 17, 0, 13, 10, 19, 14, 19, 0, 5, 0, 21, 18, 26, 12, 11, 0, 23, 18, 15, 0, 25, 0, 25, 24, 27

Offset: 1

Michael De Vlieger, Mar 14 2018

sign

Consider numbers in the cototient of n, listed in row n of A121998. For composite n > 4, there are nondivisors m in the cototient, listed in row n of A133995. Of these m, there are two species. The first are m that divide n^e with integer e > 1, while the last do not divide n^e. These are listed in row n of A272618 and A272619, and counted by A243822(n) and A243823(n), respectively. This sequence is the difference between the latter and the former species of nondivisors in the cototient of n.
Since A045763(n) = A243822(n) + A243823(n), this sequence examines the balance of the two components among nondivisors in the cototient of n.
For positive n < 6 and for p prime, a(n) = a(p) = 0, thus a(A046022(n)) = 0.
For prime powers p^e, a(p^e) = A243823(p^e), since A243822(p^e) = 0, thus a(n) = A243823(n) for n in A000961.
Value of a(n) is generally nonnegative; a(n) is negative for n = {6, 10, 12, 18, 30}; a(30) = -5, but a(n) = -1 for the rest of the aforementioned numbers. These five numbers are a subset of A295523.

			a(6) = -1 since the only nondivisor in the cototient of 6 is 4, which divides 6^e with e > 1; therefore 0 - 1 = -1.
a(8) = 1 since the only nondivisor in the cototient of 8 is 6, and 6 does not divide 8^e with e > 1, therefore 1 - 0 = 1.
Some values of a(n) and related sequences:
   n  a(n) A243823(n) A243822(n)    A272619(n)       A272618(n)
  -------------------------------------------------------------
   1   0          0          0      -                -
   2   0          0          0      -                -
   3   0          0          0      -                -
   4   0          0          0      -                -
   5   0          0          0      -                -
   6  -1          0          1      -                {4}
   7   0          0          0      -                -
   8   1          1          0      {6}              -
   9   1          1          0      {6}              -
  10  -1          1          2      {6}              {4,8}
  11   0          0          0      -                -
  12  -1          1          2      {10}             {8,9}
  13   0          0          0      -                -
  14   1          3          2      {6,10,12}        {4,8}
  15   2          3          1      {6,10,12}        {9}
  16   4          4          0      {6,10,12,14}     -
  17   0          0          0      -                -
  18  -1          3          4      {10,14,15}       {4,8,12,16}
  19   0          0          0      -                -
  20   3          5          2      {6,12,14,15,18}  {8,16}
  ...

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

Cf. A000005, A000010, A000961, A010846, A046022, A121998, A133995, A173540, A243822, A243823, A272618, A272619, A295523, A300859, A300861.

f[n_] := Count[Range@ n, _?(PowerMod[n, Floor@ Log2@ n, #] == 0 &)]; Array[#1 - #3 + 1 - 2 #2 + #4 & @@ {#, f@ #, EulerPhi@ #, DivisorSigma[0, #]} &, 76]

a(n) = 1 + n + numdiv(n) - eulerphi(n) - 2*sum(k=1, n, if(gcd(n,k)-1, 0, moebius(k)*(n\k))); \\ Michel Marcus, Mar 17 2018

a(n) = 1 + n - A000010(n) - 2*A010846(n) + A000005(n).

A376281 Number of pairs (d, k/d), d | k, d < k/d, such that gcd(d, k/d) is not in {1, d, k/d}, where k is in A379336.

Original entry on oeis.org

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

Offset: 1

Michael De Vlieger, Jan 08 2025

nonn

Number of ways to write k = A379336(n) as a product of numbers i and j that are neither coprime nor does one number divide the other. Both i and j are necessarily composite.

Both i and j = k/i appear in row k of A133995.

			Let s(n) = A379336(n).
a(1) = 1 since s(1) = 24 = 4*6.
a(2) = 1 since s(2) = 40 = 4*10.
a(3) = 1 since s(3) = 48 = 6*8.
a(12) = 2 since s(12) = 96 = 6*16 = 8*12.
a(16) = 3 since s(16) = 120 = 4*30 = 6*20 = 10*12.
a(44) = 4 since s(44) = 240 = 6*40 = 8*30 = 10*24 = 12*20.
a(75) = 5 since s(75) = 360 = 4*90 = 10*36 = 12*30 = 15*24 = 18*20.
a(105) = 6 since s(105) = 480 = 6*80 = 8*60 = 10*48 = 12*40 = 16*30 = 20*24, etc.

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

Cf. A045763, A133995, A379336, A379552, A379752, A379772.

nn = 500; mm = Floor@ Sqrt[nn]; p = 2; q = 3;
s = Complement[
  Select[Range[nn],
    And[#2 > #1 > 1, #2 > 3] & @@ {PrimeNu[#], PrimeOmega[#]} &],
  Union[Reap[
    While[p <= mm, q = NextPrime[p];
      While[p*q <= mm, If[p != q, Sow[p*q]]; q = NextPrime[q]];
        p = NextPrime[p]] ][[-1, 1]] ]^2 ];
Table[k = s[[n]];
  1/2*DivisorSum[k, 1 &, ! MemberQ[{1, #1, #2}, GCD[#1, #2]] & @@ {#, k/#} &],
  {n, Length[s]}]

A070251 Unrelated-factorial numbers: product of numbers unrelated to n (numbers which have a common divisor with n but do not divide n).

Original entry on oeis.org

1, 1, 1, 1, 1, 4, 1, 6, 6, 192, 1, 720, 1, 23040, 6480, 10080, 1, 12902400, 1, 34836480, 2449440, 1857945600, 1, 50295168000, 3000, 980995276800, 9797760, 9564703948800, 1, 1518492398911488000, 1, 41845579776000, 1571364748800

Offset: 1

Amarnath Murthy, May 05 2002

nonn

a(p) = 1 if p is a prime. 4 is the only composite number such that a(4) = 1.
From Michael De Vlieger, Jan 15 2025: (Start)
Conjecture: a(n) is in A055932, and also often in A025487.
Conjectures: a(6) = 4 is likely the only powerful term that exceeds 1. a(8) = a(9) = 6 is likely the only squarefree number exceeding 1 that appears in the sequence.
Conjecture: For n = 2*p, p > 3, gcd(n, a(n)) > 1, rad(n) does not divide a(n), and rad(a(n)) does not divide n, since gpf(n) does not divide a(n). For composite n > 9 not an even squarefree semiprime, n divides a(n). (End)

			Table of a(n) for composite n <= 30, showing prime power decomposition by listing exponents of primes shown in the column heads:
   n                   a(n)   2  3  5  7 11 13
  ---------------------------------------------
   6                     4    2
   8                     6    1, 1
   9                     6    1, 1
  10                   192    6, 1
  12                   720    4, 2, 1
  14                 23040    9, 2, 1
  15                  6480    4, 4, 1
  16                 10080    5, 2, 1, 1
  18              12902400   13, 2, 2, 1
  20              34836480   12, 5, 1, 1
  21               2449440    5, 7, 1, 1
  22            1857945600   17, 4, 2, 1
  24           50295168000   10, 6, 3, 2, 1
  25                  3000    3, 1, 3
  26          980995276800   21, 5, 2, 1, 1
  27               9797760    7, 7, 1, 1
  28         9564703948800   19, 6, 2, 1, 1, 1
  30   1518492398911488000   22,10, 3, 3, 1, 1

Michael De Vlieger, Table of n, a(n) for n = 1..629
Michael De Vlieger, Log log scatterplot of log_10(a(n)), n = 1..10000, where gold represents proper prime power n, green represents squarefree composite n, bright green represents n in A002110, blue represents n in A332785, and purple represents powerful n that are not prime powers.
Michael De Vlieger, Plot p^m | a(n) at (x,y) = (n, pi(p)), n = 1..2048, with a color function showing m = 1 in black, m = 2 in red, ..., maximum m in magenta.

Cf. A045763, A066760, A133995.

A070251 := proc(n) local i;
remove(k->igcd(n,k)=1,{$1..n}); numtheory[divisors](n);
mul(i, i = %% minus % ) end:   # Peter Luschny, Oct 11 2011

a[n_] := Times @@ Complement[Range[n], Divisors[n]]/Times @@ Select[ Range[n], CoprimeQ[n, #]&];
Array[a, 33] (* Jean-François Alcover, Jun 03 2019 *)

a(n) = A055067(n)/A001783(n). - Vladeta Jovovic, May 06 2002
From Michael De Vlieger, Jan 15 2025: (Start)
Let S(n) = { k < n : 1 < gcd(k,n) < k } = row n of A133995 for composite n > 4.
a(n) = product of S(n).
pi(gpf(a(n))) <= pi(n/lpf(n)), i.e., A000720(A006530(a(n))) <= A000720(n/A020639(n)). (End)

More terms from Vladeta Jovovic, May 06 2002

A160995 The smallest positive integer neither a divisor of n nor coprime to n.

Original entry on oeis.org

4, 6, 6, 10, 4, 14, 6, 6, 4, 22, 8, 26, 4, 6, 6, 34, 4, 38, 6, 6, 4, 46, 9, 10, 4, 6, 6, 58, 4, 62, 6, 6, 4, 10, 8, 74, 4, 6, 6, 82, 4, 86, 6, 6, 4, 94, 9, 14, 4, 6, 6, 106, 4, 10, 6, 6, 4, 118, 8, 122, 4, 6, 6, 10, 4, 134, 6, 6, 4, 142, 10, 146, 4, 6, 6, 14, 4, 158, 6, 6, 4, 166, 8, 10, 4, 6

Offset: 2

Leroy Quet, Jun 01 2009

nonn

a(1) doesn't exist because 1 is coprime to all integers.

Terms are composite since primes either divide or are coprime to other numbers. - Michael De Vlieger, Feb 20 2025

			From _David James Sycamore_, Feb 28 2025: (Start)
Using my formula above: n = 4235 = 5*7*11^2, so a(n) = 2*5 = 10.
For n = odd prime p, a(n) = 2*p.
For n = 2, a(n) = min{2^2, 2*3} = 4.
For n = 4, a(n) = min{2^3, 2*3} = 6. (For all n = 2^k, k >= 2, a(n) = 6.)
For n = 120 = 2^3*3*5, a(n) = min{16, 9, 25, 14} = 9.
For n = 5040 = 2^4*3^2*5*7, a(n) = min{32, 27, 25, 49, 22} = 22.
For n = 3603600 = 2^4*3^2*5^2*7*11*13, a(n) = min{32,27,125,49,121,169,34} = 27. (End)

Charles R Greathouse IV, Table of n, a(n) for n = 2..10000

Cf. A001221, A020639, A053669, A096014, A100484, A133995, A135718.

Table[k = 3; Until[1 < GCD[k, n] < k, k++]; k, {n, 2, 120}] (* Michael De Vlieger, Feb 20 2025 *)

a(n)=for(k=4,2*n,if(gcd(n,k)>1 && n%k, return(k))) \\ Charles R Greathouse IV, Apr 05 2013

a(n)=my(f=factor(n),b);forprime(p=2,,if(n%p,b=p*f[1,1];break));for(i=1,#f[,1],b=min(b,f[i,1]^(f[i,2]+1)));b \\ Charles R Greathouse IV, Apr 05 2013

For composite n > 4, a(n) is the first term of row n of A133995. - Michael De Vlieger, Feb 20 2025
For even n whose prime factorization is Product_{i=1..k} (p_i)^(e_i), a(n) = min({p_i^(e_i + 1) : i = 1..k} U {2*q}), where q = A053669(n); for odd n, a(n) = 2*A020639(n); see Example. - David James Sycamore, Feb 28 2025 [edited by Peter Munn, Jul 20 2025]
a(n) = min(A096014(n), A135718(n)). - Michael De Vlieger, Feb 24 2025

Extended by Ray Chandler, Jun 13 2009

cp's OEIS Frontend

A264441 Length of row n of the irregular triangle A133995 (positive integers <= n which are neither divisors of n nor coprime to n).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A045763 Number of numbers "unrelated to n": m < n such that m is neither a divisor of n nor relatively prime to n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A272618 Irregular array read by rows: n-th row contains (in ascending order) the nondivisors 1 <= k < n such that all the prime divisors p of k also divide n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

A272619 Irregular array read by rows: n-th row contains (in ascending order) the numbers 1 <= k < n such that at least one prime divisor p of k also divides n and at least one prime divisor q of k is coprime to n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

A121998 Table, n-th row gives numbers between 1 and n that have a common factor with n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A381094 Triangle read by rows where row n contains k < n that are neither coprime to n nor have the same squarefree kernel as n, or 0 if there are no such k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A300858 a(n) = A243823(n) - A243822(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI