A057635 -id:A057635 - cp's OEIS frontend

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.

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

A319928 Numbers k such that there is no other m such that (Z/mZ)* is isomorphic to (Z/kZ), where (Z/kZ) is the multiplicative group of integers modulo k.

Original entry on oeis.org

24, 32, 80, 96, 120, 128, 160, 168, 240, 252, 256, 264, 324, 384, 400, 408, 416, 456, 480, 504, 512, 544, 552, 640, 648, 672, 696, 768, 840, 928, 1040, 1088, 1128, 1272, 1280, 1312, 1320, 1360, 1408, 1416, 1504, 1536, 1632, 1696, 1704, 1840, 1848, 1896, 1920, 1992

Offset: 1

Jianing Song, Oct 03 2018

nonn

Numbers such that A317993(k) = 1.
To find such k, it's sufficient to check for A015126(k) <= m <= A028476(k).
This is a subsequence of A296233. As a result, all members in this sequence should not satisfy any congruence mentioned there. Specially, all terms here are divisible by 4.
There are only 218 terms <= 10000 and 396 terms <= 20000.

			(Z/24Z)* = C_2 X C_2 X C_2, and there is no other m such that (Z/mZ)* = C_2 X C_2 X C_2, so 24 is a term.
(Z/96Z)* = C_2 X C_2 X C_8, and there is no other m such that (Z/mZ)* = C_2 X C_2 X C_8, so 24 is a term.

Jianing Song, Table of n, a(n) for n = 1..396 (all terms <= 20000)
Wikipedia, Multiplicative group of integers modulo n

Cf. A015126, A028476, A057635, A296233, A317993.

b(n) = my(i=0, search_max = A057635(eulerphi(n))); for(j=eulerphi(n)+1, search_max, if(znstar(j)[2]==znstar(n)[2], i++)); i \\ search_max is the largest k such that phi(k) = phi(n). See A057635 for its program
isA319928(n) = if(n>2, b(n)==1, 0)

A362229 a(n) is the largest m such that uphi(m) = n, where uphi is the unitary totient function (A047994), or a(n) = 0 if no such m exists.

Original entry on oeis.org

2, 6, 4, 10, 0, 14, 8, 30, 0, 22, 0, 42, 0, 24, 16, 34, 0, 38, 0, 66, 0, 46, 0, 78, 0, 54, 0, 58, 0, 62, 32, 102, 0, 0, 0, 114, 0, 0, 0, 110, 0, 86, 0, 138, 0, 94, 0, 210, 0, 0, 0, 106, 0, 76, 0, 174, 0, 118, 0, 186, 0, 96, 64, 170, 0, 134, 0, 0, 0, 142, 0, 222

Offset: 1

Amiram Eldar, Apr 12 2023

nonn

			a(1) = 2 since there are two solutions to uphi(x) = 1: 1 and 2, and 2 is the larger of them.
a(6) = 14 since there are three solutions to uphi(x) = 6: 7, 12 and 14, and 14 is the largest of them.

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

The unitary version of A057635.

Cf. A047994, A347771 (positions of 0's), A361966, A362230 (record values), A362231 (indices of records).

a[n_] := If[(inv = invUPhi[n]) == {}, 0, Max[inv]]; Array[a, 100] (* using the function invUPhi from A361966 *)

a(A347771(n)) = 0.

A362666 a(n) is the largest m such that iphi(m) = n, where iphi is the infinitary totient function A091732, or a(n) = 0 if no such m exists.

Original entry on oeis.org

2, 6, 8, 10, 0, 24, 0, 30, 0, 22, 0, 42, 0, 0, 32, 54, 0, 56, 0, 66, 0, 46, 0, 120, 0, 0, 0, 58, 0, 96, 0, 102, 0, 0, 0, 168, 0, 0, 0, 110, 0, 86, 0, 138, 128, 94, 0, 216, 0, 0, 0, 106, 0, 152, 0, 174, 0, 118, 0, 264, 0, 0, 0, 270, 0, 184, 0, 0, 0, 142, 0, 312

Offset: 1

Amiram Eldar, Apr 29 2023

nonn

			a(1) = 2 since there are two solutions to iphi(x) = 1: 1 and 2, and 2 is the larger of them.
a(6) = 24 since there are four solutions to iphi(x) = 6: 7, 12, 14 and 24, and 24 is the largest of them.

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

The infinitary version of A057635.

Cf. A091732, A362484, A362486 (positions of 0's), A362667 (record values), A362668 (indices of records).

a[n_] := If[(inv = invIPhi[n]) == {}, 0, Max[inv]]; Array[a, 100] (* using the function invIPhi from A362484 *)

a(A362486(n)) = 0.

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}]

