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

%I #61 May 26 2024 04:29:41

%S 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 101,53,81,29,59,31,311,51,67,103,71,37,149,191,79,41,83,43,173,69,

%U 181,47,283,65,197,101,103,53,107,81,121,87,229,59,709,61,367,311,127,85

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

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

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

%H 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 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 Pieter Moree and Hans Roskam, <a href="http://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 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 Sequence is unbounded; a(n) <= n^2 since phi(n^2) is always divisible by n.

%F If n+1 is prime then a(n) = n+1.

%F a(n) = min{ k : phi(k) == 0 (mod n) }.

%F a(n) = a(2n) for odd n > 1. - _Jianing Song_, Feb 21 2021

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

%o vector(100, n, a(n))

%o (Python)

%o from sympy import totient as phi

%o def a(n):

%o k = 1

%o while phi(k)%n != 0: k += 1

%o return k

%o print([a(n) for n in range(1, 65)]) # _Michael S. Branicky_, Feb 21 2021

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

%Y Cf. A233516, A233517 (records).

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

%K nonn

%O 1,2

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