A381799 -id:A381799 - cp's OEIS frontend

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.

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.

A381798 Number of residues r such that p^m is congruent to r (mod n), where prime p | n and m >= 0.

Original entry on oeis.org

1, 2, 2, 3, 2, 4, 2, 4, 3, 6, 2, 6, 2, 5, 7, 5, 2, 9, 2, 7, 8, 12, 2, 7, 3, 14, 4, 7, 2, 11, 2, 6, 8, 10, 11, 11, 2, 20, 5, 9, 2, 14, 2, 14, 12, 13, 2, 10, 3, 23, 19, 15, 2, 22, 7, 8, 20, 30, 2, 12, 2, 7, 11, 7, 9, 18, 2, 11, 14, 23, 2, 12, 2, 38, 24, 22, 14, 17

Offset: 1

Michael De Vlieger, Mar 07 2025

nonn

Number of power residues r (mod n) of prime powers p^m such that p | n and m >= 0.
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.
This sequence is card(union(S(p,n))) where S(p,n) is taken across prime factors p | n.

			Table of n, a(n) for select values of n, showing the residues listed in row n of A381799:
 n  a(n)  row n of A381799.
------------------------------------------------
 1    1   {0}
 2    2   {0,1}
 4    3   {0,1,2}
 6    4   {1,2,3,4}
 8    4   {0,1,2,4}
10    6   {1,2,4,5,6,8}
12    6   {1,2,3,4,8,9}
14    5   {1,2,4,7,8}
15    7   {1,3,5,6,9,10,12}
18    9   {1,2,3,4,8,9,10,14,16}
20    7   {1,2,4,5,8,12,16}
21    8   {1,3,6,7,9,12,15,18}
22   12   {1,2,4,6,8,10,11,12,14,16,18,20}
24    7   {1,2,3,4,8,9,16}
26   14   {1,2,4,6,8,10,12,13,14,16,18,20,22,24}
28    7   {1,2,4,7,8,16,21}
30   11   {1,2,3,4,5,8,9,16,21,25,27}
33    8   {1,3,9,11,12,15,22,27}
34   10   {1,2,4,8,16,17,18,26,30,32}
35   11   {1,5,7,10,14,15,20,21,25,28,30}
36   11   {1,2,3,4,8,9,16,20,27,28,32}
a(1) = 1 since 1 is the empty product.
a(2) = 2 since S(2,2) = {0, 1}.
a(4) = 3 since S(2,4) = {1,2,0}.
a(6) = 4 since {1,2,3,4} is the union of S(2,6) = {1,2,4} and S(3,6) = {1,3}.
a(10) = 6 since {1,2,4,5,6,8} is the union of S(2,10) = {1,2,4,8,6} and S(5,10) = {1,5}.
a(12) = 6 since {1,2,3,4,8,9} is the union of S(2,12) = {1,2,4,8} and S(3,12) = {1,3,9}.
a(30) = 11 since {1,2,3,4,5,8,9,16,21,25,27} is the union of S(2,30) = {1,2,4,8,16}, S(3,30) = {1,3,9,27,21}, and S(5,30) = {1,5,25}, etc.

Michael De Vlieger, Table of n, a(n) for n = 1..5000
Michael De Vlieger, Log log scatterplot of a(n), n = 1..2310, 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.

Cf. A000961, A381799.

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

a(1) = 1.
a(p) = 2 since S(p,p) = {0, 1}.
a(p^m) = m+1 since S(p,p^m) = {0} U {p^i, i < m}.

A381750 Nonprime-powers k such that, for any prime p dividing k and m = 1+floor(log k/log p), rad(p^m (mod k)) divides k, where rad = A007947.

Original entry on oeis.org

6, 12, 14, 24, 39, 56, 62, 112, 120, 155, 254, 992, 1984, 3279, 5219, 16256, 16382, 19607, 32512, 70643, 97655, 208919, 262142, 363023, 402233, 712979, 1040603, 1048574, 1508597, 2265383, 2391483, 4685519, 5207819, 6728903, 21243689, 25239899, 56328959, 61035155, 67100672

Offset: 1

Michael De Vlieger, Mar 27 2025

nonn

The number p^m is the smallest power of p dividing k that exceeds k, where m = 1+floor(log k/log p).
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}.
Prime powers k = p^m, m >= 0 have omega(k) = 1 and all r in S(n,p) are such that rad(r) | n.
Numbers k in this sequence have omega(k) > 1 and all r in S(n,p) are such that rad(r) | n.
A139257 is a proper subset since 2^m is congruent to 2 (mod 2^m-2).
Intersection of this sequence and A381525 is {6}.
Row a(n) of A381799 only contains powers of primes, i.e., row a(n) of A381799 is a proper subset of A000961.

			Table of a(n) for n = 1..10, showing prime decomposition (facs(a(n))), and S(n,p_x), where x = 1 denotes the smallest prime factor, x = 2, the second smallest prime factor, etc.
                         Numbers in row n of A381799:
 n   a(n)  facs(a(n))    S(n,p_1)            S(n,p_2)        S(n,p_3)
---------------------------------------------------------------------
 1     6   2 * 3         {1,2,4},            {1,3}
 2    12   2^2 * 3       {1,2,4,8},          {1,3,9}
 3    14   2 * 7         {1,2,4,8},          {1,7}
 4    24   2^3 * 3       {1,2,4,8,16},       {1,3,9}
 5    39   3 * 13        {1,3,9,27},         {1,13}
 6    56   2^3 * 7       {1,2,4,8,16,32},    {1,7,49}
 7    62   2 * 31        {1,2,4,8,16,32},    {1,31}
 8   112   2^4 * 7       {1,2,4,8,16,32,64}, {1,7,49}
 9   120   2^3 * 3 * 5   {1,2,4,8,16,32,64}, {1,3,9,27,81}, {1,5,25}
10   155   5 * 31        {1,5,25,125},       {1,31}
.
a(1) = 6, the smallest number that is not a prime power, since 2^3 mod 6 = 2, and 3^2 mod 6 = 3, both divide 6.
10 is not in the sequence since 2^4 mod 10 = 6, rad(6) does not divide 10.
a(2) = 12 since 2^4 mod 12 = 4, rad(4) | 12, and 3^3 mod 12 = 3, rad(3) | 12.
a(3) = 14 since 2^4 mod 14 = 2 and 7^2 mod 14 = 7, both divide 14.
15 is not in the sequence since 3^3 mod 15 = 12, rad(12) does not divide 15, etc.

Cf. A000961, A007947, A024619, A139257, A381525, A381799.

nn = 10^5;
Monitor[Reap[Do[
  If[! PrimePowerQ[n],
    If[AllTrue[
      Map[PowerMod[#, 1 + Floor@ Log[#, n], n] &, FactorInteger[n][[All, 1]] ],
        Divisible[n, rad[#]] &],
      Sow[n] ] ], {n, 2, nn}] ][[-1, 1]], n]

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

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

cp's OEIS Frontend

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

A381798 Number of residues r such that p^m is congruent to r (mod n), where prime p | n and m >= 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A381750 Nonprime-powers k such that, for any prime p dividing k and m = 1+floor(log k/log p), rad(p^m (mod k)) divides k, where rad = A007947.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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