cp's OEIS Frontend

A058026 Number of positive integers, k, where k <= n and gcd(k,n) = gcd(k+1,n) = 1.

%I A058026 #85 May 22 2025 12:22:19
%S A058026 1,0,1,0,3,0,5,0,3,0,9,0,11,0,3,0,15,0,17,0,5,0,21,0,15,0,9,0,27,0,29,
%T A058026 0,9,0,15,0,35,0,11,0,39,0,41,0,9,0,45,0,35,0,15,0,51,0,27,0,17,0,57,
%U A058026 0,59,0,15,0,33,0,65,0,21,0,69,0,71,0,15,0,45,0,77,0,27,0,81,0,45,0,27,0
%N A058026 Number of positive integers, k, where k <= n and gcd(k,n) = gcd(k+1,n) = 1.
%C A058026 Called the Schemmel totient function in the Handbook of Number Theory II. - _R. J. Mathar_, Apr 15 2011
%C A058026 a(n) is also the number of units u in Z/nZ such that Phi(1,u) or Phi(2,u) is a unit, where Phi is the cyclotomic polynomial. - _Jordan Lenchitz_, Jul 12 2017
%C A058026 This is the function phi(n, 1) in Alder. - _Michel Marcus_, Nov 14 2017
%D A058026 József Sándor and Borislav Crstici, Handbook of Number theory II, Kluwer Academic Publishers, 2004, Chapter 3, p. 276.
%H A058026 Amiram Eldar, <a href="/A058026/b058026.txt">Table of n, a(n) for n = 1..10000</a> (terms 1..5000 from Enrique Pérez Herrero)
%H A058026 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 A058026 O. Bordelles and B. Cloitre, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Bordelles/bord14.html">An Alternating Sum Involving the Reciprocal of Certain Multiplicative Functions</a>, J. Int. Seq. 16 (2013) #13.6.3.
%H A058026 Colin Defant, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Defant/defant5.html">On Arithmetic Functions Related to Iterates of the Schemmel Totient Functions</a>, J. Int. Seq. 18 (2015) # 15.2.1.
%H A058026 Leonard Eugene Dickson, <a href="https://archive.org/details/historyoftheoryo01dick/page/147/mode/2up">Schemmel's Generalization of Euler's phi-Function</a>, History of the Theory of Numbers, Vol. 1: Divisibility and Primality, Washington, Carnegie Institution of Washington, 1919, p. 147.
%H A058026 Mizan R. Khan and Riaz R. Khan, <a href="https://arxiv.org/abs/2012.11081">To count clean triangles we count on imph(n)</a>, arXiv:2012.11081 [math.CO], 2020.
%H A058026 Walter Klotz and Torsten Sander, <a href="https://doi.org/10.37236/963">Some Properties of Unitary Cayley Graphs</a>, The Electronic Journal of Combinatorics, Volume 14 (2007), #R45. See Corollary 7 p. 4.
%H A058026 Emma T. Lehmer, <a href="https://doi.org/10.1090/S0002-9904-1930-04939-3">A numerical function applied to cyclotomy</a>, Bull. Amer. Math. Soc. 36 (1930), 291-298.
%H A058026 Victor Schemmel, <a href="https://doi.org/10.1515/crll.1869.70.191">Ueber relative Primzahlen</a>, Journal für die reine und angewandte Mathematik, Vol. 70 (1869), pp. 191-192.
%F A058026 Multiplicative with a(p^e) = p^(e-1)*(p-2). - _Vladeta Jovovic_, Dec 01 2001
%F A058026 a(n) = Sum_{d|n} n/d*mu(d)*tau(d). - _Vladeta Jovovic_, Apr 29 2002
%F A058026 a(n) = Sum_{d divides n} phi(n/d)*(-1)^omega(d). - _Vladeta Jovovic_, Sep 26 2002
%F A058026 A003557(n) | a(n). - _R. J. Mathar_, Mar 30 2011
%F A058026 a(n) = n*Product_{primes p|n} (1-2/p). Dirichlet g.f. zeta(s-1)*product_p (1-2*p^(-s)). - _R. J. Mathar_, Apr 15 2011
%F A058026 a(n) = phi(n) * Sum_{d|n} mu(d)/phi(d), where mu(k) is the Moebius function and phi(k) is the Euler totient function. - _Daniel Suteu_, Jun 23 2018
%F A058026 Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = A065474 = Product_{primes p} (1 - 2/p^2) = 0.32263409893924467057953169254823706657095... - _Vaclav Kotesovec_, Dec 18 2019, corrected May 22 2025 (typo found by _Amiram Eldar_)
%F A058026 a(n) = Sum_{k=1..n} (-1)^omega(gcd(n,k)). - _Ilya Gutkovskiy_, Feb 22 2020
%F A058026 a(n) = Sum_{d1|n} Sum_{d2|n} mu(d1*d2)*floor(n/(d1*d2)). - _Ridouane Oudra_, Dec 31 2022
%e A058026 a(15) = 3 because 1 and 2, 7 and 8 and 13 and 14 are all relatively prime to 15.
%e A058026 a(15) = a(3*5) = a(3)*a(5) = 3^0*(3-2)*5^0*(5-2) = 3.
%p A058026 A058026 := proc(n) local a; a := n ; for p in numtheory[factorset](n) do a := a*(1-2/p) ; end do: a ; end proc: # _R. J. Mathar_, Apr 15 2011
%t A058026 a[n_] := DivisorSum[n, n/# MoebiusMu[#] DivisorSigma[0, #]&]; Array[a, 90] (* _Jean-François Alcover_, Dec 05 2015 *)
%t A058026 f[p_, e_] := (p-2) * p^(e-1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* _Amiram Eldar_, May 01 2020 *)
%o A058026 (PARI) a(n) = sumdiv(n, d, n/d*moebius(d)*numdiv(d)); \\ _Michel Marcus_, Apr 27 2014
%o A058026 (PARI) a(n) = n*prod(p=1, n, if (isprime(p) && !(n % p), (1-2/p), 1)); \\ _Michel Marcus_, Feb 02 2016
%o A058026 (Haskell)
%o A058026 a058026 n = product $ zipWith (\p e -> p ^ (e - 1) * (p - 2))
%o A058026                               (a027748_row n) (a124010_row n)
%o A058026 -- _Reinhard Zumkeller_, May 10 2014
%o A058026 (PARI) a(n) = my(r=1,f=factor(n)); for(j=1, #f[,1], my(p=f[j,1],e=f[j,2]); r*=(p-2)*p^(e-1)); return(r); \\ _Jianing Song_, Nov 01 2022
%Y A058026 Cf. A070554, A069828, A027748, A124010, A289460.
%Y A058026 Cf. A000010 (phi(n,0)), A002472 (phi(n,2)).
%K A058026 nonn,mult
%O A058026 1,5
%A A058026 _Leroy Quet_, Nov 15 2000