A319534 - OEIS

%I #49 Feb 28 2024 10:49:12

%S 1,1,1,2,2,1,4,4,3,2,8,2,10,4,2,8,14,3,16,4,4,8,20,4,10,10,9,8,26,2,

%T 28,16,8,14,8,6,34,16,10,8,38,4,40,16,6,20,44,8,28,10,14,20,50,9,16,

%U 16,16,26,56,4,58,28,12,32,20,8,64,28,20,8,68,12,70,34,10,32,32,10,76,16

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

%C 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 triples (p, p+2, p+6). This sequence also gives the number of "admissible" residue classes (mod n) for initial primes p in the other type of prime triples: (p,p+4,p+6). This is a generalization of Euler's totient function (the number of residue classes modulo n containing infinitely many primes).

%C If n is prime, a(n) = max(1,n-3).

%D V. A. Golubev, Sur certaines fonctions multiplicatives et le problème des jumeaux. Mathesis 67 (1958), 11-20.

%D József Sándor and Borislav Crstici, Handbook of Number Theory II, Kluwer, 2004, p. 289.

%H Amiram Eldar, <a href="/A319534/b319534.txt">Table of n, a(n) for n = 1..10000</a>

%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,3; (p-3)*p^(e-1) if p > 3.

%F Sum_{k=1..n} a(k) ~ c * n^2, where c = (7/24) * Product_{p prime >= 5} (1 - 3/p^2) = 0.2196022165... . - _Amiram Eldar_, Nov 01 2022

%e All initial primes p in prime triples (p, p+2, p+6) are congruent to 5 mod 6; that is, there is only one "admissible" residue class mod 6; therefore a(6) = 1.

%t a[n_] := Sum[Boole[CoprimeQ[n, x] && CoprimeQ[n, x+2] && CoprimeQ[n, x+6]], {x, 1, n}]; Array[a, 80] (* _Jean-François Alcover_, Jan 29 2019 *)

%t f[p_, e_] := If[p < 5, p^(e-1), (p-3)*p^(e-1)]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* _Amiram Eldar_, Jan 22 2020 *)

%o (PARI) phi3(n) = sum(x=1, n, (gcd(n, x)==1) && (gcd(n, x+2)==1) && (gcd(n, x+6)==1));

%o for(n=1, 80, print1(phi3(n)", "))

%Y Cf. similar generalizations of totient for k-tuples: A002472 (k=2), A319516 (k=4), A321029 (k=5), A321030 (k=6).

%K nonn,mult

%O 1,4

%A _Alexei Kourbatov_, Sep 22 2018