A360224 Number of k < n such that gcd(k, n) > 1, gcd(n^2-1, k) = 1, and rad(k) does not divide n.

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 3, 0, 0, 0, 2, 0, 3, 0, 2, 1, 4, 0, 5, 0, 5, 2, 1, 0, 4, 0, 6, 2, 6, 0, 12, 0, 5, 3, 7, 0, 14, 0, 5, 2, 10, 0, 11, 0, 4, 5, 13, 0, 19, 0, 12, 7, 7, 1, 13, 0, 14, 3, 11, 0, 31, 0, 13, 9, 8, 2, 21, 0, 19, 7, 21, 0, 18, 2, 13, 9, 22, 0, 21, 1, 16, 10, 16

Offset

1,18

Comments

Number of terms in row n of A272619 that are coprime to (n-1)*(n+1).

Links

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

Michael De Vlieger, Scatterplot of a(n), n = 1..2*10^5.

Michael De Vlieger, Log log scatterplot of a(n), n = 1..2*10^5.

Formula

a(n) <= A243822(n).

Example

Let S(n) = row n of A272619.
a(p) = 0 since S(p) is empty.
a(4) = 0 since S(4) is empty.
a(6) = 0 since S(6) is empty.
a(8) = 0 since S(8) = {6}, but gcd(6,(8+1)) = 3.
a(10) = 0 since S(10) = {6}, but gcd(6,(10-1)) = 3.
a(12) = 1 since S(12) = {10}, and gcd(10,143) = 1.
a(16) = 1 since S(16) = {6, 10, 12, 14}, but only 14 is such that gcd(14, 255) = 1.
a(18) = 3 since S(18) = {10, 14, 15}, and none of these share a prime factor with 323.
a(20) = 0 since S(20) = {6, 12, 14, 15, 18}, and all of these share a factor with 21.

Mathematica

Table[Count[Range[k], _?(Nor[CoprimeQ[#, k], GCD[k^2 - 1, #] > 1, Divisible[k, Times @@ FactorInteger[#][[All, 1]]]] &)], {k, 120}]

Prog

(PARI) rad(n) = factorback(factorint(n)[, 1]); \\ A007947
a(n) = sum(k=1, n-1, (gcd(k, n)>1) && (gcd(n^2-1, k) == 1) && (n % rad(k))); \\ Michel Marcus, May 20 2023

Crossrefs

Cf. A045763, A243823, A272619.

Sequence in context: A036873 A081130 A358623 * A381743 A174428 A308347

Adjacent sequences: A360221 A360222 A360223 * A360225 A360226 A360227

Keyword

nonn

Author

Michael De Vlieger, May 19 2023

Status

approved