A036912 -id:A036912 - cp's OEIS frontend

A057635 a(n) is the largest m such that phi(m) = n, where phi is Euler's totient function = A000010, or a(n) = 0 if no such m exists.

2, 6, 0, 12, 0, 18, 0, 30, 0, 22, 0, 42, 0, 0, 0, 60, 0, 54, 0, 66, 0, 46, 0, 90, 0, 0, 0, 58, 0, 62, 0, 120, 0, 0, 0, 126, 0, 0, 0, 150, 0, 98, 0, 138, 0, 94, 0, 210, 0, 0, 0, 106, 0, 162, 0, 174, 0, 118, 0, 198, 0, 0, 0, 240, 0, 134, 0, 0, 0, 142, 0, 270, 0, 0, 0, 0, 0, 158, 0, 330, 0

Offset: 1

Jud McCranie, Oct 10 2000

nonn

To check that a property P holds for all EulerPhi(x) not exceeding n, for n with a(n) > 0, it suffices to check P for all EulerPhi(x) with x not exceeding a(n). - Joseph L. Pe, Jan 10 2002
The Alekseyev link in A131883 establishes the following explicit relationship between A131883, A036912 and A057635: for t belonging to A036912, we have t = A131883(A057635(t)-1). In other words, A036912(n) = A131883(A057635(A036912(n))-1) for all n.
From Jianing Song, Feb 16 2019: (Start)
Let f(n) = exp(gamma)*log(log(n)) + 2.5/log(log(n)), then a(n) < n*f(n^2) for all n > 1, where gamma = A001620.
Proof. Without loss of generality we suppose log(log(n)) > n_0 = sqrt(2.5/exp(gamma)) = 1.18475..., then f(n), n/f(n) and N(n) = ceiling(n*f(n^2)) are all monotonically increasing functions of n, and we have f(n) < 2*exp(gamma)*log(log(n)).
By the formula (3.41) in Theorem 15 by J. Barkley Rosser and Lowell Schoenfeld we have phi(k) > k/f(k) for k != 1, 2, 223092870. N(31802157) = 223092869 < 223092870, N(31802158) = 223092877 > 223092870, so N(n) != 223092870 (N(n) is increasing). So phi(N(n)) > N(n)/f(N(n)) > (n*f(n^2))/f(n*f(n^2)) (n/f(n) is increasing and log(log(n*f(n^2))) > n_0).
Note that f(n^2) < 2*exp(gamma)*log(log(n^2)) < 2*exp(gamma)*(log(n^2)/e) = 4*exp(gamma-1)*log(n) < 4*exp(gamma-2)*n < n, so n*f(n^2) < n^2, f(n*f(n^2)) < f(n^2) (f(n) is increasing and log(log(n*f(n^2))) > n_0), so phi(N(n)) > n. As a result, a(n) <= N(n) - 1 < n*f(n^2).
Conjecturally a(n) < n*f(n) for all n > 2. (End)

			m = 12 is the largest value of m such that phi(m) = 4, so a(4) = 12.

T. D. Noe, Table of n, a(n) for n = 1..10000
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1) (1962), 64-94.

Cf. A000010, A005277, A014197, A049283.

Cf. A006511 (largest k for which A000010(k) = A002202(n)).

a = Table[0, {100}]; Do[ t = EulerPhi[n]; If[t < 101, a[[t]] = n], {n, 1, 10^6}]; a

a(n) = if(n%2, 2*(n==1), forstep(k=floor(exp(Euler)*n*log(log(n^2))+2.5*n/log(log(n^2))), n, -1, if(eulerphi(k)==n, return(k)); if(k==n, return(0)))) \\ Jianing Song, Feb 15 2019

apply( {A057635(n,m=istotient(n))=if(!m, 0, n>1, m=log(log(n)*2); m=bitand(n*(exp(Euler)*m+2.5/m)\1,-2); while(eulerphi(m)!=n, m-=2); m, 2)}, [1..99]) \\ If n is known to be a totient, a nonzero 2nd arg can be given to avoid the check. - M. F. Hasler, Aug 13 2021

