|
%I #55 Oct 09 2023 19:24: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 T. D. Noe, <a href="/A061026/b061026.txt">Table of n, a(n) for n = 1..1000</a>
%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
|
