|
|
A058026
|
|
Number of positive integers, k, where k <= n and gcd(k,n) = gcd(k+1,n) = 1.
|
|
22
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,5
|
|
COMMENTS
|
Called the Schemmel totient function in the Handbook of Number Theory II. - R. J. Mathar, Apr 15 2011
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
This is the function phi(n, 1) in Alder. - Michel Marcus, Nov 14 2017
|
|
REFERENCES
|
József Sándor and Borislav Crstici, Handbook of Number theory II, Kluwer Academic Publishers, 2004, Chapter 3, p. 276.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{d divides n} phi(n/d)*(-1)^omega(d). - Vladeta Jovovic, Sep 26 2002
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 * Pi^2 * n^2 / 2, where c = A065474 = Product_{primes p} (1 - 2/p^2) = 0.32263409893924467057953169254823706657095... - Vaclav Kotesovec, Dec 18 2019
a(n) = Sum_{d1|n} Sum_{d2|n} mu(d1*d2)*floor(n/(d1*d2)). - Ridouane Oudra, Dec 31 2022
|
|
EXAMPLE
|
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.
|
|
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 *)
|
|
PROG
|
(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
(Haskell)
a058026 n = product $ zipWith (\p e -> p ^ (e - 1) * (p - 2))
(a027748_row n) (a124010_row n)
(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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,mult
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|