cp's OEIS Frontend

A053576 Smallest number whose Euler totient is divisible by 2^n.

%I A053576 #28 Sep 11 2017 20:49:10
%S A053576 1,3,5,15,17,51,85,255,257,771,1285,3855,4369,13107,21845,65535,65537,
%T A053576 196611,327685,983055,1114129,3342387,5570645,16711935,16843009,
%U A053576 50529027,84215045,252645135,286331153,858993459,1431655765,4294967295,8589934592,17179869184,34359738368,68719476736,137438953472,274877906944,549755813888,1099511627776
%N A053576 Smallest number whose Euler totient is divisible by 2^n.
%C A053576 n = 32 is the first place where this differs from A001317, since 2^32 + 1 is not prime. - _Mitch Harris_, May 02 2007
%C A053576 a(8589934592) is the first unknown term; it is 2^8589934593 if F(33) = 2^(2^33)+1 is composite or F(33) otherwise. - _Charles R Greathouse IV_, Jul 15 2013
%C A053576 a(n) is the only odd element of the set phi-1(2^n), the totient inverses of 2^n. All other elements are 2*a(n), and the even elements of phi-1(2^(n-1)) * 2. - _Torlach Rush_, Sep 05 2017
%H A053576 Charles R Greathouse IV, <a href="/A053576/b053576.txt">Table of n, a(n) for n = 0..3320</a>
%e A053576 1,2,4,8,...,131072 divide phi of 2,3,5,15,...,196611 = 3*65537 respectively.
%t A053576 With[{s = Array[EulerPhi, 10^6]}, Table[FirstPosition[s, _?(Divisible[#, 2^n] &)][[1]], {n, 0, 19}]] (* _Michael De Vlieger_, Sep 05 2017 *)
%o A053576 (PARI) a(n)={
%o A053576   if(n >= 8589934592 && valuation(n>>5,2)>27,
%o A053576     warning("Result is conjectural on the nonexistence of Fermat primes >= F(33).")
%o A053576   );
%o A053576   if(n>31,
%o A053576     return(2<<n)
%o A053576   );
%o A053576   n=binary(n);
%o A053576   prod(i=1,#n,(2^2^(i-1)+1)^n[#n+1-i])
%o A053576 }; \\ _Charles R Greathouse IV_, Jul 15 2013
%Y A053576 Cf. A000010, A003401, A001317, A045544, A058213, A058214, A058215.
%Y A053576 Not the same as A001317.
%K A053576 nonn
%O A053576 0,2
%A A053576 _Labos Elemer_, Jan 18 2000
%E A053576 More odd terms from _Jud McCranie_, Jan 25 2000