A316785 Numerator of an upper bound for the maximal element in phi^(-1)(n).

Original entry on oeis.org

2, 6, 6, 15, 10, 21, 14, 30, 18, 33, 22, 455, 26, 42, 30, 255, 34, 133, 38, 165, 42, 69, 46, 455, 50, 78, 54, 435, 58, 2387, 62, 255, 66, 102, 70, 319865, 74, 114, 78, 1353, 82, 301, 86, 345, 90, 141, 94, 7735, 98, 165, 102, 795, 106, 399, 110, 435, 114, 177, 118, 1892891

Offset: 1

Franz Vrabec, Jul 13 2018

A057635(n) <= a(n)/A316786(n).

			For n = 12, there are 5 primes p with (p-1)|12: p1 = 2, p2 = 3, p3 = 5, p4 = 7, and p5 = 13. The numerator of 12*(2/1)*(3/2)*(5/4)*(7/6)*(13/12) = 455/8 is a(12) = 455.

R. Coleman, Some remarks on Euler's totient function, HAL Id: hal-00718975, version 1, 2012.
H. Gupta, Euler's totient function and its inverse, Indian J. Pure Appl. Math., 12(1) (1981), 22-29.

Cf. A057635, A316786 (denominators).

with(numtheory): A316785 := proc(n) local d,N; N:=n; for d in divisors(n) do if is prime(d+1) then N := (N*(d+1))/(d) end if; end do; numer(N); end proc;

