A381803 Number of residues r in {0..n-1} that are not coprime to n and not in row n of A381801.

0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 3, 0, 4, 0, 1, 0, 4, 1, 0, 0, 6, 3, 0, 6, 8, 0, 4, 0, 11, 5, 8, 0, 9, 0, 0, 10, 13, 0, 7, 0, 9, 7, 11, 0, 17, 5, 3, 0, 12, 0, 6, 8, 21, 1, 0, 0, 17, 0, 25, 15, 26, 8, 15, 0, 24, 11, 12, 0, 29, 0, 0, 7, 17, 3, 22, 0, 32, 23

Offset: 1

Author

Michael De Vlieger, Mar 24 2025

Keywords

• nonn

Comments

The intersection of row n of A038566 and row n of A381801 is {1} for n > 1. Therefore most of the terms in row n of A381801 are in row n of A121998 (reading n itself in row n of A121998 instead as n mod n = 0). Thus, a(n) is the number of terms n that are in row n of A121998 but not in A381801.

Examples

			Let R(n) = row n of A381801 and let S(n) = row n of A121998, where n in S(n) is instead taken mod n.
a(2) = 0 since S(2) = {} and R(2) = {0, 1}; R(2) \ S(2) is empty.
a(4) = 0 since S(4) = {0, 2} and R(4) = {0, 1, 2}; R(4) \ S(4) is empty.
a(6) = 0 since S(6) = {0, 2, 3, 4} and R(6) = {0, 1, 2, 3, 4} is empty.
a(8) = 1 since S(8) = {0, 2, 4, 6} and R(8) = {0, 1, 2, 4} = {6}.
a(9) = 1 since S(9) = {0, 3, 6} and R(6) = {0, 1, 3} = {6}.
a(10) = 0 since S(10) = {0, 2, 4, 5, 6, 8} and R(10) = {0, 1, 2, 4, 5, 6, 8} is empty.
  Therefore in base 10, numbers k such that rad(k) | 10 (i.e., k in A003592) may end in any number that is not coprime to 10. (Except 1 ends in the digit one, which is coprime to 10).
a(12) = 1 since S(12) = {0, 2, 3, 4, 6, 8, 9, 10} and R(12) = {0, 1, 2, 3, 4, 6, 8, 9} = {10}.
  Therefore in base 12, numbers k such that rad(k) | 12 (i.e., k in A003586) never end in digit 10.
a(14) = 3 since S(14) = {0, 2, 4, 6, 7, 8, 10, 12} and R(14) = {0, 1, 2, 4, 7, 8} = {6, 10, 12}.
  Therefore in base 14, numbers k such that rad(k) | 14 (i.e., k in A003591) never end in digits 6, 10, or 12.
a(16) = 4 since S(16) = {0, 2, 4, 6, 8, 10, 12, 14} and R(14) = {0, 1, 2, 4, 8} = {6, 10, 12, 14}, etc.
  Therefore in hexadecimal, numbers k such that powers of 2 (i.e., A000079) never end in digits 6, 10, 12, or 14.
		

Links

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

Crossrefs

Cf. A000010, A038566, A051953, A121998, A381800, A381802.

Programs

Mathematica

f[x_] := Block[{c, ff, m, r, p, s, w},
  c[_] := True; ff = FactorInteger[x][[All, 1]]; w = Length[ff];
  s = {1};
  Do[Set[p[i], ff[[i]]], {i, w}];
  Do[Set[s, Union@ Flatten@ Join[s, #[[-1, 1]]]] &@ Reap@
    Do[m = s[[j]];
      While[Sow@ Set[r, Mod[m*p[i], x]];
        c[r],
        c[r] = False;
        m *= p[i]],
       {j, Length[s]}],
    {i, w}]; s ];
{0}~Join~Table[1 + n - EulerPhi[n] - Length@ f[n], {n, 2, 120}]

Formula

a(n) = 1 + n - phi(n) - A381800(n)

= 1 + n - A000010(n) - A381800(n)

= 1 + A051953(n) - A381800(n)

= A381802(n) - phi(n) - 1.

a(p) = 0.

a(p^m) = p^(m-1) - m.