A061026 -id:A061026 - cp's OEIS frontend

A067005 Totient of A061026(n) divided by n.

1, 1, 2, 1, 2, 1, 4, 1, 2, 1, 2, 1, 4, 2, 2, 1, 6, 1, 10, 1, 2, 1, 2, 1, 4, 2, 2, 1, 2, 1, 10, 1, 2, 3, 2, 1, 4, 5, 2, 1, 2, 1, 4, 1, 4, 1, 6, 1, 4, 2, 2, 1, 2, 1, 2, 1, 4, 1, 12, 1, 6, 5, 2, 1, 2, 1, 4, 2, 2, 1, 8, 1, 4, 2, 2, 3, 6, 1, 4, 1, 2, 1, 2, 1, 12, 2, 4, 1, 2, 2, 6, 1, 4, 3, 2, 1, 4, 2, 2, 1

Offset: 1

Labos Elemer, Dec 22 2001

nonn

			n = 24: a(24) = 1 = phi(A061026(24))/24 = phi(35)/24 = 24/24;
n = 85: a(85) = 12 = phi(A061026(85))/85 = 1020/85.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Zak Seidov)

Cf. A000010, A061026, A066674, A066675, A066676, A066677, A066678.

Table[m = 1; While[! Divisible[Set[k, EulerPhi@ m], n], m++]; k/n, {n, 100}] (* Michael De Vlieger, Mar 18 2017 *)

for(n=1,100, s=1; while((e=eulerphi(s))%n>0, s++); print1(e/n ", ")); \\ Zak Seidov, Feb 22 2014

list(len) = {my(v = vector(len), c = 0, k = 1, e); while(c < len, e = eulerphi(k); fordiv(e, d, if(d <= len && v[d] == 0, v[d] = e/d; c++)); k++); v; } \\ Amiram Eldar, Mar 08 2025

from sympy.ntheory import totient
def k(n):
    m=1
    while totient(m)%n: m+=1
    return m
print([totient(k(n))//n for n in range(1, 101)]) # Indranil Ghosh, Mar 18 2017

a(n) = A000010(A061026(n))/n.

a(n) = A066678(n)/n. - Amiram Eldar, Mar 08 2025

A066677 Duplicate of A061026.

Original entry on oeis.org

1, 3, 7, 5, 11, 7, 29, 15, 19, 11, 23, 13, 53, 29, 31, 17, 103, 19, 191, 25, 43, 23, 47, 35

Offset: 1

dead

A233516 Where records occur in A061026, the smallest number m such that n divides phi(m), where phi is Euler's totient function.

Original entry on oeis.org

1, 2, 3, 5, 7, 13, 17, 19, 31, 59, 85, 109, 133, 167, 197, 227, 317, 389, 457, 521, 799, 859, 1153, 1163, 1637, 1861, 1997, 2053, 2633, 3011, 3167, 3721, 3833, 5227, 6637, 7213, 9199, 12919, 13259, 13469, 14263

Offset: 1

T. D. Noe, Feb 12 2014

nonn

Not all of these numbers are prime. The record values are in A233517.

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

Cf. A061026, A233517.

t2 = {{1, 1}}; Do[k = 1; While[Mod[EulerPhi[k], n] > 0, k++]; If[k > t2[[-1,2]], AppendTo[t2, {n, k}]; Print[{n, k}]], {n, 2, 10^3}]; Transpose[t2][[1]]

lista(cmax) = {my(v = vector(cmax), c = 0, k = 1, d, vm = 0); while(c < cmax, d = divisors(eulerphi(k)); for(i = 1, #d, if(d[i] <= cmax && v[d[i]] == 0, c++; v[d[i]] = k)); k++); for(i = 1, cmax, if(v[i] > vm, vm = v[i]; print1(i, ", ")));} \\ Amiram Eldar, May 26 2024

A233517 Record values in A061026, the smallest number m such that n divides phi(m), where phi is Euler's totient function.

Original entry on oeis.org

1, 3, 7, 11, 29, 53, 103, 191, 311, 709, 1021, 1091, 1597, 2339, 3547, 5449, 8243, 9337, 13711, 16673, 17579, 18899, 25367, 37217, 62207, 74441, 87869, 94439, 94789, 96353, 114013, 171167, 229981, 397253, 424769, 432781, 496747, 542599, 583397, 673451, 741677

Offset: 1

T. D. Noe, Feb 12 2014

nonn

See A233516 for the n that produce these values. After the initial 1, these numbers are prime.

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

Cf. A061026, A233516.

t2 = {{1, 1}}; Do[k = 1; While[Mod[EulerPhi[k], n] > 0, k++]; If[k > t2[[-1,2]], AppendTo[t2, {n, k}]; Print[{n, k}]], {n, 2, 10^3}]; Transpose[t2][[2]]

lista(cmax) = {my(v = vector(cmax), c = 0, k = 1, d, vm = 0); while(c < cmax, d = divisors(eulerphi(k)); for(i = 1, #d, if(d[i] <= cmax && v[d[i]] == 0, c++; v[d[i]] = k)); k++); for(i = 1, cmax, if(v[i] > vm, vm = v[i]; print1(v[i], ", ")));} \\ Amiram Eldar, May 26 2024

A341845 a(n) = A061026(2n): smallest k such that 2n divides phi(k), phi = A000010.

Original entry on oeis.org

3, 5, 7, 15, 11, 13, 29, 17, 19, 25, 23, 35, 53, 29, 31, 51, 103, 37, 191, 41, 43, 69, 47, 65, 101, 53, 81, 87, 59, 61, 311, 85, 67, 137, 71, 73, 149, 229, 79, 123, 83, 129, 173, 89, 181, 141, 283, 97, 197, 101, 103, 159, 107, 109, 121, 113, 229, 177, 709, 143

Offset: 1

Jianing Song, Feb 21 2021

nonn

A061026(n) = A061026(2n) for odd n > 1 since phi(m) is even for m >= 3. In this sequence the redundant values are omitted.
We have the obvious inequality A070846(n) >= A307437(n) >= a(n). For odd p = prime(k), A307437(p) = a(p), and if A341861(k) > 0 we have A070846(p) = a(p).
The smallest n such that A070846(n) > A307437(n) > a(n) is n = 40, where A070846(40) = 241, A307437(40) = 187 and a(40) = 123.

			a(12) = 35 since phi(35) = 24 is divisible by 2*12, and there is no m < 12 such that phi(m) is divisible by 2*12.
a(16) = 51 since phi(51) = 32 is divisible by 2*16, and there is no m < 16 such that phi(m) is divisible by 2*16.

Jianing Song, Table of n, a(n) for n = 1..20000

Cf. A061026, A000010, A070846, A307437, A341861.

a(n) = for(m=1, (2*n)^2, if(eulerphi(m)%(2*n)==0, return(m)))

from sympy import totient as phi
def a(n):
  k = 1
  while phi(k)%(2*n) != 0: k += 1
  return k
print([a(n) for n in range(1, 61)]) # Michael S. Branicky, Feb 21 2021

A002181 Least number k such that phi(k) = m, where m runs through the values (A002202) taken by phi.

Original entry on oeis.org

1, 3, 5, 7, 15, 11, 13, 17, 19, 25, 23, 35, 29, 31, 51, 37, 41, 43, 69, 47, 65, 53, 81, 87, 59, 61, 85, 67, 71, 73, 79, 123, 83, 129, 89, 141, 97, 101, 103, 159, 107, 109, 121, 113, 177, 143, 127, 255, 131, 161, 137, 139, 213, 185, 149, 151, 157, 187, 163, 249, 167, 203, 173

Offset: 1

N. J. A. Sloane

nonn

Inverse of Euler totient function.
A051445 without the zeros. The values of m are in A002180.
According to Guy, the first even term is for 2m = 16842752 = 257*2^16. If there are only five Fermat primes, then terms will be even for 2m = 2^r for all r > 31. This was discussed in problem E3361. - T. D. Noe, Aug 14 2008

J. W. L. Glaisher, Number-Divisor Tables. British Assoc. Math. Tables, Vol. 8, Camb. Univ. Press, 1940, p. 64.
R. K. Guy, Unsolved problems in number theory, B39.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
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
R. D. Carmichael, A table of the values of m corresponding to given values of phi(m), Amer. J. Math., 30 (1908), 394-400. [Annotated scanned copy]
T. D. Noe, Numbers Like 16842752.
William P. Wardlaw, L. L. Foster and R. J. Simpson, Problem E3361, Amer. Math. Monthly, Vol. 98, No. 5 (May, 1991), 443-444.
K. W. Wegner, Values of phi(x) = n for n from 2 through 1978, mimeographed manuscript, no date [Annotated scanned copy]

Cf. A058277, A006511, A002202, A061026.

With[{ep=EulerPhi[Range[1000]]},Flatten[Table[Position[ep,n,{1},1],{n,200}]]] (* Harvey P. Dale, Apr 10 2015 *)

a(n) = A061026(A002202(n)). - Flávio V. Fernandes, Oct 08 2023

Offset and initial term corrected Oct 07 2007

Revised definition from T. D. Noe, Aug 14 2008

A070982 Smallest integer k such that n divides sigma(k).

Original entry on oeis.org

1, 3, 2, 3, 8, 5, 4, 7, 10, 19, 43, 6, 9, 12, 8, 21, 67, 10, 37, 19, 20, 43, 137, 14, 149, 45, 34, 12, 173, 24, 16, 21, 86, 67, 76, 22, 73, 37, 18, 27, 163, 20, 257, 43, 40, 137, 281, 33, 52, 149, 101, 63, 211, 34, 109, 28, 49, 173, 353, 24, 169, 48, 32, 93, 72, 86, 401

Offset: 1

Benoit Cloitre, May 24 2002

Ivan Neretin, Table of n, a(n) for n = 1..10000
József Sándor, The sum-of-divisors minimum and maximum functions, Research Report Collection, Volume 8, Issue 1, 2005. See p. 3.

Right diagonal of A074625.

Cf. A005179 (analog for number of divisors), A061026 (analog for Euler totient).

a = ConstantArray[1, 67]; k = 1; While[Length[vac = Rest[Flatten[Position[a, 1]]]] > 0, k++; a[[Intersection[Divisors[DivisorSigma[1, k]], vac]]] *= k]; a (* Ivan Neretin, May 15 2015 *)
With[{dsk=Table[{k,DivisorSigma[1,k]},{k,500}]},Table[SelectFirst[ dsk, Divisible[#[[2]],n]&],{n,70}]][[All,1]] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Jan 04 2018 *)

PARI
```
a(n)=my(s); while(sigma(s++)%n, ); s
```

a(n) = min( k : sigma(k) == 0 mod(n) ).
Sum(k=1, n, a(k)) seems to be asymptotic to c*n^2 with probably 1.1 < c < 1.2.
By Xylouris' form of Linnk's theorem, a(n) << n^5. Can this be improved? - Charles R Greathouse IV, Mar 09 2017

A066678 Totients of the least numbers for which the totient is divisible by n.

Original entry on oeis.org

1, 2, 6, 4, 10, 6, 28, 8, 18, 10, 22, 12, 52, 28, 30, 16, 102, 18, 190, 20, 42, 22, 46, 24, 100, 52, 54, 28, 58, 30, 310, 32, 66, 102, 70, 36, 148, 190, 78, 40, 82, 42, 172, 44, 180, 46, 282, 48, 196, 100, 102, 52, 106, 54, 110, 56, 228, 58, 708, 60, 366, 310, 126, 64

Offset: 1

Labos Elemer, Dec 22 2001

nonn

From Alonso del Arte, Feb 03 2017: (Start)
One of the less obvious consequences of Dirichlet's theorem on primes in arithmetic progression is that this sequence is well-defined for all positive integers.
Suppose n is a nontotient (see A007617). Obviously a(n) != n. Dirichlet's theorem assures us that, if nothing else, there are infinitely many primes of the form nk + 1 for k positive (and in this case, k > 1). Then phi(nk + 1) = nk, suggesting a(n) = nk corresponding to the smallest k.
Of course not all a(n) are 1 less than a prime, such as 8, 20, 24, 54, etc. (End)

			a(23) = 46 because there is no solution to phi(x) = 23 but there are solutions to phi(x) = 46, like x = 47.
a(24) = 24 because there are solutions to phi(x) = 24, such as x = 35.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..5000 from Vincenzo Librandi)

Cf. A000010, A066674, A066675, A066676, A066677, A067005, A061026.

EulerPhi[mulTotientList = ConstantArray[1, 70]; k = 1; While[Length[vac = Rest[Flatten[Position[mulTotientList, 1]]]] > 0, k++; mulTotientList[[Intersection[Divisors[EulerPhi[k]], vac]]] *= k]; mulTotientList] (* Vincenzo Librandi Feb 04 2017 *)
a[n_] := For[k=1, True, k++, If[Divisible[t = EulerPhi[k], n], Return[t]]];
Array[a, 64] (* Jean-François Alcover, Jul 30 2018 *)

list(len) = {my(v = vector(len), c = 0, k = 1, e); while(c < len, e = eulerphi(k); fordiv(e, d, if(d <= len && v[d] == 0, v[d] = e; c++)); k++); v;} \\ Amiram Eldar, Mar 07 2025

def A066678(n):
    s = 1
    while euler_phi(s) % n: s += 1
    return euler_phi(s)
print([A066678(n) for n in (1..64)]) # Peter Luschny, Feb 05 2017

a(n) = A000010(A061026(n)).

A319048 a(n) is the greatest k such that A000010(k) divides n where A000010 is the Euler totient function.

Original entry on oeis.org

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

Offset: 1

Michel Marcus, Sep 09 2018

nonn

Sándor calls this function the totient maximum function and remarks that this function is well-defined, since a(n) can be at least 2, and cannot be greater than n^2 (when n > 6).

Antti Karttunen, Table of n, a(n) for n = 1..16384
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
József Sándor, On the Euler minimum and maximum functions, Notes on Number Theory and Discrete Mathematics, Volume 15, 2009, Number 3, Pages 1—8.

Cf. A000010 (Euler totient), A061026 (the totient minimum function).
Cf. A319068 (the analog for the sum of divisors).
Cf. A070633, also A057635, A057826, A069932, A071181.
Right border of A378638.

a[n_] := Module[{kmax = If[n <= 6, 10 n, n^2]}, For[k = kmax, True, k--, If[Divisible[n, EulerPhi[k]], Return[k]]]];
Array[a, 80] (* Jean-François Alcover, Sep 17 2018, from PARI *)

a(n) = {my(kmax = if (n<=6, 10*n, n^2)); forstep (k=kmax, 1, -1, if ((n % eulerphi(k)) == 0, return (k)););}

\\ (The first two functions could probably be combined in a smarter way):
A014197(n, m=1) = { n==1 && return(1+(m<2)); my(p, q); sumdiv(n, d, if( d>=m && isprime(d+1), sum( i=0, valuation(q=n\d, p=d+1), A014197(q\p^i, p))))} \\ From A014197 by M. F. Hasler
A057635(n) = if(1==n,2,if((n%2),0,my(k=A014197(n),i=n); if(!k, 0, while(k, i++; if(eulerphi(i)==n, k--)); (i))));
A319048(n) = { my(m=0); fordiv(n,d, m = max(m,A057635(d))); (m); }; \\ Antti Karttunen, Sep 09 2018

a(n) = {my(d = divisors(n)); vecmax(vector(#d, i, invphiMax(d[i])));} \\ Amiram Eldar, Nov 29 2024, using Max Alekseyev's invphi.gp

a(n) = Max_{d|n} A057635(d). - Antti Karttunen, Sep 09 2018

A338266 Least prime p such that p*n is not a totient number.

Original entry on oeis.org

3, 7, 3, 17, 3, 19, 2, 19, 3, 5, 3, 43, 2, 7, 3, 19, 2, 5, 2, 17, 3, 7, 3, 167, 2, 7, 3, 11, 3, 3, 2, 19, 3, 2, 3, 67, 2, 2, 3, 17, 3, 17, 2, 7, 2, 5, 2, 211, 2, 7, 3, 7, 3, 11, 3, 13, 2, 3, 2, 139, 2, 2, 3, 31, 3, 19, 2, 5, 3, 5, 2, 109, 2, 5, 3, 2, 2, 3, 2

Offset: 1

Bernard Schott, Oct 19 2020

nonn

Zhang Ming-Zhi has shown that for every positive integer n, there is a prime p such that p*n is not a totient (see Reference and link, theorem 1).

Differs from A282160, where multiplier p is not requested to be prime, for n = 6, 66, 80, 126, ... those indices where A282160(n) is not prime (see Example).

			a(6) = 19 because 19 * 6 = 114 is not a totient number and 19 is the least prime with this property. Also 15 * 6 = 90 is not either a totient number, so A282160(6) = 15 that is not a prime number.

Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section B36, p. 139.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Zhang Ming-Zhi, On Nontotients, J. Number Theory, Vol. 43, No. 2 (1993), pp. 168-172.

Cf. A000010, A002202, A061026, A071615, A079695, A282160.

a(n) = my(p=2); while (istotient(p*n), p = nextprime(p+1)); p; \\ Michel Marcus, Oct 19 2020

a(A079695(n)) = 2.

cp's OEIS Frontend

A067005 Totient of A061026(n) divided by n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Formula

A066677 Duplicate of A061026.

Views

Author

Keywords

A233516 Where records occur in A061026, the smallest number m such that n divides phi(m), where phi is Euler's totient function.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A233517 Record values in A061026, the smallest number m such that n divides phi(m), where phi is Euler's totient function.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A341845 a(n) = A061026(2n): smallest k such that 2n divides phi(k), phi = A000010.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

A002181 Least number k such that phi(k) = m, where m runs through the values (A002202) taken by phi.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A070982 Smallest integer k such that n divides sigma(k).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A066678 Totients of the least numbers for which the totient is divisible by n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs