OFFSET
1,4
COMMENTS
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]
From Jianing Song, Dec 14 2021: (Start)
a(1) should have been 0.
If 2n-1 is a prime Sierpiński number which is not a Fermat prime, then a(2n-1) = -1.
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.
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)
LINKS
T. D. Noe, Table of n, a(n) for n=1..1000
D. Bressoud, CNT.m Computational Number Theory Mathematica package.
FORMULA
a(n)=Min[{x; Card(InvPhi[(2n-1)*(2^x)])>0}]
EXAMPLE
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.
MAPLE
with(numtheory); [seq(nops(invphi(odd*2^i)), i=1..N)]; Position of first nonzero provides a[n] belonging to 2n-1 odd number.
MATHEMATICA
Needs["CNT`"]; Table[m=1; While[PhiInverse[n*2^m] == {}, m++], {n, 1, 200, 2}]
CROSSREFS
KEYWORD
nonn
AUTHOR
Labos Elemer, May 30 2002
EXTENSIONS
Escape clause added by Jianing Song, Dec 14 2021
STATUS
approved