A058026 -id:A058026 - cp's OEIS frontend

A074722 a(n) = Sum_{d divides n} phi(n/d)*(-1)^bigomega(d).

1, 0, 1, 2, 3, 0, 5, 2, 5, 0, 9, 2, 11, 0, 3, 6, 15, 0, 17, 6, 5, 0, 21, 2, 17, 0, 13, 10, 27, 0, 29, 10, 9, 0, 15, 10, 35, 0, 11, 6, 39, 0, 41, 18, 15, 0, 45, 6, 37, 0, 15, 22, 51, 0, 27, 10, 17, 0, 57, 6, 59, 0, 25, 22, 33, 0, 65, 30, 21, 0, 69, 10, 71, 0, 17, 34, 45, 0, 77, 18, 41, 0

Offset: 1

Vladeta Jovovic, Sep 27 2002

a(n) = 0 if and only if n == 2 (mod 4). - Robert Israel, Jan 04 2017

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A000010, A001222, A008683, A058026, A206369.

f:= proc(n) uses numtheory; local d;
   add(phi(n/d)*(-1)^bigomega(d), d=divisors(n))
end proc:
map(f, [$1..100]); # Robert Israel, Jan 04 2017

f[d_] := EulerPhi[n/d] LiouvilleLambda[d]
Table[DivisorSum[n, f], {n, 1, 50}] (* Benedict W. J. Irwin, Jul 11 2018 *)
f[p_, e_] := 2*(-1)^(e + 1)*((-p)^(e + 1) - 1)/(p + 1) - p^e; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Oct 30 2022 *)

a(n) = sumdiv(n, d, eulerphi(n/d)*(-1)^bigomega(d)); \\ Michel Marcus, Jul 11 2018

Multiplicative with a(p^e) = 2*(-1)^(e+1)*((-p)^(e+1)-1)/(p+1)-p^e.
Dirichlet g.f.: zeta(2s)*zeta(s-1)/(zeta(s)^2). - Benedict W. J. Irwin, Jul 11 2018
Sum_{k=1..n} a(k) ~ n^2 / 5. - Vaclav Kotesovec, Feb 01 2019
a(n) = Sum_{k=1..n} (-1)^bigomega(gcd(n,k)). - Ilya Gutkovskiy, Feb 22 2020
Möbius transform of A206369: a(n) = Sum_{d|n} A008683(d) * A206369(n/d). - Amiram Eldar, Aug 28 2023

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

Original entry on oeis.org

1, 1, 3, 5, 3, 9, 11, 3, 15, 17, 5, 21, 15, 9, 27, 29, 9, 15, 35, 11, 39, 41, 9, 45, 35, 15, 51, 27, 17, 57, 59, 15, 33, 65, 21, 69, 71, 15, 45, 77, 27, 81, 45, 27, 87, 55, 29, 51, 95, 27, 99, 101, 15, 105, 107, 35, 111, 63, 33, 75, 99, 39, 75, 125, 41, 129, 85, 27, 135, 137

Offset: 0

Leroy Quet, Nov 15 2000

nonn

Amiram Eldar, Table of n, a(n) for n = 0..10000
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.

Bisection of A058026.

Cf. A065474.

A070554:=proc(n) local p, a:=2*n+1; for p in numtheory[factorset](2*n+1) do a:=a*(1-2/p) end do; a end proc: seq(A070554(n), n=0..100); # Ridouane Oudra, Aug 20 2024

f[p_, e_] := (p-2) * p^(e-1); a[0] = 1; a[n_] := Times @@ f @@@ FactorInteger[2*n+1]; Array[a, 100, 0] (* Amiram Eldar, Jun 22 2025 *)

a(n) = my(n = 2*n+1); n*prod(p=1, n, if (isprime(p) && !(n % p), (1-2/p), 1)); \\ Michel Marcus, Feb 02 2016

