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,2

Comments

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

Links

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.

Formula

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

Example

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

Mathematica

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

Prog

(PARI) a(n) = my(s=1); while(eulerphi(s)%n, s++); s;
vector(100, n, a(n))
(Python)
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

Crossrefs

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

Cf. A233516, A233517 (records).

Cf. A005179 (analog for number of divisors), A070982 (analog for sum of divisors).

Sequence in context: A357275 A254929 A066677 * A064632 A216487 A328984

Adjacent sequences: A061023 A061024 A061025 * A061027 A061028 A061029

Keyword

nonn

Author

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

Status

approved