A381800 -id:A381800 - cp's OEIS frontend

A382138 a(n) = A381800(n) - A381798(n).

0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 2, 0, 1, 1, 0, 0, 3, 0, 2, 1, 1, 0, 4, 0, 1, 0, 2, 0, 8, 0, 0, 1, 1, 1, 5, 0, 1, 1, 3, 0, 10, 0, 2, 3, 1, 0, 6, 0, 5, 1, 2, 0, 9, 1, 4, 1, 1, 0, 16, 0, 1, 2, 0, 1, 14, 0, 2, 1, 12, 0, 8, 0, 1, 5, 2, 1, 16, 0, 5, 0, 1, 0, 19, 1

Offset: 1

Michael De Vlieger, Apr 12 2025

nonn

Number of residue classes r (mod n) of k such that rad(k) | n that are not residue classes q (mod n) of p^m, p | n.

Let S(n) = row n of A381799 and let T(n) = row n of A381801. Let V(n,p) = {p^m mod n : m >= 0}. Then S(n) = U_{p|n} V(n,p).

			    n  a(n)  T(n) \ S(n)
  ----------------------------------------------
    6    1   {0}
   10    1   {0}
   12    2   {0,6}
   18    3   {0,6,12}
   20    2   {0,10}
   24    4   {0,6,12,18}
   28    2   {0,14}
   30    8   {0,6,10,12,15,18,20,24}
   36    5   {0,6,12,18,24}
   72    8   {0,6,12,18,24,36,48,54}
  100    7   {0,10,20,40,50,60,80}
  108   12   {0,6,12,18,24,36,48,54,60,72,84,96}
  144   11   {0,6,12,18,24,36,48,54,72,96,108}
  210   70   {0,6,10,12,14,15,18,20,..,200,204}
.
a(2) = 0 since T(2) = S(2) = V(2,2) = {0,1}.
a(4) = 0 since T(4) = S(4) = V(4,2) = {0,1,2}.
a(6) = 1 since T(6) = {0,1,2,3,4} but S(6) = {1,2,4} U {1,3}.
a(12) = 2 since T(12) = {0,1,2,3,4,6,8,9} but S(12) = {1,2,4,8} U {1,3,9}.
a(16) = 0 since T(16) = S(16) = V(16,2) = {0,1,2,4,8}.
a(18) = 3 since T(18) = {0,1,2,3,4,6,8,9,10,12,14,16} but S(18) = {1,2,4,8,16,14,10} U {1,3,9}. The numbers {0,6,12} do not appear in S(18).
a(30) = 8 since T(30) = {0,1,2,3,4,5,6,8,9,10,12,15,16,18,20,21,24,25,27}, but S(30) = {1,2,4,8,16} U {1,3,9,27,21} U {1,5,25}. The numbers {0,6,12,18,24} do not appear in S(30), etc.

Michael De Vlieger, Table of n, a(n) for n = 1..10000
Michael De Vlieger, Graph of terms k in row n of A381801 not in row n of A381799, n = 1..60.

Cf. A000961, A024619, A381798, A381799, A381800, A381801.