a(n) = invphiMax(n); \\ Amiram Eldar, Nov 14 2024 using Max Alekseyev's invphi.gp

a(2n+1) = 0 for n > 0, and a(2n) = 0 iff 2n is in A005277.

Edited and escape clause added to definition by M. F. Hasler, Aug 13 2021

A006511 Largest inverse of totient function (A000010): a(n) is the largest x such that phi(x) = m, where m = A002202(n) is the n-th number in the range of phi.

Original entry on oeis.org

2, 6, 12, 18, 30, 22, 42, 60, 54, 66, 46, 90, 58, 62, 120, 126, 150, 98, 138, 94, 210, 106, 162, 174, 118, 198, 240, 134, 142, 270, 158, 330, 166, 294, 276, 282, 420, 250, 206, 318, 214, 378, 242, 348, 354, 462, 254, 510, 262, 414, 274, 278, 426, 630, 298, 302

Offset: 1

N. J. A. Sloane

nonn

Always even, as phi(2n) = phi(n) when n is odd. - Alain Jacques (thegentleway(AT)bigpond.com), Jun 15 2006

J. W. L. Glaisher, Number-Divisor Tables. British Assoc. Math. Tables, Vol. 8, Camb. Univ. Press, 1940, p. 64.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=1..10000
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
Richard K. Guy, Letter to N. J. A. Sloane, Jun 1991.

Cf. A000010, A002202, A002181, A057826.

For records see A036913, A132154, A036912.

