|
%I #24 Dec 14 2021 22:53:02
%S 1,1,1,2,1,1,2,1,3,6,1,1,2,1,1,8,1,1,2,1,1,2,2,583,2,1,1,1,2,5,4,1,1,
%T 2,1,3,2,1,3,2,1,1,4,2,1,4,2,1,2,1,3,16,1,3,6,1,1,2,2,1,4,2,1,2,3,1,4,
%U 1,3,2,1,3,2,1,3,4,1,1,8,2,3,2,1,7,2,1,1,2,2,1,4,1,3,4,1,1,2,2,15,2,3,2
%N Smallest m such that (2n-1)*2^m is totient, that is, in A002202, or -1 if (2n-1)*2^m is never a totient.
%C When 2n-1 is the k-th prime, then a(n) = A040076(2n-1) = A046067(n) = A057192(k). [This is only partially correct. If 2n-1 = 2^2^m + 1 is a Fermat prime, then a(n) = min{2^m, A040076(2n-1)} if 2n-1 is not a Sierpiński number and a(n) = 2^m otherwise, since phi((2n-1)^2) = (2n-1)*2^m. For example, a(129) = 8 < A040076(257) = 279, a(32769) = 16 < A040076(65537) = 287. - _Jianing Song_, Dec 14 2021]
%C From _Jianing Song_, Dec 14 2021: (Start)
%C a(1) should have been 0.
%C If 2n-1 is a prime Sierpiński number which is not a Fermat prime, then a(2n-1) = -1.
%C Do there exists n such that 2n-1 is composite and that a(2n-1) = -1? It seems very unlikely that this will happen: Let 2n-1 = (a_1)^(e_1) * (a_2)^(e_2) * ... * (a_r)^(e_r) * (q_1)^(f_1) * (q_2)^(f_2) * ... * (q_s)^(f_s), where a_1, a_2, ..., a_r are distinct numbers that are not Fermat primes (a_i is not necessarily a prime), q_1, q_2, ..., q_s are distinct Fermat primes. If p_{i,1}, p_{i,2}, ..., p_{i,e_i} are distinct primes of the form 2^e * (a_i) + 1, then the odd part of phi((Product_{i=1..r, j=1..e_i} p_{i,j}) * (Product_{i=1..s} (q_s)^(1+f_s))) is 2n-1.
%C Therefore, if k is not a Sierpiński number implies that there are infinitely many e such that 2^e * k + 1 is prime, then a necessary condition for a(2n-1) = -1 is that: for every factorization 2n-1 = (u_1) * (u_2) * ... * (u_t) (u_i is not necessarily a prime, and (u_i)'s are not necessarily distinct), at least one u_i must be a Sierpiński number which is not a Fermat prime. In particular, 2n-1 itself must be a Sierpiński number. (End)
%H T. D. Noe, <a href="/A071628/b071628.txt">Table of n, a(n) for n=1..1000</a>
%H D. Bressoud, <a href="http://www.macalester.edu/~bressoud/books/CNT.m">CNT.m</a> Computational Number Theory Mathematica package.
%F a(n)=Min[{x; Card(InvPhi[(2n-1)*(2^x)])>0}]
%e n=52:2n-1=13, [seq(nops(invphi(103*2^i)),i=1..25)]; gives: [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,6,8,10,12,14,16,18,20]; nonzero appears first at position 16, so a(52)=16,since 6750208=103.2^16 is totient, while 3375104 is nontotient. n=24, 2n-1=47: the first nonempty InvPhi(47.2^i) set arises at i=a[24]=583, a very large number.
%p with(numtheory); [seq(nops(invphi(odd*2^i)),i=1..N)]; Position of first nonzero provides a[n] belonging to 2n-1 odd number.
%t Needs["CNT`"]; Table[m=1; While[PhiInverse[n*2^m] == {}, m++], {n,1,200,2}]
%Y Similar to but different from A046067. See also A058887, A057192.
%Y Cf. A000010, A002202, A007617, A076336 (Sierpiński numbers).
%K nonn
%O 1,4
%A _Labos Elemer_, May 30 2002
%E Escape clause added by _Jianing Song_, Dec 14 2021
|
