%I #20 Jun 15 2018 22:09:45
%S 1,3,5,5,7,7,11,11,11,11,13,13,17,17,17,17,19,19,23,23,23,23,29,29,29,
%T 29,29,29,31,31,37,37,37,37,37,37,41,41,41,41,43,43,47,47,47,47,53,53,
%U 53,53,53,53,59,59,59,59,59,59,61,61,67,67,67,67,67,67,71,71,71,71,73
%N Least k such that phi(k) >= n.
%C Thinking of n as time, a(n) represents the first time phi catches up with i(n), where i is the identity function. a(n) - n can be seen as the lag of phi behind i at time n. The sequence of these lags begins 0 1 2 1 2 1 4 3 2 1 2 1 4 3 2 1 2 1 4 3 2 1
%C a(n) is the smallest number for which the reduced residue system (=RRS(a(n))) contains {1,2,...,n} as a subset; a(m) jumps at a(p)-1 and a(p) from value of p to nextprime(p); a(x)=p(n) holds {p(n-1)...p(n)-1}; p(n) is repeated p(n)-p(n-1) times. For n > 1, a(n) = p(Pi(n)+1), while a(1)=1. - _Labos Elemer_, May 14 2003
%H Harry J. Smith, <a href="/A066169/b066169.txt">Table of n, a(n) for n = 1..1000</a>
%F a(1) = 1 a(n) = p(s+1) for n in [p(s), p(s+1) - 1], where p(s) denotes the s-th prime.
%F For n > 1 a(n) = A007918(n+1). - _Benoit Cloitre_, May 04 2002
%F For n > 1, a(n) = A000040(A000720(n)+1), while a(1)=1. - _Labos Elemer_, May 14 2003
%e a(5) = 7 since phi(7) = 6 is at least 5 and 7 is the smallest k satisfying phi(k) is greater than or equal to 5.
%t a(1)=1; Table[Prime[PrimePi[w]+1], {w, 1, 100}]
%o (PARI) { for (n=1, 1000, k=1; while (eulerphi(k) < n, k++); write("b066169.txt", n, " ", k) ) } \\ _Harry J. Smith_, Feb 04 2010
%o (PARI) print1(n=1);n=2;forprime(p=3,31,while(n++<=p,print1(", "p));n--) \\ _Charles R Greathouse IV_, Oct 31 2011
%Y Cf. A000040, A000720, A057237.
%K nonn,easy
%O 1,2
%A _Joseph L. Pe_, Dec 13 2001
%E More terms from _Benoit Cloitre_, May 04 2002
|