cp's OEIS Frontend

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

%I A061026 #66 May 10 2025 23:14:35
%S A061026 1,3,7,5,11,7,29,15,19,11,23,13,53,29,31,17,103,19,191,25,43,23,47,35,
%T A061026 101,53,81,29,59,31,311,51,67,103,71,37,149,191,79,41,83,43,173,69,
%U A061026 181,47,283,65,197,101,103,53,107,81,121,87,229,59,709,61,367,311,127,85
%N A061026 Smallest number m such that phi(m) is divisible by n, where phi = Euler totient function A000010.
%C A061026 Conjecture: a(n) is odd for all n. Verified up to n <= 3*10^5. - _Jianing Song_, Feb 21 2021
%C A061026 The conjecture above is false because a(16842752) = 33817088; see A002181 and A143510. - _Flávio V. Fernandes_, Oct 08 2023
%H A061026 Amiram Eldar, <a href="/A061026/b061026.txt">Table of n, a(n) for n = 1..10000</a> (terms 1..1000 from T. D. Noe)
%H A061026 Ho-joo Lee and Gerald Myerson, <a href="http://www.jstor.org/stable/3647787">Consecutive Integers Whose Totients Are Multiples of n: 10837</a>, The American Mathematical Monthly, Vol. 110, No. 2 (Feb., 2003), pp. 158-159.
%H A061026 Pieter Moree and Hans Roskam, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/33-4/moree.pdf">On an arithmetical function related to Euler's totient and the discriminator</a>, Fib. Quart., Vol. 33, No. 4 (1995), pp. 332-340.
%H A061026 József Sándor, <a href="http://nntdm.net/volume-15-2009/number-3/01-08/">On the Euler minimum and maximum functions</a>, Notes on Number Theory and Discrete Mathematics, Volume 15, 2009, Number 3, pp. 1-8.
%F A061026 Sequence is unbounded; a(n) <= n^2 since phi(n^2) is always divisible by n.
%F A061026 If n+1 is prime then a(n) = n+1.
%F A061026 a(n) = min{ k : phi(k) == 0 (mod n) }.
%F A061026 a(n) = a(2n) for odd n > 1. - _Jianing Song_, Feb 21 2021
%e A061026 a(48) = 65 because phi(65) = phi(5)*phi(13) = 4*12 = 48 and no smaller integer m has phi(m) divisible by 48.
%t A061026 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 *)
%o A061026 (PARI) a(n) = my(s=1); while(eulerphi(s)%n, s++); s;
%o A061026 vector(100, n, a(n))
%o A061026 (Python)
%o A061026 from sympy import totient as phi
%o A061026 def a(n):
%o A061026   k = 1
%o A061026   while phi(k)%n != 0: k += 1
%o A061026   return k
%o A061026 print([a(n) for n in range(1, 65)]) # _Michael S. Branicky_, Feb 21 2021
%Y A061026 Cf. A000010, A066674, A066675, A066676, A066678, A067005.
%Y A061026 Cf. A233516, A233517 (records).
%Y A061026 Cf. A005179 (analog for number of divisors), A070982 (analog for sum of divisors).
%K A061026 nonn
%O A061026 1,2
%A A061026 Melvin J. Knight (knightmj(AT)juno.com), May 25 2001