phiinv[n_, pl_] := Module[{i, p, e, pe, val}, If[pl=={}, Return[If[n==1, {1}, {}]]]; val={}; p=Last[pl]; For[e=0; pe=1, e==0||Mod[n, (p-1)pe/p]==0, e++; pe*=p, val=Join[val, pe*phiinv[If[e==0, n, n*p/pe/(p-1)], Drop[pl, -1]]]]; Sort[val]]; phiinv[n_] := phiinv[n, Select[1+Divisors[n], PrimeQ]]; Last/@Select[phiinv/@Range[1, 200], #!={}&] (* phiinv[n, pl] = list of x with phi(x)=n and all prime divisors of x in list pl. phiinv[n] = list of x with phi(x)=n *)

g(n) = if(n%2, 2*(n==1), forstep(k = floor(exp(Euler)*n*log(log(n^2))+2.5*n/log(log(n^2))), n, -1, if(eulerphi(k)==n, return(k)); if(k==n, return(0)))); \\ A057635
lista(nn) = for(m = 1, nn, if(istotient(m), print1(g(m), ", "))); \\ Jinyuan Wang, Aug 29 2019

lista(nmax) = my(s); for(n = 1, nmax, s = invphiMax(n); if(s > 0, print1(s, ", "))); \\ Amiram Eldar, Nov 14 2024, using Max Alekseyev's invphi.gp

use ntheory ":all"; my $k=1; for my $i (1..100) { my @v; do{@v=inverse_totient($k++)} until @v; print "$i $v[-1]\n"; } # Dana Jacobsen, Mar 04 2019

a(n) = A057635(A002202(n)). - T. D. Noe

A132154 Where records occur in A006511.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 10, 12, 15, 16, 17, 21, 27, 30, 32, 37, 46, 48, 54, 58, 64, 69, 80, 85, 98, 107, 112, 127, 138, 153, 179, 205, 219, 230, 257, 281, 306, 330, 361, 367, 379, 403, 427, 466, 477, 524, 571, 595, 619, 645, 689, 713, 737, 761, 806, 828, 875, 894, 963, 986, 1031

Offset: 1

N. J. A. Sloane, Nov 05 2007

nonn

Donovan Johnson, Table of n, a(n) for n = 1..500

Cf. A000010, A006511, A036913, A036912.

A131883 a(n) = the minimum value from among (phi(n+1),phi(n+2),phi(n+3),...,phi(2n)), where phi(m) (A000010) is the number of positive integers which are coprime to m and are <= m.

Original entry on oeis.org

1, 2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 6, 6, 6, 6, 6, 6, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 20, 20, 20, 20, 20, 20, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24

Offset: 1

Leroy Quet, Oct 24 2007

nonn

Conjecture: After omitting multiple occurrences we get A036912. - Vladeta Jovovic, Oct 31 2007. This conjecture has been established by Max Alekseyev - see link below.

The Alekseyev link establishes the following explicit relationship between A131883, A036912 and A057635. Namely, for t belonging to A036912, we have t=A131883(A057635(t)-1). In other words, A036912(n) = A131883(A057635(A036912(n))-1) for all n.

			For n = 6 we have phi(7)=6, phi(8)=4, phi(9)=6, phi(10)=4, phi(11)=10, phi(12)=4. The least of these values is 4. So a(6) = 4.

M. F. Hasler, Table of n, a(n) for n = 1..1000
Max Alekseyev, Proof of Jovovic's conjecture

A131883 := proc(n) min(seq(numtheory[phi](i),i=n+1..2*n)) ; end: seq(A131883(n),n=1..500) ; # R. J. Mathar, Nov 09 2007

Table[Min[Table[EulerPhi[i], {i, n + 1, 2*n}]], {n, 1, 80}] (* Stefan Steinerberger, Oct 30 2007 *)

A131883(n)=vecsort(vector(n,i,eulerphi(n+i)))[1]
vector(300,i,A131883(i)) \\ M. F. Hasler, Nov 04 2007

More terms from Stefan Steinerberger and R. J. Mathar, Oct 30 2007

A362231 a(n) = A047994(A362230(n)).

Original entry on oeis.org

1, 2, 4, 6, 8, 12, 20, 24, 32, 36, 44, 48, 72, 80, 96, 120, 128, 144, 176, 192, 216, 224, 240, 264, 288, 320, 336, 360, 368, 384, 416, 464, 480, 576, 768, 864, 960, 1056, 1280, 1344, 1440, 1536, 1728, 1920, 2016, 2208, 2400, 2496, 2688, 2784, 2880, 3168, 3360

Offset: 1

Amiram Eldar, Apr 12 2023

nonn

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

The unitary version of A036912.
Indices of records of A362229.
Cf. A047994, A361966, A362230.

s[n_] := If[(inv = invUPhi[n]) == {}, 0, Max[inv]]; seq[kmax_] := Module[{v = {}, s1, sm = 0}, Do[s1 = s[k]; If[s1 > sm, sm = s1; AppendTo[v, k]], {k, 1, kmax}]; v]; seq[3000] (* using the function invUPhi from A361966 *)

A362668 a(n) = A091732(A362667(n)).

Original entry on oeis.org

1, 2, 3, 4, 6, 8, 12, 16, 18, 20, 24, 36, 48, 60, 64, 72, 80, 90, 96, 108, 120, 128, 132, 144, 192, 240, 288, 360, 384, 432, 480, 528, 576, 648, 672, 720, 792, 864, 960, 1008, 1080, 1104, 1152, 1440, 1728, 1920, 2160, 2304, 2592, 2880, 3072, 3168, 3456, 3600, 3840

Offset: 1

Amiram Eldar, Apr 29 2023

nonn

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

The infinitary version of A036912.
Indices of records of A362666.
Cf. A091732, A362484, A362667.

s[n_] := If[(inv = invIPhi[n]) == {}, 0, Max[inv]]; seq[kmax_] := Module[{v = {}, s1, sm = 0}, Do[s1 = s[k]; If[s1 > sm, sm = s1; AppendTo[v, k]], {k, 1, kmax}]; v]; seq[4000] (* using the function invIPhi from A362484 *)

A219930 n such that phi(n) represents a new lower bound for the phi function.

Original entry on oeis.org

1, 3, 8, 14, 20, 36, 48, 66, 70, 96, 126, 132, 156, 240, 252, 300, 336, 450, 480, 540, 660, 690, 714, 870, 900, 1080, 1320, 1470, 1530, 1710, 1950, 2340, 2940, 2970, 3360, 3780, 4200, 4830, 5040, 5610, 5670, 5880, 6270, 7140, 7350, 7410, 8400, 9660, 9870

Offset: 1

Jon Perry, Dec 01 2012

nonn

Conjecture: If n is in the sequence, then the sequence contains an infinite number of multiples of n.
Conjecture: Except for 1 and 3, all members of the sequence are even. If n is odd, it cannot be squarefree.
Conjecture: There does not exist N such that for all n > N, a(n) is divisible by 30.
A036912 gives the values of the phi function at these n.

			phi(1)=1, and for n>=1, phi(n)>=1.
phi(3)=2, and for n>=3, phi(n)>=2.
phi(8)=4, and for n>=8, phi(n)>=4.
phi(14)=6, and for n>=14, phi(n)>=6.

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

Cf. A000010, A036912, A057635, A014197.

p = new Array();
p[0] = NaN;
p[1] = 2;
p[2] = 3;
mj = 2;
for (k = 3; k < 50000; k += 2) makeprimes(k);
function makeprimes(i) {
for (j = 2; j <= mj; j++)
if (i%p[j] == 0) return false;
p[++mj] = i;
return true;
}
function primeFactorize(n) {
var pf = new Array(), pc, pfc;
pf[0] = new Array();
pf[1] = new Array();
pc = 1;
pfc = -1;
while (n != 1) {
if (n%p[pc] == 0) {pfc++; pf[0][pfc] = p[pc]; pf[1][pfc] = 0;}
while (n%p[pc] == 0) {n /= p[pc]; pf[1][pfc]++;}
pc++;
}
return pf;
}
function phi(n) {
var f, i, v;
v = 1;
f = primeFactorize(n);
for (i = 0; i < f[0].length; i++) v *= Math.pow(f[0][i], f[1][i] - 1)*(f[0][i] - 1);
return v;
}
function isMin(arr, ik, k) {
var i, im;
im = true;
for (i = ik; i < arr.length; i++) if (arr[i] < k) {im = false; break;}
return im;
}
phiV = new Array();
for (k = 1; k < 50000; k++) phiV[k] = phi(k);
cm = 1;
for (n = 1; n < 3000; n++) if (phiV[n] > cm && isMin(phiV, n, phiV[n])) {cm = phiV[n]; document.write(n + ", ");}

nn = 8!; t = Table[EulerPhi[n], {n, nn}]; min = Infinity; t2 = {}; Do[If[t[[n]] <= min, AppendTo[t2, {n, t[[n]]}]; min = t[[n]]], {n, Length[t], 1, -1}]; t2 = Reverse[t2]; t3 = {}; mx = 0; Do[If[i[[2]] > mx, mx = i[[2]]; AppendTo[t3, i[[1]]]], {i, t2}]; t3 (* T. D. Noe, Dec 04 2012 *)

A253215 a(n) is the greatest positive integer m such that phi(m) <= n where phi is Euler's totient function.

Original entry on oeis.org

2, 6, 6, 12, 12, 18, 18, 30, 30, 30, 30, 42, 42, 42, 42, 60, 60, 60, 60, 66, 66, 66, 66, 90, 90, 90, 90, 90, 90, 90, 90, 120, 120, 120, 120, 126, 126, 126, 126, 150, 150, 150, 150, 150, 150, 150, 150, 210, 210, 210, 210, 210, 210, 210, 210

Offset: 1

Jean-François Alcover, Jan 08 2015

nonn

If all duplicates are removed the result is A036913. The indices where a(n) takes a new value are A036912. - Jeppe Stig Nielsen, Sep 28 2021

Jean-François Alcover, Table of n, a(n) for n = 1..1000
MathOverflow, The maximum of the preimage of [1,x] through Euler's totient function
Eric Weisstein's World of Mathematics, Totient Function
Wikipedia, Euler's totient function

Cf. A000010, A007614, A032447, A036912, A036913, A057635.

inversePhi[m_?EvenQ] := Module[{p, nmax, n, nn}, p = Select[Divisors[m]+1, PrimeQ]; nmax = m*Times @@ (p/(p-1)); n = m; nn = {}; While[n <= nmax, If[EulerPhi[n] == m, AppendTo[nn, n]]; n++]; nn]; a[1] = 2; a[n_?OddQ] := a[n-1]; a[n_] := a[n] = Module[{m}, m = inversePhi[n] // Max; If[m > a[n-1], m, a[n-1]]]; Table[a[n], {n, 1, 100}]

A066362 a(n) = least k > n such that phi(k) < phi(n), if such a k exists; otherwise a(n) = 0.

Original entry on oeis.org

0, 0, 0, 0, 6, 0, 8, 0, 10, 0, 12, 0, 14, 0, 18, 18, 18, 0, 20, 0, 22, 24, 24, 0, 26, 30, 28, 30, 30, 0, 32, 36, 34, 36, 36, 0, 38, 40, 40, 42, 42, 0, 44, 48, 46, 48, 48, 0, 50, 54, 52, 54, 54, 60, 56, 60, 58, 60, 60, 0, 62, 66, 64, 66, 66, 0, 68, 70, 70, 0, 72, 0, 74, 78, 76, 78, 78, 0

Offset: 1

Joseph L. Pe, Dec 20 2001

nonn

If a(n) = 0, then from n onwards, phi will not go below its value at n.

The first odd term in this sequence is a(314) = 315. - Franklin T. Adams-Watters, Oct 25 2006

			a(2) = 0 since there is no k > 2 for which phi(k) < 1 = phi(2). a(5) = 6 since for k = 6, phi(6) = 2 < 4 = phi(5).

Cf. A000010, A036912, A036913.

More terms from Franklin T. Adams-Watters, Oct 25 2006

A306371 Number of primitive roots of prime A103521(n).

Original entry on oeis.org

1, 2, 4, 6, 8, 12, 16, 20, 24, 32, 36, 40, 48, 64, 72, 80, 96, 120, 144, 160, 176, 200, 216, 240, 288, 320, 336, 384, 432, 448, 480, 576, 720, 768, 880, 960, 1056, 1200, 1280, 1344, 1440, 1664, 1680, 1728, 1920, 2112, 2208, 2304, 2400, 2592, 2784, 2880, 3072, 3456, 3840, 4224, 4320

Offset: 1

Jianing Song, Feb 11 2019

nonn

Numbers k in A008330 such that no numbers <= k occur later than k in A008330.

Different from A036912 since a(19) = 144 and A036912(19) = 128.

Cf. A103521.

Cf. also A103203, A121519.

b(n) = if(n==1, 2, floor(exp(Euler)*n*log(log(n^2))+2.5*n/log(log(n^2))));
f(p) = my(i=0); forprime(q=p+1, b(eulerphi(p-1))+1, i+=(eulerphi(q-1)<=eulerphi(p-1))); i;
forprime(p=2, 2e4, if(f(p)==0, print1(eulerphi(p-1), ", ")))

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

cp's OEIS Frontend

A057635 a(n) is the largest m such that phi(m) = n, where phi is Euler's totient function = A000010, or a(n) = 0 if no such m exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

Extensions

A006511 Largest inverse of totient function (A000010): a(n) is the largest x such that phi(x) = m, where m = A002202(n) is the n-th number in the range of phi.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Perl

Formula

A132154 Where records occur in A006511.

Views

Author

Keywords

Links

Crossrefs

A131883 a(n) = the minimum value from among (phi(n+1),phi(n+2),phi(n+3),...,phi(2n)), where phi(m) (A000010) is the number of positive integers which are coprime to m and are <= m.

Views

Author

Keywords

Comments

Examples

Links

Programs

Maple

Mathematica

PARI

Extensions

A362231 a(n) = A047994(A362230(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A362668 a(n) = A091732(A362667(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A219930 n such that phi(n) represents a new lower bound for the phi function.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

JavaScript

Mathematica

A253215 a(n) is the greatest positive integer m such that phi(m) <= n where phi is Euler's totient function.

Views

Author

Keywords

Comments