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

0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 6, 0, 0, 0, 0, 11, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 26, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 3, 23, 0, 0, 0, 0, 0

Offset

1,16

Comments

Number of residue classes r = m*rad(n) in {0..n-1}, 1 < m < n/rad(n) that are neither coprime to n nor in row n of A381801.

a(n) = A360543(n) for n < 45.

Links

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

Formula

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

a(p^m) = A360543(p^m) = A243823(p^m) with prime p and m > 0. For p^m > 4, a(p^m) > 0.

a(n) = 0 for squarefree n.

a(n) <= A360543(n) <= A243823(n).

a(n) <= A381803(n).

Example

a(8) = 1 since for r = 6, k = 6 + 8*m is even but rad(k) does not divide 8.
a(9) = 1 since for r = 6, k = 6 + 9*m is divisible by 3, but rad(k) does not divide 9.
a(16) = 4 since for r in {6, 12, 14, 16}, k = r + 16*m is even, but rad(k) does not divide 16.
a(36) = 1 since for r = 30, k = 30 + 36*m is divisible by rad(36) = 6, but rad(k) does not divide 36.
a(40) = 1 since for r = 30, k = 30 + 40*m is divisible by rad(40) = 10, but rad(k) does not divide 40.
a(45) = 0 despite the fact that rad(45) | r for r = 30, since 75 = 30 + 45, divisible by rad(45) = 15.
a(48) = 2 since for r in {30, 42}, k = r + 48*m is divisible by rad(48) = 6, but rad(k) does not divide 48.
a(50) = 0 despite the fact that rad(50) | r for r = 30, since 80 = 30 + 50, divisible by rad(50) = 10.
a(54) = 0 despite rad(54) | r for r in {30, 42}, both divisible by rad(54) = 6, but 192 = 30 + 3*54 and 96 = 42 + 54.

Mathematica

rad[x_] := Times @@ FactorInteger[x][[All, 1]]; 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, 86}]

Crossrefs

Cf. A000010, A003557, A005117, A007947, A038566, A051953, A246547, A381801, A381802, A381803, A395900.

Sequence in context: A307380 A178990 A276570 * A360543 A236378 A341880

Adjacent sequences: A395981 A395982 A395983 * A395985 A395986 A395987

Keyword

nonn

Author

Michael De Vlieger, May 15 2026

Status

approved