f[x_, p_] := Block[{m = 2, r, c},
  Which[PrimePowerQ[x],
    Join[{0}, #1^Range[0, #2 - 1]] & @@ FactorInteger[x][[1]],
    PowerMod[p, m, x] == p, {1, p}, True, c[_] := False;
  c[1] = c[p] = True; {1, p}~Join~
  Reap[While[r = PowerMod[p, m, x]; ! c[r], Sow[r];
    c[r] = True; m++]][[-1, 1]]]];
g[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}];
    Length[s] ];
{0}~Join~Table[g[n] - CountDistinct@ Flatten@ Map[f[n, #] &, FactorInteger[n][[All, 1]] ], {n, 2, 120}]

a(p^m) = 0 for prime p and m >= 0.

a(n) >= 1 for n in A024619, since residue 0 (mod n) is in T(n) is not in any V(n,p) and thus also not in S(n), because n is not a prime power.

A381801 Irregular triangle read by rows: row n lists the residues r mod n of numbers k such that rad(k) | n, where rad = A007947.

Original entry on oeis.org

0, 0, 1, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 3, 4, 0, 1, 0, 1, 2, 4, 0, 1, 3, 0, 1, 2, 4, 5, 6, 8, 0, 1, 0, 1, 2, 3, 4, 6, 8, 9, 0, 1, 0, 1, 2, 4, 7, 8, 0, 1, 3, 5, 6, 9, 10, 12, 0, 1, 2, 4, 8, 0, 1, 0, 1, 2, 3, 4, 6, 8, 9, 10, 12, 14, 16, 0, 1, 0, 1, 2, 4, 5, 8, 10, 12, 16

Offset: 1

Michael De Vlieger, Mar 07 2025

Define S(p,n) to be the set of residues r (mod n) taken by the power range of prime divisor p, i.e., {p^m, m >= 1}.
Define T(n) to be the union of the tensor product of distinct terms in S(p,n) for all p|n, where the products are expressed mod n.
Row n of this triangle is T(n), a superset of row n of A381799.
For n > 1, the intersection of row n of this triangle and row n of A038566 is {1}.

			Table of c(n) = A381800(n) and T(n) for select n:
 n  c(n)  T(n)
-----------------------------------------------------------------------------
 1    1   {0}
 2    2   {0, 1}
 3    2   {0, 1}
 4    3   {0, 1, 2}
 5    2   {0, 1}
 6    5   {0, 1, 2, 3, 4}
 8    4   {0, 1, 2, 4}
 9    3   {0, 1, 3}
10    7   {0, 1, 2, 4, 5, 6, 8}
11    2   {0, 1}
12    8   {0, 1, 2, 3, 4, 6, 8, 9}
14    6   {0, 1, 2, 4, 7, 8}
15    8   {0, 1, 3, 5, 6, 9, 10, 12}
16    5   {0, 1, 2, 4, 8}
18   12   {0, 1, 2, 3, 4, 6, 8, 9, 10, 12, 14, 16}
20    9   {0, 1, 2, 4, 5, 8, 10, 12, 16}
24   11   {0, 1, 2, 3, 4, 6, 8, 9, 12, 16, 18}
28    9   {0, 1, 2, 4, 7, 8, 14, 16, 21}
30   19   {0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 21, 24, 25, 27}
36   16   {0, 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 20, 24, 27, 28, 32}
For n = 10, we have S(2,10) = {1, 2, 4, 6, 8} and S(5,10) = {1, 5}. Therefore we have the following distinct products:
   1  2  4  8  6
   5  0
Hence T(10) = {0, 1, 2, 4, 5, 6, 8}; terms in A003592 belong to these residues (mod 10).
For n = 12, we have S(2,12) = {1, 2, 4, 8} and S(3,12) = {1, 3, 9}. Therefore we have the following distinct products:
   1  2  4  8
   3  6  0
   9
Thus T(12) = {0, 1, 2, 3, 4, 6, 8, 9}, terms in A003586 belong to these residues (mod 12).
For n = 30, we have {1, 2, 4, 8, 16}, {1, 3, 9, 21, 27}, and {1, 5, 25}. Therefore we have the following distinct products:
   1  2  4  8  16         5  10  20         25
   3  6 12 24            15   0
   9 18
  27
Thus T(30) = {0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 21, 24, 25, 27}; terms in A051037 belong to these residues (mod 30).

Michael De Vlieger, Table of n, a(n) for n = 1..22906 (rows n = 1..500, flattened)
Michael De Vlieger, Plot k in row n at (x,y) = (k,-n), n = 1..36, showing reduced residues mod n in gray and labeling terms in row n. The number n appears on the left in red italic, and row length A381800(n) in blue at right.
Michael De Vlieger, Plot k in row n at (x,y) = (k,-n), n = 1..5000.

Cf. A007947, A038566, A121998, A162306, A381799, A381800.

Table[Union@ Flatten@ Mod[TensorProduct @@ Map[(p = #; NestWhileList[Mod[p*#, n] &, 1, UnsameQ, All]) &, FactorInteger[n][[All, 1]] ], n], {n, 30}]

Row 1 is {0} since 1 is the empty product and the only number that has zero prime factors is 1, congruent to 0 (mod 1).
Row n begins with {0,1} for n > 1.
For prime p, row p = {0,1}.
For prime power p^m, m > 0, row p = union of {0} and {p^i, i < m}.
Row n is a subset of row n of A121998, considering n in A121998 instead as n mod n = 0.
Row n is a superset of row n of A162306, considering n in A162306 instead as n mod n = 0.

A381802 a(n) = number of distinct residues r mod n of numbers k congruent to r (mod n) such that rad(k) does not divide n, where rad = A007947.

Original entry on oeis.org

0, 0, 1, 1, 3, 1, 5, 4, 6, 3, 9, 4, 11, 8, 7, 11, 15, 6, 17, 11, 12, 9, 21, 13, 22, 11, 23, 19, 27, 11, 29, 26, 24, 23, 23, 20, 35, 17, 33, 28, 39, 18, 41, 28, 30, 32, 45, 32, 46, 22, 31, 35, 51, 23, 47, 44, 36, 27, 57, 32, 59, 54, 50, 57, 55, 34, 65, 55, 54, 35

Offset: 1

Michael De Vlieger, Mar 14 2025

nonn

			a(n) = 0 for n = 1..2, since there do not exist any residues mod n that do not represent a power of n.
 n  a(n)  [0..n-1] \ row n of A381801.
------------------------------------------------
 6    1   {5}
10    3   {3,7,9}
12    4   {5,7,10,11}
14    8   {3,5,6,9,10,11,12,13}
15    7   {2,4,7,8,11,13,14}
18    6   {5,7,11,13,15,17}
20   11   {3,6,7,9,11,13,14,15,17,18,19}
21   12   {2,4,5,8,10,11,13,14,16,17,19,20}
22    9   {3,5,7,9,13,15,17,19,21}
24   13   {5,7,10,11,13,14,15,17,19,20,21,22,23}
26   11   {3,5,7,9,11,15,17,19,21,23,25}
28   19   {3,5,6,9,10,11,12,13,15,17,18,19,20,22,23,24,25,26,27}
30   11   {7,11,13,14,17,19,22,23,26,28,29}

Michael De Vlieger, Table of n, a(n) for n = 1..10000
Michael De Vlieger, Log log scatterplot of a(n), n = 1..2^16, showing prime n in red, proper prime power n in gold, squarefree composite n in green, and n that is neither squarefree nor prime power in blue and magenta, with magenta also representing powerful n that is not a prime power.

Cf. A000010, A381800, A381801.

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[n - Length@ f[n], {n, 2, 120}]

a(n) = n - A381800(n).
a(n) > 0 for n > 2.
a(n) - phi(n) + 1 >= 0, where phi = A000010.
a(p) = p-2.
a(p^m) = n - m - 1.

A381804 Number of residues r mod n congruent to k such that rad(k) | n but rad(r) does not divide n, with rad = A007947.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 3, 0, 0, 2, 0, 1, 4, 6, 0, 0, 0, 8, 0, 1, 0, 1, 0, 0, 3, 3, 7, 2, 0, 13, 0, 1, 0, 5, 0, 7, 7, 6, 0, 1, 0, 16, 14, 8, 0, 15, 3, 1, 15, 23, 0, 2, 0, 0, 5, 0, 5, 10, 0, 3, 9, 15, 0, 2, 0, 30, 20, 14, 10, 10, 0, 3, 0, 14, 0

Offset: 1

Michael De Vlieger, Mar 14 2025

nonn

a(n) is the number of r in row n of A381801 that are such that rad(r) does not divide n.
For prime p, a(p) = 0 since r < n are coprime to p and k such that rad(k) | p are powers of p with p^0 congruent to 1 (mod p) and p^m congruent to 0 (mod p) for m > 0.
For proper prime power p^m, m > 1, a(p^m) = 0 since k such that rad(k) | p are powers p^j, j > 1, such that p^j mod p^m = p^(j mod m), divisors d of p^m and thus rad(d) | p^m.

			Let S(n) = row n of A381801 and R(n) = row n of A162306, with n in R(n) instead written as n mod n = 0.
Define quality Q between natural numbers k and n to be rad(k) does not divide n.
a(10) = 1 since S(10) = {0,1,2,4,5,6,8} only contains r = 6 with quality Q.
a(15) = 3 since S(15) = {0,1,3,5,6,9,10,12} and R(15) = {0,1,3,5,9} = {6,10,12}.
a(18) = 2 since S(18) = {0,1,2,3,4,6,8,9,10,12,14,16} and R(18) = {1,2,3,4,6,8,9,12,16,18} = {10,14}.
a(20) = 1 since S(20) = {0,1,2,4,5,8,10,12,16} and R(20) = {0,1,2,4,5,8,10,16} = {12}, etc.

Cf. A010846, A243623, A381800.

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 ];
rad[x_] := Times @@ FactorInteger[x][[All, 1]];
{0}~Join~Table[Length@ Complement[f[n], {0}~Join~Select[Range[n - 1], Divisible[#, rad[#]] &]], {n, 2, 120}]

a(n) = A381800(n) - A010846(n).
a(n) <= A243623(n).
For prime power p^m, a(p^m) = 0.

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

Original entry on oeis.org

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

Michael De Vlieger, Mar 24 2025

nonn

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.

			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.

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

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

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}]

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.

cp's OEIS Frontend

A382138 a(n) = A381800(n) - A381798(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A381801 Irregular triangle read by rows: row n lists the residues r mod n of numbers k such that rad(k) | n, where rad = A007947.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A381802 a(n) = number of distinct residues r mod n of numbers k congruent to r (mod n) such that rad(k) does not divide n, where rad = A007947.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A381804 Number of residues r mod n congruent to k such that rad(k) | n but rad(r) does not divide n, with rad = A007947.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula