|
%I M0411 N0157 #62 Oct 23 2022 02:54:41
%S 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,
%T 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,
%U 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
%N Number of pairs x,y such that y-x=2, (x,n)=1, (y,n)=1 and 1 <= x <= n.
%C This is the function phi(n, 2) defined in Alder. - _Michel Marcus_, Nov 14 2017
%D V. A. Golubev, Sur certaines fonctions multiplicatives et le problème des jumeaux. Mathesis 67 (1958), 11-20.
%D V. A. Golubev, Nombres de Mersenne et caractères du nombre 2. Mathesis 67 (1958), 257-262.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Amiram Eldar, <a href="/A002472/b002472.txt">Table of n, a(n) for n = 1..10000</a> (terms 1..1000 from T. D. Noe)
%H Henry L. Alder, <a href="http://www.jstor.org/stable/2308710">A Generalization of the Euler phi-Function</a>, The American Mathematical Monthly, Vol. 65, No. 9 (Nov., 1958), pp. 690-692.
%H V. A. Golubev, <a href="http://dml.cz/dmlcz/117061">A generalization of the functions phi(n) and pi(x)</a>. Časopis pro pěstování matematiky 78 (1953), 47-48.
%H V. A. Golubev, <a href="http://dml.cz/dmlcz/117442">Exact formulas for the number of twin primes and other generalizations of the function pi(x)</a>. Časopis pro pěstování matematiky 87 (1962), 296-305.
%H Alexei Kourbatov and Marek Wolf, <a href="http://arxiv.org/abs/1901.03785">Predicting maximal gaps in sets of primes</a>, arXiv preprint arXiv:1901.03785 [math.NT], 2019.
%F 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
%F 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
%F 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
%e 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.
%t 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 *)
%t (* Second program (5 times faster): *)
%t a[n_] := Sum[Boole[GCD[n, x] == 1 && GCD[n, x+2] == 1], {x, 1, n}];
%t Array[a, 81] (* _Jean-François Alcover_, Jun 19 2018, after _Michel Marcus_ *)
%t 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 *)
%o (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))<<max(0,k-1) \\ _Charles R Greathouse IV_, Nov 22 2011
%o (PARI) a(n) = sum(x=1, n, (gcd(n,x) == 1) && (gcd(n, x+2) == 1)); \\ _Michel Marcus_, Nov 14 2017
%o (Haskell)
%o a002472 n = length [x | x <- [1..n], gcd n x == 1, gcd n (x + 2) == 1]
%o -- _Reinhard Zumkeller_, Mar 23 2012
%Y Cf. A000010 (phi(n,0)), A058026 (phi(n,1)), A065474.
%Y 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).
%K nonn,nice,easy,mult
%O 1,4
%A _N. J. A. Sloane_
%E More terms from _David W. Wilson_
|
