cp's OEIS Frontend

A039650 Prime reached by iterating f(x) = phi(x)+1 on n.

%I A039650 #19 Dec 11 2019 08:19:33
%S A039650 2,2,3,3,5,3,7,5,7,5,11,5,13,7,7,7,17,7,19,7,13,11,23,7,13,13,19,13,
%T A039650 29,7,31,17,13,17,13,13,37,19,13,17,41,13,43,13,13,23,47,17,43,13,13,
%U A039650 13,53,19,41,13,37,29,59,17,61,31,37,13,43,13,67,13,13,13,71,13,73,37,41
%N A039650 Prime reached by iterating f(x) = phi(x)+1 on n.
%C A039650 Or, a(n) = lim_k {s(k,n)} where s(k,n) is defined inductively on k by: s(1,n) = n; s(k+1,n) = 1 + phi(s(k,n)). - _Joseph L. Pe_, Apr 30 2002
%C A039650 Sequence A229487 gives the conjectured largest number that converges to prime(n). - _T. D. Noe_, Oct 17 2013
%C A039650 For n>1, phi(n) <= n-1, with equality iff n is prime. So the trajectory decreases until it hits a prime. So a(n) always exists. - _N. J. A. Sloane_, Sep 22 2017
%D A039650 Alexander S. Karpenko, Lukasiewicz Logics and Prime Numbers, Luniver Press, Beckington, 2006, p. 51.
%H A039650 T. D. Noe, <a href="/A039650/b039650.txt">Table of n, a(n) for n = 1..10000</a>
%e A039650 s(24,1) = 24, s(24,2) = 1 + phi(24) = 1 + 8 = 9, s(24,3) = 1 + phi(9) = 1 + 6 = 7, s(24,4) = 1 + phi(7) = 1 + 6 = 7,.... Therefore a(24) = lim_k {s(24,k)} = 7.
%p A039650 A039650 := proc(n)
%p A039650     local nitr,niitr ;
%p A039650     niitr := n ;
%p A039650     while true do:
%p A039650         nitr := 1+numtheory[phi](niitr) ;
%p A039650         if nitr = niitr then
%p A039650             return nitr ;
%p A039650         end if;
%p A039650         niitr := nitr ;
%p A039650     end do:
%p A039650 end proc:
%p A039650 seq(A039650(n),n=1..40) ; # _R. J. Mathar_, Dec 11 2019
%t A039650 f[n_] := FixedPoint[1 + EulerPhi[ # ] &, n]; Table[ f[n], {n, 1, 75}]
%Y A039650 Cf. A039649, A039650, A039651, A039652, A039653, A039654, A039655, A039656, A229487.
%K A039650 nonn
%O A039650 1,1
%A A039650 _David W. Wilson_