A002472 Number of pairs x,y such that y-x=2, (x,n)=1, (y,n)=1 and 1 <= x <= n.

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

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy
• mult

Comments

This is the function phi(n, 2) defined in Alder. - Michel Marcus, Nov 14 2017

Examples

			For n = 4, the condition gcd(x,4) = gcd(x+2,4) = 1 is satisfied by exactly two positive integers x not exceeding n, namely, by x = 1 and x = 3. Therefore a(4) = 2.
		

References

• V. A. Golubev, Sur certaines fonctions multiplicatives et le problème des jumeaux. Mathesis 67 (1958), 11-20.
• V. A. Golubev, Nombres de Mersenne et caractères du nombre 2. Mathesis 67 (1958), 257-262.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
• Henry L. Alder, A Generalization of the Euler phi-Function, The American Mathematical Monthly, Vol. 65, No. 9 (Nov., 1958), pp. 690-692.
• V. A. Golubev, A generalization of the functions phi(n) and pi(x), Časopis pro pěstování matematiky 78 (1953), 47-48.
• V. A. Golubev, Exact formulas for the number of twin primes and other generalizations of the function pi(x), Časopis pro pěstování matematiky 87 (1962), 296-305.
• Alexei Kourbatov and Marek Wolf, Predicting maximal gaps in sets of primes, arXiv preprint arXiv:1901.03785 [math.NT], 2019.

Crossrefs

Cf. A000010 (phi(n,0)), A058026 (phi(n,1)), A065474.

Similar generalizations of Euler's totient for prime k-tuples: this sequence (k=2), A319534 (k=3), A319516 (k=4), A321029 (k=5), A321030 (k=6).

Cf. A160467, A000265.

Programs

Haskell

a002472 n = length [x | x <- [1..n], gcd n x == 1, gcd n (x + 2) == 1]
-- Reinhard Zumkeller, Mar 23 2012

Maple

with(numtheory): seq(add(mobius(d)*phi(2*n)/phi(2*d), d in divisors(n)), n=1..100); # Ridouane Oudra, Aug 20 2024

Mathematica

a[n_] := If[ Head[ r=Reduce[ GCD[x, n] == 1 && GCD[x+2, n] == 1 && 1 <= x <= n, x, Integers]] === Or, Length[r], 1]; Table[a[n], {n, 1, 81}] (* Jean-François Alcover, Nov 22 2011 *)
(* Second program (5 times faster): *)
a[n_] := Sum[Boole[GCD[n, x] == 1 && GCD[n, x+2] == 1], {x, 1, n}];
Array[a, 81] (* Jean-François Alcover, Jun 19 2018, after Michel Marcus *)
f[p_, e_] := 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, Jan 22 2020 *)

PARI

a(n)=my(k=valuation(n,2),f=factor(n>>k));prod(i=1,#f[,1],(f[i,1]-2)*f[i,1]^(f[i,2]-1))<Charles R Greathouse IV, Nov 22 2011

PARI

a(n) = sum(x=1, n, (gcd(n,x) == 1) && (gcd(n, x+2) == 1)); \\ Michel Marcus, Nov 14 2017

Formula

Multiplicative with a(p^e) = p^(e-1) if p = 2; (p-2)*p^(e-1) if p > 2. - David W. Wilson, Aug 01 2001

a(n) = Sum_{k=1..n} [GCD(2*n-k,n) * GCD(k+2,n) = 1], where [ ] is the Iverson bracket. - Wesley Ivan Hurt, Sep 29 2021

Sum_{k=1..n} a(k) ~ c * n^2, where c = (3/4) * Product_{p prime} (1 - 2/p^2) = (3/4) * A065474 = 0.2419755742... . - Amiram Eldar, Oct 23 2022

From Ridouane Oudra, Aug 20 2024: (Start)

a(n) = phi(2*n) * Sum_{d|n} mu(d)/phi(2*d).

a(n) = - phi(n) * Sum_{d|n} mu(2*d)/phi(d).

a(n) = A160467(n)*A058026(A000265(n)).

a(2*n+1) = A070554(n).

a(2^m*(2*n+1)) = 2^(m-1)*A070554(n), with m>0. (End)

Extensions

More terms from David W. Wilson