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
Keywords
Examples
a(48) = 65 because phi(65) = phi(5)*phi(13) = 4*12 = 48 and no smaller integer m has phi(m) divisible by 48.
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.
Crossrefs
Programs
-
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 *)
-
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
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
Comments