A395900 Number of residue classes r (mod n) for which k = r + m*n, m >= 1, is such that gcd(k,n) > 1 but rad(k) does not divide n, and rad(n) does not divide k, where rad = A007947.

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 3, 0, 0, 0, 1, 0, 4, 1, 0, 0, 6, 0, 0, 0, 8, 0, 4, 0, 0, 5, 8, 0, 8, 0, 0, 10, 12, 0, 7, 0, 9, 7, 11, 0, 15, 0, 3, 0, 12, 0, 6, 8, 21, 1, 0, 0, 17, 0, 25, 14, 0, 8, 15, 0, 24, 11, 12, 0, 25, 0, 0, 7, 17, 3, 22, 0, 29, 0, 20

Offset

1,14

Comments

Number of residues r not divisible by rad(n) that are neither coprime to n nor in row n of A381801.

Links

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

Michael De Vlieger, Diagram showing r <= n, n = 1..36, where a(n) is the number of labeled r in row n. Gray dots correspond to reduced residues r (mod n). Red dots represent divisors, yellow r such that rad(r) | n. Green and blue dots represent r such that neither gcd(r,n) = 1 nor rad(r) | n, where blue additionally represents r such that rad(n) | r (counted by A360543(n)). The unlabeled dots that are not gray correspond to residues r (mod n) such that there exists k = r + m*n such that rad(k) | n, therefore not counted by a(n).

Formula

a(n) < n/rad(n); a(n) < A003557(n).

a(n) <= A360480(n).

a(n) <= A381803(n).

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

a(n) = 0 for n in A381525.

Example

a(6) = 0 since r in {1,5} are coprime to 6, and 1 <= r <= 4 is such that k = r + 6*m have rad(k) | 6 for some m.
a(8) = 0 since for r = 6, k = 6 + 8*m is even, though rad(k) does not divide 8.
a(12) = 1 since for r = 10, k = 10 + 2*m is even, though rad(k) does not divide 12, since numbers congruent to 10 (mod 12) are not divisible by 3.
a(14) = 3 since for r in {6, 10, 12} are even but not divisible by 7, 2^j (mod 14), j >= 0, are in {1,2,4,8}, 7^j (mod 14), j >= 0, are in {1,7}, and the reduced residue system of 14 is row 14 of A038566, i.e., {1, 3, 5, 9, 11, 13}.
a(15) = 0, despite the fact that 6, 10, and 12 are numbers that share a factor with 15, yet 15 is not divisible by their squarefree kernels. This is because 3^4 = 6 (mod 15), 5^2 = 10 (mod 15), 3^3 = 12 (mod 15).
a(18) = 1 since among r in row 18 of A272619, 2^6 = 10 (mod 18), 2^5 = 14 (mod 18), and only r = 15 is such that r + 18*m is not divisible by rad(18) = 6.
a(36) = 8 since among r in row 36 of A272619, 2^7 = 20 (mod 36) and 2^6 = 28 (mod 36). Furthermore, r = 30 is such that rad(36) | r, yet there is no number k = 30 + 36*m such that rad(k) = 30 (mod 36), which distinguishes 30 from all the other terms in row n of A272619.

Mathematica

rad[n_] := Times @@ (First@# & /@ FactorInteger@ n);
Table[r = rad[n]; s = Select[Range[n], CoprimeQ[#, n] &]; t = Union@ Flatten@ Mod[TensorProduct @@ Map[(p = #; NestWhileList[Mod[p*#, n] &, 1, UnsameQ, All]) &, FactorInteger[n][[All, 1]] ], n]; Count[Complement[Range[0, n - 1], Union[s, t] ], _?(! Divisible[#, r] &)], {n, 82}]

Crossrefs

Cf. A000010, A000961, A003557, A007947, A038566, A051953, A243823, A272619, A360480, A360543, A381525, A381801, A381802, A381803.

Sequence in context: A069531 A335487 A035677 * A283470 A101941 A089313

Adjacent sequences: A395897 A395898 A395899 * A395901 A395902 A395903

Keyword

nonn

Author

Michael De Vlieger, May 15 2026

Status

approved