A319534 -id:A319534 - cp's OEIS frontend

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

N. J. A. Sloane

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

			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.

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).

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.

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.

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

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

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 *)

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

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

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)

More terms from David W. Wilson

A319516 Number of integers x such that 1 <= x <= n and gcd(x,n) = gcd(x+2,n) = gcd(x+6,n) = gcd(x+8,n) = 1.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 3, 4, 3, 1, 7, 2, 9, 3, 1, 8, 13, 3, 15, 2, 3, 7, 19, 4, 5, 9, 9, 6, 25, 1, 27, 16, 7, 13, 3, 6, 33, 15, 9, 4, 37, 3, 39, 14, 3, 19, 43, 8, 21, 5, 13, 18, 49, 9, 7, 12, 15, 25, 55, 2, 57, 27, 9, 32, 9, 7, 63, 26, 19, 3, 67, 12, 69, 33, 5, 30, 21, 9, 75, 8

Offset: 1

Alexei Kourbatov, Sep 21 2018

Equivalently, a(n) is the number of "admissible" residue classes modulo n which are allowed (by divisibility considerations) to contain infinitely many initial primes in prime quadruples (p, p+2, p+6, p+8). This is a generalization of Euler's totient function: the number of residue classes modulo n containing infinitely many primes.

If n is prime, a(n) = max(1,n-4).

			Some prime quadruples start with a prime congruent to 1 mod 4; others start with a prime congruent to 3 mod 4; that is, there are 2 "admissible" residue classes mod 4; therefore a(4)=2. All initial primes in prime quadruples are 5 mod 6; that is, there is only one "admissible" residue class mod 6; therefore a(6) = 1.

V. A. Golubev, Sur certaines fonctions multiplicatives et le problème des jumeaux. Mathesis 67 (1958), 11-20.
József Sándor and Borislav Crstici, Handbook of Number Theory II, Kluwer, 2004, p. 289.

Amiram Eldar, Table of n, a(n) for n = 1..10000
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.

Cf. similar generalizations of totient for k-tuples: A002472 (k=2), A319534 (k=3), A321029 (k=5), A321030 (k=6).

a[n_] := Sum[Boole[CoprimeQ[n, x] && CoprimeQ[n, x+2] && CoprimeQ[n, x+6] && CoprimeQ[n, x+8]], {x, 1, n}]; Array[a, 80] (* Jean-François Alcover, Jan 29 2019 *)
f[p_, e_] := If[p < 7, p^(e-1), (p-4)*p^(e-1)]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Jan 22 2020 *)

phi4(n) = sum(x=1, n, (gcd(n,x)==1) && (gcd(n,x+2)==1) && (gcd(n,x+6)==1) && (gcd(n,x+8)==1));
for(n=1,80,print1(phi4(n)","))

Multiplicative with a(p^e) = p^(e-1) if p <= 5; (p-4)*p^(e-1) if p > 5.

Sum_{k=1..n} a(k) ~ c * n^2, where c = (49/200) * Product_{p prime >= 7} (1 - 4/p^2) = 0.1987646881... . - Amiram Eldar, Nov 01 2022

A321029 Number of integers x such that 1 <= x <= n and gcd(x,n) = gcd(x+4,n) = gcd(x+6,n) = gcd(x+10,n) = gcd(x+12,n) = 1.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 2, 4, 3, 1, 6, 2, 8, 2, 1, 8, 12, 3, 14, 2, 2, 6, 18, 4, 5, 8, 9, 4, 24, 1, 26, 16, 6, 12, 2, 6, 32, 14, 8, 4, 36, 2, 38, 12, 3, 18, 42, 8, 14, 5, 12, 16, 48, 9, 6, 8, 14, 24, 54, 2, 56, 26, 6, 32, 8, 6, 62, 24, 18, 2, 66, 12, 68, 32, 5, 28, 12, 8, 74, 8

Offset: 1

Alexei Kourbatov, Oct 26 2018

Equivalently, a(n) is the number of "admissible" residue classes modulo n which are allowed (by divisibility considerations) to contain infinitely many initial primes p in prime 5-tuples (p, p+4, p+6, p+10, p+12). This sequence also gives the number of "admissible" residue classes (mod n) for initial primes p in the other type of prime 5-tuples: (p, p+2, p+6, p+8, p+12). This sequence is a generalization of Euler's totient function (A000010(n), the number of residue classes modulo n containing infinitely many primes).

If n is prime, a(n) = max(1,n-5).

			All initial primes p in prime 5-tuples (p, p+4, p+6, p+10, p+12) are congruent to 7 mod 10; that is, there is only one "admissible" residue class mod 10; therefore a(10) = 1.

V. A. Golubev, Sur certaines fonctions multiplicatives et le problème des jumeaux. Mathesis 67 (1958), 11-20.
József Sándor and Borislav Crstici, Handbook of Number Theory II, Kluwer, 2004, p. 289.

