A058026 Number of positive integers, k, where k <= n and gcd(k,n) = gcd(k+1,n) = 1.
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, 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, 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
Offset: 1
Examples
a(15) = 3 because 1 and 2, 7 and 8 and 13 and 14 are all relatively prime to 15. a(15) = a(3*5) = a(3)*a(5) = 3^0*(3-2)*5^0*(5-2) = 3.
References
- József Sándor and Borislav Crstici, Handbook of Number theory II, Kluwer Academic Publishers, 2004, Chapter 3, p. 276.
Links
- Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..5000 from Enrique Pérez Herrero)
- Henry L. Alder, A Generalization of the Euler phi-Function, The American Mathematical Monthly, Vol. 65, No. 9 (Nov., 1958), pp. 690-692.
- O. Bordelles and B. Cloitre, An Alternating Sum Involving the Reciprocal of Certain Multiplicative Functions, J. Int. Seq. 16 (2013) #13.6.3.
- Colin Defant, On Arithmetic Functions Related to Iterates of the Schemmel Totient Functions, J. Int. Seq. 18 (2015) # 15.2.1.
- Leonard Eugene Dickson, Schemmel's Generalization of Euler's phi-Function, History of the Theory of Numbers, Vol. 1: Divisibility and Primality, Washington, Carnegie Institution of Washington, 1919, p. 147.
- Mizan R. Khan and Riaz R. Khan, To count clean triangles we count on imph(n), arXiv:2012.11081 [math.CO], 2020.
- Walter Klotz and Torsten Sander, Some Properties of Unitary Cayley Graphs, The Electronic Journal of Combinatorics, Volume 14 (2007), #R45. See Corollary 7 p. 4.
- Emma T. Lehmer, A numerical function applied to cyclotomy, Bull. Amer. Math. Soc. 36 (1930), 291-298.
- Victor Schemmel, Ueber relative Primzahlen, Journal für die reine und angewandte Mathematik, Vol. 70 (1869), pp. 191-192.
Crossrefs
Programs
-
Haskell
a058026 n = product $ zipWith (\p e -> p ^ (e - 1) * (p - 2)) (a027748_row n) (a124010_row n) -- Reinhard Zumkeller, May 10 2014 -
Maple
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
-
Mathematica
a[n_] := DivisorSum[n, n/# MoebiusMu[#] DivisorSigma[0, #]&]; Array[a, 90] (* Jean-François Alcover, Dec 05 2015 *) 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 *)
-
PARI
a(n) = sumdiv(n, d, n/d*moebius(d)*numdiv(d)); \\ Michel Marcus, Apr 27 2014
-
PARI
a(n) = n*prod(p=1, n, if (isprime(p) && !(n % p), (1-2/p), 1)); \\ Michel Marcus, Feb 02 2016
-
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
Formula
Multiplicative with a(p^e) = p^(e-1)*(p-2). - Vladeta Jovovic, Dec 01 2001
a(n) = Sum_{d|n} n/d*mu(d)*tau(d). - Vladeta Jovovic, Apr 29 2002
a(n) = Sum_{d divides n} phi(n/d)*(-1)^omega(d). - Vladeta Jovovic, Sep 26 2002
A003557(n) | a(n). - R. J. Mathar, Mar 30 2011
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
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
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)
a(n) = Sum_{k=1..n} (-1)^omega(gcd(n,k)). - Ilya Gutkovskiy, Feb 22 2020
a(n) = Sum_{d1|n} Sum_{d2|n} mu(d1*d2)*floor(n/(d1*d2)). - Ridouane Oudra, Dec 31 2022
Comments