A381801 -id:A381801 - cp's OEIS frontend

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

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.

A382438 Numbers k in A024619 such that all residues r (mod k) in row k of A381801 are such that rad(r) divides k, where rad = A007947.

Original entry on oeis.org

6, 12, 14, 24, 39, 62, 155, 254, 3279, 5219, 16382, 19607, 70643, 97655, 208919, 262142, 363023, 402233, 712979, 1040603, 1048574, 1508597, 2265383, 2391483, 4685519, 5207819, 6728903, 21243689, 25239899, 56328959, 61035155, 67977559, 150508643

Offset: 1

Michael De Vlieger, Mar 27 2025

nonn

Numbers k in A024619 such that A381804(k) = 0.
Let S(n,p) be the set of distinct power residues r (mod n) beginning with empty product and recursively multiplying by prime p | n. For example, S(10,2) = {1,2,4,8,6}.
This sequence builds on A381750, taking the tensor product T(k) (mod k) of S(k,p), p | k. If all products r (mod k) are such that rad(r) | k, then k is in this sequence. Distinct residues r (mod k) in T(k) are listed in row k of A381801.
Proper subset of A381750.
A139257 is a proper subset since 2^m is congruent to 2 (mod 2^m-2).
Conjecture: 12 and 24 are the only nonsquarefree numbers in this sequence, i.e., in A126706.

			Table of a(n) for n = 1..10, showing prime decomposition (facs(a(n))), row a(n) of A381801:
                        Row a(n) of A381801
 n    a(n)  facs(a(n))  k (mod a(n)) such that rad(k) | a(n).
-------------------------------------------------------------
 1      6   2 * 3       {0, 1, 2, 3, 4}
 2     12   2^2 * 3     {0, 1, 2, 3, 4, 6, 8, 9}
 3     14   2 * 7       {0, 1, 2, 4, 7, 8}
 4     24   2^3 * 3     {0, 1, 2, 3, 4, 6, 8, 9, 12, 16, 18}
 5     39   3 * 13      {0, 1, 3, 9, 13, 27}
 6     62   2 * 31      {0, 1, 2, 4, 8, 16, 31, 32}
 7    155   5 * 31      {0, 1, 5, 25, 31, 125}
 8    254   2 * 127     {0, 1, 2, 4, 8, 16, 32, 64, 127, 128}
 9   3279   3 * 1093    {0, 1, 3, 9, 27, 81, 243, 729, 1093, 2187}
10   5219   17 * 307    {0, 1, 17, 289, 307, 4913}
Let b = A381750.
a(1) = 6 since T(6) (mod 6) = {1,2,4} X {1,3} = {{1,2,4},{3,0,0}}; all residues r (mod 6) in T(6) (i.e., in row 6 of A381801) are such that rad(r) | 6.
a(2) = 12 since T(12) (mod 12) = {1,2,4,8} X {1,3,9} = {{1,2,4,8},{3,6,0,0},{9,6,0,0}}; all residues r (mod 12) in T(12) are such that rad(r) | 12.
a(3) = 14 since T(14) (mod 14) = {1,2,4,8} X {1,7} = {{1,2,4,8},{7,0,0,0}}; all residues r (mod 14) in T(14) are such that rad(r) | 14.
a(4) = 24 since T(24) (mod 24) = {1,2,4,8,16} X {1,3,9} = {{1,2,4,8,16},{3,6,12,0,0},{9,18,0,0,0}}; all residues r (mod 24) in T(24) are such that rad(r) | 24.
b(6) = 56 is not in the sequence since 49*2 = 98 = 42 (mod 56), rad(42) does not divide 56.
b(8) = 112 is not in the sequence since 49*4 = 196 = 84 (mod 112), rad(84) does not divide 112, etc.

Michael De Vlieger, Efficient Mathematica code for this sequence (2025).

Cf. A007947, A024619, A381750, A381801.

A381800 a(n) = number of distinct residues r mod n of numbers k such that rad(k) | n, where rad = A007947.

Original entry on oeis.org

1, 2, 2, 3, 2, 5, 2, 4, 3, 7, 2, 8, 2, 6, 8, 5, 2, 12, 2, 9, 9, 13, 2, 11, 3, 15, 4, 9, 2, 19, 2, 6, 9, 11, 12, 16, 2, 21, 6, 12, 2, 24, 2, 16, 15, 14, 2, 16, 3, 28, 20, 17, 2, 31, 8, 12, 21, 31, 2, 28, 2, 8, 13, 7, 10, 32, 2, 13, 15, 35, 2, 20, 2, 39, 29, 24

Offset: 1

Michael De Vlieger, Mar 07 2025

nonn

			 n  a(n)  row n of A381801
----------------------------------------------
 1    1   {0}
 2    2   {0,1}
 3    2   {0,1}
 4    3   {0,1,2}
 6    5   {0,1,2,3,4}
 8    4   {0,1,2,4}
10    7   {0,1,2,4,5,6,8}
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}
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}
21    9   {0,1,3,6,7,9,12,15,18}
22   13   {0,1,2,4,6,8,10,11,12,14,16,18,20}
24   11   {0,1,2,3,4,6,8,9,12,16,18}
26   15   {0,1,2,4,6,8,10,12,13,14,16,18,20,22,24}
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}

Michael De Vlieger, Table of n, a(n) for n = 1..5000
Michael De Vlieger, Log log scatterplot of a(n), n = 1..5000, showing a(n) for prime n in red, a(n) for proper prime power n in gold, a(n) such that n is squarefree and composite in green, and a(n) such that n is neither squarefree nor prime power in blue and magenta, where the latter color also signifies n is powerful but not a prime power.
Michael De Vlieger, Faster code for A381800 and A381801, 2025.

Cf. A000005, A010846, A024619, A051953, A381798, A381801.

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

a(n) = length of row n of A381801.
a(1) = 1 since 1 is the empty product.
A010846(n) <= a(n) <= A051953(n).
a(n) >= 2 for n > 1.
For prime p, a(p) = A010846(p^m) = A000005(p^m) = A381798(p) = 2.
For prime power p^m, m > 0, a(p^m) = A010846(p^m) = A000005(p^m) = A381798(p^m) = m+1.
For n in A024619, a(n) > A381798(n).

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.

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

Original entry on oeis.org

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.

cp's OEIS Frontend

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

A382438 Numbers k in A024619 such that all residues r (mod k) in row k of A381801 are such that rad(r) divides k, where rad = A007947.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A381800 a(n) = number of distinct residues r mod n of numbers k such that rad(k) | n, where rad = A007947.

Views

Author

Keywords

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula