A390299 Number of positive z <= n such that z^2 - 9^g is relatively prime to n (for any particular positive integer g).

1, 1, 2, 2, 3, 2, 5, 4, 6, 3, 9, 4, 11, 5, 6, 8, 15, 6, 17, 6, 10, 9, 21, 8, 15, 11, 18, 10, 27, 6, 29, 16, 18, 15, 15, 12, 35, 17, 22, 12, 39, 10, 41, 18, 18, 21, 45, 16, 35, 15, 30, 22, 51, 18, 27, 20, 34, 27, 57, 12, 59, 29, 30, 32, 33, 18, 65, 30, 42, 15, 69, 24, 71, 35, 30, 34, 45, 22, 77, 24, 54

Offset

1,3

Comments

This is the function phi(n, 3) defined in Alder because:

if phi(n, 2)/phi(n, 2) =: 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

then phi(n, 3)/phi(n, 2) =: 1, 1, 2/1, 1, 1, 2/1, 1, 1, 2/1, 1, 1, 2/1, 1, 1, 2/1, ...

phi(n, 5)/phi(n, 2) =: 1, 1, 1, 1, 4/3, 1, 1, 1, 1, 4/3, 1, 1, 1, 1, 4/3, ...

phi(n, 7)/phi(n, 2) =: 1, 1, 1, 1, 1, 1, 6/5, 1, 1, 1, 1, 1, 1, 6/5, 1, ...

Links

Andrew Howroyd, Table of n, a(n) for n = 1..10000

Henry L. Alder, A Generalization of the Euler phi-Function, The American Mathematical Monthly, Vol. 65, No. 9 (Nov., 1958), pp. 690-692.

Formula

a(n) = A002472(n)*A100063(n).

Also, A000010(A000079(n)) = A002472(A000079(n)), A000010(A003586(n)) = a(A003586(n)), A000010(A003592(n)) = A390470(A003592(n)), ...

From Amiram Eldar, Nov 03 2025: (Start)

Multiplicative with a(2^e) = 2^(e-1), a(3^e) = 2*3^(e-1), and a(p^e) = (p-2)*p^(e-1) for p >= 5.

Dirichlet g.f.: zeta(s-1) * ((1-1/2^s)*(1-1/3^s))/((1-1/2^(s-1))*(1-2/3^s)) * Product_{p prime} (1 - 2/p^s).

Sum_{k=1..n} a(k) ~ c * n^2, where c = (6/7) * Product_{p prime} (1 - 2/p^2) = (6/7) * A065474 = 0.2765435133... . (End)

Mathematica

f[p_, e_] := If[p == 3, 2, 1] * If[p == 2, p^(e - 1), (p - 2)*p^(e - 1)]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Nov 03 2025 *)

Prog

(Magma) [#[z: z in [1..n] | Gcd(z^2 - 9, n) eq 1]: n in [1..81]];
(PARI) a(n) = {my(f = factor(n), p, e); prod(i = 1, #f~, p = f[i, 1]; e = f[i, 2]; if(p == 2, p^(e-1), if(p == 3, 2*(p-2)*p^(e-1), (p-2)*p^(e-1)))); } \\ Amiram Eldar, Nov 03 2025

Crossrefs

Cf. A000010 (phi(n, 0)), A058026 (phi(n, 1)), A002472 (phi(n, 2)), A065474, A100063, A000079, A003586, A003592, A390470.

Sequence in context: A384882 A003974 A065769 * A280264 A219606 A307148

Adjacent sequences: A390296 A390297 A390298 * A390300 A390301 A390302

Keyword

nonn,mult,easy

Author

Juri-Stepan Gerasimov, Oct 31 2025

Status

approved