a(n) = {my(f = factor(2*n+1)); prod(i=1, #f~, (f[i,1]-2) * f[i,1]^(f[i,2]-1));} \\ Amiram Eldar, Jun 22 2025

a(n) = A058026(2*n+1). - Ridouane Oudra, Aug 20 2024

Sum_{k=0..n} a(k) ~ c * n^2, where c = 2 * A065474. - Amiram Eldar, Jun 22 2025

More terms from Sascha Kurz, Feb 02 2003

A069828 Sum of positive integers k for k <= n and gcd(k,n) = gcd(k+1,n).

Original entry on oeis.org

1, 0, 1, 0, 6, 0, 15, 0, 12, 0, 45, 0, 66, 0, 21, 0, 120, 0, 153, 0, 50, 0, 231, 0, 180, 0, 117, 0, 378, 0, 435, 0, 144, 0, 255, 0, 630, 0, 209, 0, 780, 0, 861, 0, 198, 0, 1035, 0, 840, 0, 375, 0, 1326, 0, 729, 0, 476, 0, 1653, 0, 1770, 0, 465, 0, 1056, 0, 2145, 0, 714, 0, 2415

Offset: 1

Vladeta Jovovic, Apr 29 2002

nonn

Cf. A058026, A065474, A070555.

f[p_, e_] := (p-2) * p^(e-1); a[1] = 1; a[n_] := ((n-1)/2) * Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, May 23 2025 *)

a(n) = if (n==1, 1, n*(n-1)/2*sumdiv(n, d, moebius(d)*numdiv(d)/d)) \\ Michel Marcus, Jun 17 2013

a(n) = if(n == 1, 1, my(f = factor(n)); ((n-1)*n/2) * prod(i = 1, #f~, (f[i,1]-2) / f[i,1])); \\ Amiram Eldar, May 23 2025

a(n) = (n*(n-1)/2)*Sum_{d|n} mu(d)*tau(d)/d, n > 1.
From Amiram Eldar, May 23 2025: (Start)
a(n) = (n-1)*A058026(n)/2 for n >= 2.
Sum_{k=1..n} a(k) ~ c * n^2 / 6, where c = A065474. (End)

A306408 a(n) = Sum_{d|n} (-1)^omega(n/d) * d.

Original entry on oeis.org

1, 1, 2, 1, 4, 2, 6, 1, 5, 4, 10, 2, 12, 6, 8, 1, 16, 5, 18, 4, 12, 10, 22, 2, 19, 12, 14, 6, 28, 8, 30, 1, 20, 16, 24, 5, 36, 18, 24, 4, 40, 12, 42, 10, 20, 22, 46, 2, 41, 19, 32, 12, 52, 14, 40, 6, 36, 28, 58, 8, 60, 30, 30, 1, 48, 20, 66, 16, 44, 24, 70, 5, 72

Offset: 1

Daniel Suteu, Apr 05 2019

If n is squarefree (A005117), then a(n) = A000010(n) where A000010 is the Euler totient function.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A058026, A065469, A076479, A206369.

with(numtheory): omega := n -> nops(factorset(n)):
seq(add((-1)^omega(n/d)*d, d in divisors(n)), n=1..100); # Ridouane Oudra, Nov 24 2019

f[p_, e_] := p^e - (p^e - 1)/(p - 1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, May 01 2020 *)

a(n) = sumdiv(n, d, (-1)^omega(n/d) * d);

a(n) = my(f=factor(n)); prod(k=1, #f~, f[k,1]^f[k,2] - (f[k,1]^f[k,2] - 1)/(f[k,1]-1));

a(n) = n * Sum_{d|n} A076479(d)/d.
Sum_{k=1..n} a(k) ~ A065469 * n*(n+1)/2.
Multiplicative with a(p^e) = p^e - (p^e - 1)/(p-1).
a(n) = Sum_{d|n} mu(d)*tau(d)*sigma(n/d). - Ridouane Oudra, Nov 24 2019
a(n) = Sum_{d|n} A058026(d). - Amiram Eldar, May 01 2020

A110358 Beginning with 3, the least prime which is the product of one or more previous terms + 2.

Original entry on oeis.org

3, 5, 7, 17, 19, 23, 37, 53, 59, 61, 71, 73, 97, 107, 109, 113, 163, 179, 181, 257, 293, 307, 347, 349, 359, 367, 373, 401, 439, 487, 491, 499, 547, 557, 631, 751, 773, 797, 853, 881, 883, 887, 907, 971, 1009, 1039, 1049, 1051, 1097, 1103, 1123, 1283, 1297

Offset: 1

Amarnath Murthy, Jul 23 2005

nonn

Conjecture: The sequence is infinite.

Subbarao & Yip prove that if there is an integer m such that the equation Phi_2(x) = m has a unique solution, where Phi_2 is the 2nd Schemmel totient function (A058026), then x == 0 (mod a(n)^2) for each term in this sequence. They conjectured an analog to Carmichael's conjecture, that this equation has no unique solution to any integer m, and prove that any counterexample to this conjecture is > 10^120000, a bound calculated from the first 10000 terms of this sequence. A proof that this sequence is infinite would prove the conjecture. - Amiram Eldar, Mar 25 2017

			After 3, 5 and 7 the next term is 3*5 + 2 = 17, then 17 + 2 = 19, then 3*7 + 2 = 23, then 5*7 + 2 = 37, etc.

Giovanni Resta, Table of n, a(n) for n = 1..10000
M. V. Subbarao and L. W. Yip, Carmichael's conjecture and some analogues, Théorie des nombres/Number Theory: Proceedings of the International Number Theory Conference held at Université Laval, July 5-18, 1987, Jean M. de Koninck and Claude Levesque, eds., Walter de Gruyter, 1989, pp. 928-941.

Cf. A058026.

L={3}; p=3; While[Length[L] < 100, p = NextPrime@p; If[SquareFreeQ[p - 2] && SubsetQ[L, First /@ FactorInteger[p - 2]], AppendTo[L, p]]]; L (* Giovanni Resta, Mar 25 2017 *)

More terms from John Pammer (jcp5027(AT)psu.edu), Oct 10 2005

Corrected and extended by Joshua Zucker, May 08 2006

A289835 Number of units u in Z/(2n-1)Z such that Phi(4,u) is a unit, where Phi is the cyclotomic polynomial.

Original entry on oeis.org

1, 2, 2, 6, 6, 10, 10, 4, 14, 18, 12, 22, 10, 18, 26, 30, 20, 12, 34, 20, 38, 42, 12, 46, 42, 28, 50, 20, 36, 58, 58, 36, 20, 66, 44, 70, 70, 20, 60, 78, 54, 82, 28, 52, 86, 60, 60, 36, 94, 60, 98, 102, 24, 106, 106, 68, 110, 44, 60, 84, 110, 76, 50, 126, 84

Offset: 1

Jordan Lenchitz, Michael Mueller, Tristan Phillips, Madison Wellen, Eric Jovinelly, Joshua Harrington, Jul 25 2017

If k is even, the number of units u in Z/kZ such that Phi(4,u) is a unit is zero.

Jordan Lenchitz, Table of n, a(n) for n = 1..1000

Cf. A058026, A289460.

m:=4 do for t from 1 to 1000 do n:=2*t-1: S:={}: for a from 0 to n-1 do if gcd(a,n)=1 and gcd(cyclotomic(m,a),n)=1 then S:={op(S),a}: fi: od: print(t,nops(S)): od: od:

a(n) = sum(k=0, 2*n-2, (gcd(2*n-1, k)==1) && (gcd(2*n-1, polcyclo(4, k))==1)); \\ Michel Marcus, Jul 29 2017

A290309 Number of units u in Z/nZ such that Phi(5,u) is a unit, where Phi is the cyclotomic polynomial.

Original entry on oeis.org

1, 1, 2, 2, 3, 2, 6, 4, 6, 3, 6, 4, 12, 6, 6, 8, 16, 6, 18, 6, 12, 6, 22, 8, 15, 12, 18, 12, 28, 6, 26, 16, 12, 16, 18, 12, 36, 18, 24, 12, 36, 12, 42, 12, 18, 22, 46, 16, 42, 15, 32, 24, 52, 18, 18, 24, 36, 28, 58, 12, 56, 26, 36, 32, 36, 12, 66, 32, 44, 18

Offset: 1

Tristan Phillips, Jordan Lenchitz, Michael Mueller, Madison Wellen, Eric Jovinelly, Joshua Harrington, Jul 27 2017

If n is a prime other than 5, then a(n) = n - 5 if n == 1 (mod 10), otherwise a(n) = n - 1. - Robert Israel, Jul 31 2017

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A058026 (with Phi(1,u) or Phi(2,u)), A289460 (with Phi(3,u)).

m:=5; T:=[]: for n from 1 to 100 do S:={}: for a from 0 to n-1 do if gcd(a,n)=1 and gcd(cyclotomic(m,a),n)=1 then S:={op(S),a}: fi: od: T:=[op(T),nops(S)]: od: print(T):

Table[Count[Range[n - 1], k_ /; And[CoprimeQ[k, n], CoprimeQ[Cyclotomic[5, k], n]]], {n, 70}] (* Michael De Vlieger, Jul 30 2017 *)

a(n) = sum(k=0, n-1, (gcd(n, k)==1) && (gcd(n, polcyclo(5, k))==1)); \\ Michel Marcus, Jul 29 2017

A290322 Sum modulo n of all units u in Z/nZ such that Phi(5,u) is a unit, where Phi is the cyclotomic polynomial.

Original entry on oeis.org

1, 0, 0, 4, 0, 0, 0, 0, 9, 1, 0, 0, 0, 3, 0, 0, 0, 0, 8, 0, 12, 0, 0, 20, 0, 0, 0, 0, 18, 1, 0, 24, 0, 14, 0, 0, 0, 0, 16, 1, 0, 0, 24, 9, 0, 0, 0, 0, 45, 0, 0, 0, 0, 14, 0, 0, 0, 0, 36, 1, 32, 0, 0, 13, 24, 0, 0, 0, 14, 1, 0, 0, 0, 15, 0, 28, 0, 0, 32, 0, 42, 0

Offset: 2

Joshua Harrington, Michael Mueller, Jordan Lenchitz, Tristan Phillips, Madison Wellen, Eric Jovinelly, Jul 27 2017

Conjecture: If n is divisible by 5 then a(n) > 0. - Robert Israel, Jan 23 2024

Robert Israel, Table of n, a(n) for n = 2..10000

Cf. A058026, A289460.

with(numtheory): m:=5: for n from 2 to 100 do S:={}: for a from 1 to n-1 do if gcd(a,n)=1 and gcd(cyclotomic(m,a),n)=1 then S:={op(S),a}: fi: od: print(sum(op(i,S),i=1..nops(S)) mod n): od:

Table[Mod[Total@ Select[Range[n - 1], CoprimeQ[#, n] && CoprimeQ[Cyclotomic[5, #], n] &], n], {n, 83}] (* Michael De Vlieger, Jul 29 2017 *)

a(n) = sum(k=0, n-1, k*((gcd(n, k)==1) && (gcd(n, polcyclo(5, k))==1))) % n; \\ Michel Marcus, Jul 29 2017

A332845 a(n) = (-1)^omega(n) * Sum_{k=1..n} (-1)^omega(n/gcd(n, k)), where omega = A001221.

Original entry on oeis.org

1, 0, 1, 2, 3, 0, 5, 6, 7, 0, 9, 2, 11, 0, 3, 14, 15, 0, 17, 6, 5, 0, 21, 6, 23, 0, 25, 10, 27, 0, 29, 30, 9, 0, 15, 14, 35, 0, 11, 18, 39, 0, 41, 18, 21, 0, 45, 14, 47, 0, 15, 22, 51, 0, 27, 30, 17, 0, 57, 6, 59, 0, 35, 62, 33, 0, 65, 30, 21, 0, 69, 42, 71

Offset: 1

Ilya Gutkovskiy, Feb 26 2020

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000010, A001221, A016825 (positions of 0's), A049060, A058026, A074722, A076479, A307868.

Table[(-1)^PrimeNu[n] Sum[(-1)^PrimeNu[n/GCD[n, k]], {k, 1, n}], {n, 1, 73}]
Table[(-1)^PrimeNu[n] Sum[(-1)^PrimeNu[d] EulerPhi[d], {d, Divisors[n]}], {n, 1, 73}]
f[p_, e_] := p^e - 2; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; s = Array[a, 100] (* Amiram Eldar, Nov 01 2022 *)

a(n) = (-1)^omega(n) * sum(k=1, n, (-1)^omega(n/gcd(n, k))); \\ Michel Marcus, Feb 26 2020

a(n) = {my(f = factor(n)); prod(i=1, #f~, f[i,1]^f[i,2] - 2); } \\ Amiram Eldar, Nov 01 2022

a(n) = (-1)^omega(n) * Sum_{d|n} (-1)^omega(d) * phi(d).
a(p) = p - 2, where p is prime.
From Amiram Eldar, Nov 01 2022: (Start)
Multiplicative with a(p^e) = p^e - 2.
Sum_{k=1..n} a(k) ~ c * n^2, where c = (1/2) * Product_{p prime} (1 - 2/(p*(p+1))) = A307868 / 2 = 0.2358403068... . (End)

A333569 a(n) = Sum_{d|n} (-1)^(bigomega(d) - omega(d)) * phi(n/d).

Original entry on oeis.org

1, 2, 3, 2, 5, 6, 7, 6, 7, 10, 11, 6, 13, 14, 15, 10, 17, 14, 19, 10, 21, 22, 23, 18, 23, 26, 23, 14, 29, 30, 31, 22, 33, 34, 35, 14, 37, 38, 39, 30, 41, 42, 43, 22, 35, 46, 47, 30, 47, 46, 51, 26, 53, 46, 55, 42, 57, 58, 59, 30, 61, 62, 49, 42, 65, 66, 67, 34, 69, 70, 71, 42, 73, 74, 69

Offset: 1

Ilya Gutkovskiy, Mar 26 2020

Moebius transform of A327668.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000010, A001221, A001222, A005117 (fixed points), A046660, A058026, A074722, A162511, A327666, A327668.

Table[Sum[(-1)^(PrimeOmega[d] - PrimeNu[d]) EulerPhi[n/d], {d, Divisors[n]}], {n, 1, 75}]
Table[Sum[(-1)^(PrimeOmega[GCD[n, k]] - PrimeNu[GCD[n, k]]), {k, 1, n}], {n, 1, 75}]
f[p_, e_] := If[e > 1, (p^e*(p^2+p-2) - 2*(-1)^e*p)/(p*(p + 1)), p]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a,100] (* Amiram Eldar, Nov 12 2022 *)

a(n) = sumdiv(n, d, (-1)^(bigomega(d) - omega(d)) * eulerphi(n/d)); \\ Michel Marcus, Mar 27 2020

a(n) = Sum_{k=1..n} (-1)^(bigomega(gcd(n,k)) - omega(gcd(n,k))).
a(n) = Sum_{d|n} mu(n/d) * A327668(d).
From Amiram Eldar, Nov 12 2022: (Start)
Multiplicative with a(p) = p, and a(p^e) = (p^e*(p^2+p-2) - 2*(-1)^e*p)/(p*(p+1)) for e>1.
Sum_{k=1..n} a(k) ~ c * n^2, where c = (1/5) * Product_{p prime} (1 + 2/p^2) = 0.4381740171... . (End)

cp's OEIS Frontend

A074722 a(n) = Sum_{d divides n} phi(n/d)*(-1)^bigomega(d).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A069828 Sum of positive integers k for k <= n and gcd(k,n) = gcd(k+1,n).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A306408 a(n) = Sum_{d|n} (-1)^omega(n/d) * d.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A110358 Beginning with 3, the least prime which is the product of one or more previous terms + 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A289835 Number of units u in Z/(2n-1)Z such that Phi(4,u) is a unit, where Phi is the cyclotomic polynomial.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

A290309 Number of units u in Z/nZ such that Phi(5,u) is a unit, where Phi is the cyclotomic polynomial.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica