A067005 -id:A067005 - cp's OEIS frontend

A061026 Smallest number m such that phi(m) is divisible by n, where phi = Euler totient function A000010.

1, 3, 7, 5, 11, 7, 29, 15, 19, 11, 23, 13, 53, 29, 31, 17, 103, 19, 191, 25, 43, 23, 47, 35, 101, 53, 81, 29, 59, 31, 311, 51, 67, 103, 71, 37, 149, 191, 79, 41, 83, 43, 173, 69, 181, 47, 283, 65, 197, 101, 103, 53, 107, 81, 121, 87, 229, 59, 709, 61, 367, 311, 127, 85

Offset: 1

Melvin J. Knight (knightmj(AT)juno.com), May 25 2001

nonn

Conjecture: a(n) is odd for all n. Verified up to n <= 3*10^5. - Jianing Song, Feb 21 2021

The conjecture above is false because a(16842752) = 33817088; see A002181 and A143510. - Flávio V. Fernandes, Oct 08 2023

			a(48) = 65 because phi(65) = phi(5)*phi(13) = 4*12 = 48 and no smaller integer m has phi(m) divisible by 48.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
Ho-joo Lee and Gerald Myerson, Consecutive Integers Whose Totients Are Multiples of n: 10837, The American Mathematical Monthly, Vol. 110, No. 2 (Feb., 2003), pp. 158-159.
Pieter Moree and Hans Roskam, On an arithmetical function related to Euler's totient and the discriminator, Fib. Quart., Vol. 33, No. 4 (1995), pp. 332-340.
József Sándor, On the Euler minimum and maximum functions, Notes on Number Theory and Discrete Mathematics, Volume 15, 2009, Number 3, pp. 1-8.

Cf. A000010, A066674, A066675, A066676, A066678, A067005.
Cf. A233516, A233517 (records).
Cf. A005179 (analog for number of divisors), A070982 (analog for sum of divisors).

a = ConstantArray[1, 64]; k = 1; While[Length[vac = Rest[Flatten[Position[a, 1]]]] > 0, k++; a[[Intersection[Divisors[EulerPhi[k]], vac]]] *= k]; a  (* Ivan Neretin, May 15 2015 *)

a(n) = my(s=1); while(eulerphi(s)%n, s++); s;
vector(100, n, a(n))

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

Sequence is unbounded; a(n) <= n^2 since phi(n^2) is always divisible by n.
If n+1 is prime then a(n) = n+1.
a(n) = min{ k : phi(k) == 0 (mod n) }.
a(n) = a(2n) for odd n > 1. - Jianing Song, Feb 21 2021

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)).

A282160 Least k > 1 such that k*n is not a totient number.

Original entry on oeis.org

3, 7, 3, 17, 3, 15, 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, 9, 2, 5, 3, 5, 2, 109, 2, 5, 3, 2, 2, 3, 2, 85, 3, 3, 3, 61

Offset: 1

Altug Alkan, Feb 07 2017

nonn

First occurrence of odd k or zero if impossible: 0, 1, 10, 2, 66, 28, 56, 6, 4, 8, 5244, 460, 272, 0, 232, 64, 7788, 4180, 300, 348, 328, 12, etc. - Robert G. Wilson v, Feb 09 2017

			a(14) = 7 because 7 * 14 = 98 is not a totient number and 7 is the least number that is greater than 1 with this property.

Altug Alkan, Table of n, a(n) for n = 1..10000

Cf. A000010, A002202, A007617, A067005, A071615, A079695.

TotientQ[m_] := Select[ Range[m +1, 2m*Product[(1 - 1/(k*Log[k]))^(-1), {k, 2, DivisorSigma[0, m]}]], EulerPhi[#] == m &, 1] != {}; (* after Jean-François Alcover, May 23 2011 in A002202 *) f[n_] := Block[{k = 2}, While[ TotientQ[k*n], k++]; k]; Array[f, 84] (* Robert G. Wilson v, Feb 09 2017 *)

a(n) = my(k = 2); while (istotient(k*n), k++); k;

a(A079695(n)) = 2. - Michel Marcus, Feb 08 2017

A067006 Smallest number for which the totient is divisible by the n-th nontotient number, that is, the n-th term of A007617.

Original entry on oeis.org

7, 11, 29, 19, 23, 53, 29, 31, 103, 191, 43, 47, 101, 53, 81, 59, 311, 67, 103, 71, 149, 191, 79, 83, 173, 181, 283, 197, 101, 103, 107, 121, 229, 709, 367, 311, 127, 131, 269, 137, 139, 569, 293, 149, 151, 229, 463, 317, 163, 167, 1021, 173, 349, 179, 181, 547

Offset: 1

Labos Elemer, Dec 22 2001

nonn

			14 = A007617(7) is not totient of any other number, but phi(29) = 28 is divisible by 14 and 29 is the smallest number of which the totient is a multiple of 14, so a(7)=29.

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

Cf. A000010, A007617, A066674, A066675, A066676, A066677, A066678, A067005.

a(n) = min_{x : mod(phi(x), A007617(n)) = 0}. For all nontotient numbers x, q*x+1 is prime with large enough q and a divisor of phi(q*x+1) = q*x is x, the selected nontotient number. [Corrected by Sean A. Irvine, Nov 28 2023]

A302495 a(n) is the least k such that k * A005277(n) is a term of A002202.

Original entry on oeis.org

2, 2, 3, 5, 2, 5, 2, 2, 3, 2, 2, 3, 2, 2, 6, 3, 3, 2, 4, 2, 3, 3, 2, 6, 2, 3, 2, 3, 2, 3, 3, 3, 5, 2, 2, 3, 3, 3, 2, 3, 2, 4, 6, 3, 2, 2, 3, 2, 4, 3, 3, 2, 5, 2, 3, 2, 7, 2, 3, 2, 2, 3, 3, 4, 3, 3, 2, 2, 9, 2, 4, 2, 2, 2, 3, 2, 5, 2, 2, 3, 5, 6, 2, 12, 6, 2, 3, 3, 3, 3, 2, 3, 3, 2, 3, 2, 5, 3, 2, 3

Offset: 1

Torlach Rush, Jun 10 2018

nonn

This sequence maps non-totients to totients, a(n) * A005277(n) is not a term of A005277, rather it is a term of A002202.

Conjecture: Every k > 1 eventually appears in the sequence.

			a(1) = 2 because 2*A005277(1) = 2*14 = 28 is not a term of A005277.
a(3) = 3 because 3*A005277(3) = 3*34 = 102 is not a term of A005277.

Cf. A000010, A002202, A005277, A000027.

lista(nn) = {forstep(n=2, nn, 2, if (! istotient(n), my(k = 1); while (! istotient(k*n), k++); print1(k, ", ");););} \\ Michel Marcus, Jul 19 2018

a(n) = A067005(A005277(n)). - Michel Marcus, Jul 25 2018

More terms from Michel Marcus, Jul 19 2018

cp's OEIS Frontend

A061026 Smallest number m such that phi(m) is divisible by n, where phi = Euler totient function A000010.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Formula

A282160 Least k > 1 such that k*n is not a totient number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A067006 Smallest number for which the totient is divisible by the n-th nontotient number, that is, the n-th term of A007617.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A302495 a(n) is the least k such that k * A005277(n) is a term of A002202.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

Extensions