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

Author

Michael De Vlieger, May 19 2023

Keywords

• nonn

Comments

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

Examples

			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.
		

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.

Crossrefs

Cf. A045763, A243823, A272619.

Programs

Mathematica

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

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

Formula

a(n) <= A243822(n).