a[n_] := Block[{p = Select[Prime@ Range@ PrimePi[n + 1], Mod[n, # - 1] == 0 &]}, Numerator[n*Times @@ (p/(p - 1))]]; Array[a, 60] (* Robert G. Wilson v, Aug 01 2018 *)

a(n) = my(p=n); fordiv(n, d, if (isprime(d+1), p *= (d+1)/d)); numerator(p); \\ Michel Marcus, Jul 29 2018

Numerator of n*Product_{p prime, (p-1)|n} p/(p-1).

A316786 Denominator of an upper bound for the maximal element in phi^(-1)(n).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 8, 1, 1, 1, 4, 1, 2, 1, 2, 1, 1, 1, 4, 1, 1, 1, 4, 1, 20, 1, 2, 1, 1, 1, 1728, 1, 1, 1, 8, 1, 2, 1, 2, 1, 1, 1, 32, 1, 1, 1, 4, 1, 2, 1, 2, 1, 1, 1, 5760, 1, 1, 1, 1, 1, 44, 1, 1, 1, 10, 1, 62208, 1, 1, 1, 1, 1, 2, 1, 64, 1, 1, 1, 192, 1, 1, 1, 88, 1, 120, 1, 2, 1, 1, 1, 1536, 1, 1, 1, 8

Offset: 1

Franz Vrabec, Jul 13 2018

A057635(n) <= A316785(n)/a(n).

			For n = 12, there are 5 primes p with (p-1)|12: p1 = 2, p2 = 3, p3 = 5, p4 = 7, and p5 = 13. The denominator of 12*(2/1)*(3/2)*(5/4)*(7/6)*(13/12) = 455/8 is a(12) = 8.

Antti Karttunen, Table of n, a(n) for n = 1..5039
R. Coleman, Some remarks on Euler's totient function, HAL Id: hal-00718975, version 1, 2012.
H. Gupta, Euler's totient function and its inverse, Indian J. Pure Appl. Math., 12(1) (1981), 22-29.
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..100000

Cf. A057635, A316785 (numerators).

with(numtheory): A316786 := proc(n) local d,N; N:=n; for d in divisors(n) do if is prime(d+1) then N := (N*(d+1))/(d) end if; end do; denom(N); end proc;

a(n) = my(p=n); fordiv(n, d, if (isprime(d+1), p *= (d+1)/d)); denominator(p); \\ Michel Marcus, Jul 29 2018

Denominator of n*Product_{p prime, (p-1)|n} p/(p-1).

A320046 Largest k such that (Z/kZ)* is isomorphic to (Z/nZ)*.

Original entry on oeis.org

2, 2, 6, 6, 10, 6, 18, 12, 18, 10, 22, 12, 26, 18, 30, 30, 34, 18, 54, 30, 42, 22, 46, 24, 50, 26, 54, 42, 58, 30, 62, 32, 66, 34, 90, 42, 74, 54, 90, 60, 82, 42, 98, 66, 90, 46, 94, 60, 98, 50, 102, 90, 106, 54, 150, 84, 114, 58, 118, 60, 122, 62, 126, 102, 130, 66, 134, 102, 138, 90

Offset: 1

Jianing Song, Oct 04 2018

nonn

All terms are even because (Z/kZ)* is isomorphic to (Z/(2k)Z)* for odd k. Most terms are congruent to 2 modulo 4. Among the first 10000 terms there are 8980 ones congruent to 2 modulo 4.

			The solutions to (Z/kZ)* = C_6 are k = 7, 9, 14 and 18, so a(7) = a(9) = a(14) = a(18) = 18.
The solutions to (Z/kZ)* = C_2 X C_20 are k = 55, 75, 100, 110 and 150, so a(55) = a(75) = a(100) = a(110) = a(150) = 150.
The solutions to (Z/kZ)* = C_2 X C_12 are k = 35, 39, 45, 52, 70, 78 and 90, so a(35) = a(39) = a(45) = a(52) = a(70) = a(78) = a(90) = 90.

Jianing Song, Table of n, a(n) for n = 1..10000
Wikipedia, Multiplicative group of integers modulo n

Cf. A028476, A057635, A320045.

a(n) = if(abs(n)==1||abs(n)==2, 2, my(i=0, search_max = A057635(eulerphi(n))); for(j=eulerphi(n)+1, search_max, if(znstar(j)[2]==znstar(n)[2], i=j)); i) \\ search_max is the largest k such that phi(k) = phi(n). See A057635 for its program

n <= a(n) <= A028476(n).

A328411 Largest m such that (Z/mZ)* = C_2 X C_(2n), or 0 if no such m exists, where (Z/mZ)* is the multiplicative group of integers modulo m.

Original entry on oeis.org

12, 30, 42, 32, 66, 90, 0, 102, 114, 150, 138, 0, 0, 174, 198, 128, 0, 270, 0, 246, 294, 230, 282, 306, 0, 318, 324, 0, 354, 450, 0, 256, 414, 0, 426, 438, 0, 0, 474, 374, 498, 522, 0, 534, 594, 470, 0, 582, 0, 750, 618, 0, 642, 810, 726, 678, 0, 590, 0, 738, 0, 0, 762, 512

Offset: 1

Jianing Song, Oct 14 2019

nonn

It is sufficient to check all numbers in the range [A049283(4n), A057635(4n)] for m if 4n is a totient number.

If (Z/mZ)* is isomorphic to C_2 X C_(2k) for some k, let x be any element in (Z/mZ)* such that the multiplicative order of x is 2k and that x != -1, then {-1, x} generates (Z/mZ)*. For example, (Z/16Z)* = {+-1, +-3, +-9, +-11}, (Z/32Z)* = {+-1, +-3, +-9, +-27, +-17, +-19, +-25, +-11}.

			The solutions to (Z/mZ)* = C_2 X C_12 are m = 35, 39, 45, 52, 70, 78 and 90, the largest of which is 90, so a(6) = 90.

Wikipedia, Multiplicative group of integers modulo n

Cf. A062373, A328410 (largest m).

Cf. also A049283, A057635.

a(n) = my(r=4*n, N=floor(exp(Euler)*r*log(log(r^2))+2.5*r/log(log(r^2)))); forstep(k=N, r, -1, if(eulerphi(k)==r && lcm(znstar(k)[2])==r/2, return(k)); if(k==r, return(0)))

cp's OEIS Frontend

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

A319928 Numbers k such that there is no other m such that (Z/mZ)* is isomorphic to (Z/kZ)*, where (Z/kZ)* is the multiplicative group of integers modulo k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A362229 a(n) is the largest m such that uphi(m) = n, where uphi is the unitary totient function (A047994), or a(n) = 0 if no such m exists.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A362666 a(n) is the largest m such that iphi(m) = n, where iphi is the infinitary totient function A091732, or a(n) = 0 if no such m exists.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Links

Crossrefs

Programs

Mathematica

A316785 Numerator of an upper bound for the maximal element in phi^(-1)(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A316786 Denominator of an upper bound for the maximal element in phi^(-1)(n).

Views

Author

Keywords

A319928 Numbers k such that there is no other m such that (Z/mZ)* is isomorphic to (Z/kZ), where (Z/kZ) is the multiplicative group of integers modulo k.