Amiram Eldar, Table of n, a(n) for n = 1..10000
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.

Cf. similar generalizations of totient for k-tuples: A002472 (k=2), A319534 (k=3), A319516 (k=4), A321030 (k=6).

Table[Count[Range@ n, x_ /; Equal @@ Append[Map[GCD[# + x, n] &, {0, 4, 6, 10, 12}], 1]], {n, 80}] (* Michael De Vlieger, Nov 13 2018 *)
f[p_, e_] := If[p < 7, p^(e-1), (p-5)*p^(e-1)]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Jan 22 2020 *)

phi5(n) = sum(x=1, n, (gcd(n, x)==1) && (gcd(n, x+4)==1) && (gcd(n, x+6)==1) && (gcd(n, x+10)==1) && (gcd(n, x+12)==1));
for(n=1, 80, print1(phi5(n)", "))

Multiplicative with a(p^e) = p^(e-1) if p <= 5; (p-5)*p^(e-1) if p >= 7.

Sum_{k=1..n} a(k) ~ c * n^2, where c = (49/200) * Product_{p prime >= 7} (1 - 5/p^2) = 0.1883521849... . - Amiram Eldar, Nov 01 2022

A321030 Number of integers x such that 1 <= x <= n and gcd(x,n) = gcd(x+4,n) = gcd(x+6,n) = gcd(x+10,n) = gcd(x+12,n) = gcd(x+16,n) = 1.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 4, 3, 1, 5, 2, 7, 1, 1, 8, 11, 3, 13, 2, 1, 5, 17, 4, 5, 7, 9, 2, 23, 1, 25, 16, 5, 11, 1, 6, 31, 13, 7, 4, 35, 1, 37, 10, 3, 17, 41, 8, 7, 5, 11, 14, 47, 9, 5, 4, 13, 23, 53, 2, 55, 25, 3, 32, 7, 5, 61, 22, 17, 1, 65, 12, 67, 31, 5, 26, 5, 7, 73, 8

Offset: 1

Alexei Kourbatov, Oct 26 2018

Equivalently, a(n) is the number of "admissible" residue classes modulo n which are allowed (by divisibility considerations) to contain infinitely many initial primes in prime 6-tuples (p, p+4, p+6, p+10, p+12, p+16). This is a generalization of Euler's totient function (A000010(n), the number of residue classes modulo n containing infinitely many primes).

If n is prime, a(n) = max(1,n-6).

			All initial primes p in prime 6-tuples (p, p+4, p+6, p+10, p+12, p+16) are congruent to 7 mod 10; that is, there is only one "admissible" residue class mod 10; therefore a(10) = 1.

V. A. Golubev, Sur certaines fonctions multiplicatives et le problème des jumeaux. Mathesis 67 (1958), 11-20.
József Sándor and Borislav Crstici, Handbook of Number Theory II, Kluwer, 2004, p. 289.

Amiram Eldar, Table of n, a(n) for n = 1..10000
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.

Cf. similar generalizations of totient for k-tuples: A002472 (k=2), A319534 (k=3), A319516 (k=4), A321029 (k=5).

Table[Count[Range@ n, x_ /; Equal @@ Append[Map[GCD[# + x, n] &, {0, 4, 6, 10, 12, 16}], 1]], {n, 80}] (* Michael De Vlieger, Nov 13 2018 *)
f[p_, e_] := If[p <= 7, p^(e-1), (p-6)*p^(e-1)]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Jan 22 2020 *)

phi6(n) = sum(x=1, n, (gcd(n, x)==1) && (gcd(n, x+4)==1) && (gcd(n, x+6)==1) && (gcd(n, x+10)==1) && (gcd(n, x+12)==1) && (gcd(n, x+16)==1));
for(n=1, 80, print1(phi6(n)", "))

Multiplicative with a(p^e) = p^(e-1) if p <= 7; (p-6)*p^(e-1) if p > 7.

Sum_{k=1..n} a(k) ~ c * n^2, where c = (43/200) * Product_{p prime >= 11} (1 - 6/p^2) = 0.1783680033... . - Amiram Eldar, Nov 01 2022

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Formula

Extensions

A319516 Number of integers x such that 1 <= x <= n and gcd(x,n) = gcd(x+2,n) = gcd(x+6,n) = gcd(x+8,n) = 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A321029 Number of integers x such that 1 <= x <= n and gcd(x,n) = gcd(x+4,n) = gcd(x+6,n) = gcd(x+10,n) = gcd(x+12,n) = 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A321030 Number of integers x such that 1 <= x <= n and gcd(x,n) = gcd(x+4,n) = gcd(x+6,n) = gcd(x+10,n) = gcd(x+12,n) = gcd(x+16,n) = 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula