A219428 -id:A219428 - cp's OEIS frontend

A340090 Dirichlet inverse of A219428, n - phi(n) - 1.

-1, 0, 0, -1, 0, -3, 0, -3, -2, -5, 0, -7, 0, -7, -6, -8, 0, -11, 0, -11, -8, -11, 0, -21, -4, -13, -8, -15, 0, -21, 0, -21, -12, -17, -10, -36, 0, -19, -14, -33, 0, -29, 0, -23, -20, -23, 0, -63, -6, -29, -18, -27, 0, -47, -14, -45, -20, -29, 0, -85, 0, -31, -26, -55, -16, -45, 0, -35, -24, -45, 0, -123, 0, -37

Offset: 1

Antti Karttunen, Jan 05 2021

sign

Antti Karttunen, Table of n, a(n) for n = 1..16384

Cf. A000010, A033987, A051953, A219428, A340094, A340140, A340197, A340198.

up_to = 2^14;
DirInverseCorrect(v) = { my(u=vector(#v)); u[1] = (1/v[1]); for(n=2, #v, u[n] = (-u[1]*sumdiv(n, d, if(dA219428(n) = (n - 1 - eulerphi(n));
v340090 = DirInverseCorrect(vector(up_to, n, A219428(n)));
A340090(n) = v340090[n];
\\ Or as:
A340090(n) = if(1==n, -1, sumdiv(n, d, if(dA219428(n/d)*A340090(d), 0)));

a(1) = -1, for n > 1, a(n) = Sum_{d|n, dA219428(n/d) * a(d).

A049559 a(n) = gcd(n - 1, phi(n)).

Original entry on oeis.org

1, 1, 2, 1, 4, 1, 6, 1, 2, 1, 10, 1, 12, 1, 2, 1, 16, 1, 18, 1, 4, 1, 22, 1, 4, 1, 2, 3, 28, 1, 30, 1, 4, 1, 2, 1, 36, 1, 2, 1, 40, 1, 42, 1, 4, 1, 46, 1, 6, 1, 2, 3, 52, 1, 2, 1, 4, 1, 58, 1, 60, 1, 2, 1, 16, 5, 66, 1, 4, 3, 70, 1, 72, 1, 2, 3, 4, 1, 78, 1, 2, 1, 82, 1, 4, 1, 2, 1, 88, 1, 18, 1, 4

Offset: 1

Labos Elemer, Dec 28 2000

nonn

For prime n, a(n) = n - 1. Question: do nonprimes exist with this property?
Answer: No. If n is composite then a(n) < n - 1. - Charles R Greathouse IV, Dec 09 2013
Lehmer's totient problem (1932): are there composite numbers n such that a(n) = phi(n)? - Thomas Ordowski, Nov 08 2015
a(n) = 1 for n in A209211. - Robert Israel, Nov 09 2015

			a(9) = 2 because phi(9) = 6 and gcd(8, 6) = 2.
a(10) = 1 because phi(10) = 4 and gcd(9, 4) = 1.

Richard K. Guy, Unsolved Problems in Number Theory, B37.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Lehmer's Totient Problem

Cf. A000010, A002322, A039766, A063994, A160595, A209211, A219428, A264012, A264024, A280262, A283656, A283872, A284089, A284440, A318827, A318829, A318830, A330747 (ordinal transform), A340195.

Cf. also A009195, A058515, A058663, A187730, A258409, A339964, A340071, A340081, A340087 for more or less analogous sequences.

[Gcd(n-1, EulerPhi(n)): n in [1..80]]; // Vincenzo Librandi, Oct 13 2018

seq(igcd(n-1, numtheory:-phi(n)), n=1..100); # Robert Israel, Nov 09 2015

Table[GCD[n - 1, EulerPhi[n]], {n, 93}] (* Michael De Vlieger, Nov 09 2015 *)

a(n)=gcd(eulerphi(n),n-1) \\ Charles R Greathouse IV, Dec 09 2013

from sympy import totient, gcd
print([gcd(totient(n), n - 1) for n in range(1, 101)]) # Indranil Ghosh, Mar 27 2017

a(p^m) = a(p) = p - 1 for prime p and m > 0. - Thomas Ordowski, Dec 10 2013
From Antti Karttunen, Sep 09 2018: (Start)
a(n) = A000010(n) / A160595(n) = A063994(n) / A318829(n).
a(n) = n - A318827(n) = A000010(n) - A318830(n).
(End)
a(n) = gcd(A000010(n), A219428(n)) = gcd(A000010(n), A318830(n)). - Antti Karttunen, Jan 05 2021

A219029 a(n) = n - 1 - phi(phi(n)).

Original entry on oeis.org

-1, 0, 1, 2, 2, 4, 4, 5, 6, 7, 6, 9, 8, 11, 10, 11, 8, 15, 12, 15, 16, 17, 12, 19, 16, 21, 20, 23, 16, 25, 22, 23, 24, 25, 26, 31, 24, 31, 30, 31, 24, 37, 30, 35, 36, 35, 24, 39, 36, 41, 34, 43, 28, 47, 38, 47, 44, 45, 30, 51, 44, 53, 50, 47, 48, 57, 46, 51, 48

Offset: 1

V. Raman, Nov 10 2012

sign

There are exactly n - 1 - phi(phi(n)) non-primitive roots for n, less than n, if n is prime.

a(n) will be the same as A219027(n) except when n is a member of A033949 or n = 1, i.e., n is not 2, 4, prime, power of a prime, twice a prime, or twice a prime power.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Cf. A008330 (number of primitive roots for the n-th prime).
Cf. A046144 (number of primitive roots for n).
Cf. A010554 (value of phi(phi(n))).
Cf. A219027, A219428.

[(n - 1 - EulerPhi(EulerPhi(n))): n in [1..70] ]; // Vincenzo Librandi, Jan 26 2013

Table[n - (EulerPhi[EulerPhi[n]] + 1), {n, 75}] (* Alonso del Arte, Nov 17 2012 *)

for(n=1,100,print1(n-1-eulerphi(eulerphi(n))","))

a(n) = n - 1 - A010554(n). - V. Raman, Nov 22 2012

A070164 Least number m such that cototient(m) - 1 = prime(n).

Original entry on oeis.org

9, 6, 10, 12, 18, 26, 34, 38, 36, 42, 48, 74, 82, 60, 72, 78, 84, 122, 134, 108, 146, 152, 164, 126, 194, 202, 206, 156, 150, 226, 192, 180, 198, 204, 222, 296, 266, 260, 328, 258, 252, 338, 288, 386, 270, 398, 340, 392, 452, 350, 342, 336, 482, 372, 514, 360

Offset: 1

Labos Elemer, Apr 26 2002

nonn

			prime(17) = 59, cototient(k) - 1 = 59 for k = 84, 100, 116 and 118, and the smallest is a(17) = 84.

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

Cf. A000010, A051953, A070162, A219428.

seq[lim_] := Module[{c = Table[n - EulerPhi[n] - 1, {n, 1, lim}], m}, m = PrimePi[Max[c]]; TakeWhile[Flatten[FirstPosition[c,#]& /@ Prime[Range[m]]], !MissingQ[#] &]]; seq[600] (* Amiram Eldar, Mar 17 2025 *)

list(len) = {my(v = vector(len), k = 2, c = 0, p, i); while(c < len, p = k - eulerphi(k) - 1; if(isprime(p), i = primepi(p); if(i <= len && v[i] == 0, v[i] = k; c++)); k++); v;} \\ Amiram Eldar, Mar 17 2025

a(n) = Min{x: A051953(x) - 1 = n-th prime}.

cp's OEIS Frontend

A340090 Dirichlet inverse of A219428, n - phi(n) - 1.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A049559 a(n) = gcd(n - 1, phi(n)).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

A219029 a(n) = n - 1 - phi(phi(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A070164 Least number m such that cototient(m) - 1 = prime(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula