A381798 -id:A381798 - cp's OEIS frontend

A380870 a(n) = A381798(n) - A361373(n) - 1.

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, 4, 0, 7, 6, 6, 0, 1, 0, 15, 14, 8, 0, 13, 3, 0, 15, 23, 0, 1, 0, 0, 5, 0, 5, 7, 0, 3, 9, 12, 0, 2, 0, 30, 18, 14, 10, 6, 0, 3, 0, 14, 0

Offset: 1

Michael De Vlieger, Apr 08 2025

nonn

a(n) = cardinality of the intersection of A024619 and row n of A381799.
Let S(n,p) = {p^m : p | n, m = 1..floor(log_p n)}. Therefore S(10,2) = {1,2,4,8} and S(30,3) = {1,3,9,27}. Then U({S(n,p) : p|n}) = row n of A377485.
Let T(n,p) = {p^m (mod n) : p | n} the set of prime divisor power residues r (mod n) == p^m, p | n. Thus T(10,2) = {1,2,4,8,6} and T(30,3) = {1,3,9,27,21}. Then U({T(n,p) : p|n}) = row n of A381799.

			Table of n, a(n), and H(n) = intersection of row n of A381799 with A024619.
 n   facs(n)   a(n)  H(n)
--------------------------------------------
 6   2 * 3       0   -
10   2 * 5       1   {6}
12   2^2 * 3     0   -
14   2 * 7       0   -
15   3 * 5       3   {6, 10, 12}
18   2 * 3^2     2   {10, 14}
20   2^2 * 5     1   {12}
21   3 * 7       4   {6, 12, 15, 18}
22   2 * 11      6   {6, 10, 12, 14, 18, 20}
24   2^3 * 3     0   -
30   2 * 3 * 5   1   {21}
.
a(6) = 0 since Q(6) = R(6) = {1,2,3,4}, i.e., all terms in row 6 of A381799 are powers of primes.
a(10) = 1 since Q(10) = {1,2,4,5,8} but R(10) = {1,2,4,5,6,8}; the latter set contains 1 term (i.e., 6) that is not a member of the former set.
a(14) = 0 since R(14) = {1,2,4,7,8} are all powers of primes.
a(15) = 3 since R(15) = {1,3,5,6,9,10,12} has 3 terms {6,10,12} that are not powers of primes.
a(18) = 2 since R(18) = {1,2,3,4,8,9,10,14,16} has 2 terms {6,10} that are not powers of primes, etc.

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

Cf. A000961, A024619, A361373, A377485, A381750, A381798, A381799.

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]] ] ]
Table[Count[Union@ Flatten@ Map[f[n, #] &, FactorInteger[n][[All, 1]] ], _?(And[# > 1, ! PrimePowerQ[#]] &)], {n, 120}]

Let Q(n) = {1} joined to row n > 1 of A377485 and let R(n) = row n of A381799.
a(n) = card(U(Q(n) \ R(n))).
a(p^m) = 0 for prime power p^m, m >= 0.
a(n) = 0 for n in A381750.

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.

A381799 Irregular triangle read by rows, where row n is a list of residues of powers of prime factors of n (mod n).

Original entry on oeis.org

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

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}. Examples: S(2,10) = {1, 2, 4, 8, 6}, while S(2,8) = {0, 1, 2, 4} and S(2,12) = {1, 2, 4, 8}; S(3,6) = {1, 3}, S(3,9) = {0, 1, 3}, S(3,12) = {1, 3, 9}, etc.
Define T(n) to be the (sorted) union of S(p,n) for all prime factors p | n.
Row n of this table is T(n).
For n > 1, the intersection of row n of this table and row n of A038566 is {1}. Thus, 1 appears in each row except for n = 1, since p^0 = 1 for all primes p | n.
The number 0 appears in T(p^m) (where p is prime and m >= 1) since p^m is congruent to 0 (mod p^m).
Zero does not appear in T(n) for n in A024619.

			Triangle begins:
 n   row n
--------------------------
 1:  0;
 2:  0, 1;
 3:  0, 1;
 4:  0, 1, 2;
 5:  0, 1;
 6:  1, 2, 3, 4;
 7:  0, 1;
 8:  0, 1, 2, 4;
 9:  0, 1, 3;
10:  1, 2, 4, 5, 6, 8;
11:  0, 1;
12:  1, 2, 3, 4, 8, 9; etc.
For n = 10, we have S(2,10) = {1, 2, 4, 8, 6}, S(5,10) = {1, 5}, thus T(10) = {1, 2, 4, 5, 6, 8}.
For n = 12, we have S(2,12) = {1, 2, 4, 8}, S(3,12) = {1, 3, 9}, thus T(12) = {1, 2, 3, 4, 8, 9}.
For n = 16, we have S(2,16) = {1, 2, 4, 8, 0}, thus T(16) = {0, 1, 2, 4, 8}.
For n = 30, we have S(2,30) = {1, 2, 4, 8, 16}, S(3,30) = {1, 3, 9, 27, 21}, and S(5,30) = {1, 5, 25}, so T(30) = {1, 2, 3, 4, 5, 8, 9, 16, 21, 25, 27}, etc.

Michael De Vlieger, Table of n, a(n) for n = 1..17305 (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 A381798(n) in blue at right.
Michael De Vlieger, Plot k in row n at (x,y) = (k,-n), n = 1..5000.

Cf. A024619, A038566, A121998, A381798.

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

Row 1 = {0} since 1 is the empty product.
For prime p, row p is {0, 1}.
For proper prime power p^m, m > 1, row p^m is the union of {0} and p^i, i < m.
A381798(n) = length of row n.

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).

cp's OEIS Frontend

A380870 a(n) = A381798(n) - A361373(n) - 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A381799 Irregular triangle read by rows, where row n is a list of residues of powers of prime factors of n (mod n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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