login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A058026 Number of positive integers, k, where k <= n and gcd(k,n) = gcd(k+1,n) = 1. 20
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

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.

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 * 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_{k=1..n} (-1)^omega(gcd(n,k)). - Ilya Gutkovskiy, Feb 22 2020

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)

-- Reinhard Zumkeller, May 10 2014

CROSSREFS

Cf. A070554, A069828, A027748, A124010, A289460.

Cf. A000010 (phi(n,0)), A002472 (phi(n,2)).

Sequence in context: A340525 A003966 A123931 * A004605 A347361 A175919

Adjacent sequences:  A058023 A058024 A058025 * A058027 A058028 A058029

KEYWORD

nonn,mult

AUTHOR

Leroy Quet, Nov 15 2000

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 1 19:37 EDT 2022. Contains 354974 sequences. (Running on oeis4.)