cp's OEIS Frontend

A039654 a(n) = prime reached by iterating f(x) = sigma(x)-1 starting at n, or -1 if no prime is ever reached.

%I A039654 #74 Aug 08 2024 03:38:30
%S A039654 2,3,11,5,11,7,23,71,17,11,71,13,23,23,71,17,59,19,41,31,47,23,59,71,
%T A039654 41,71,71,29,71,31,167,47,53,47,233,37,59,71,89,41,167,43,83,167,71,
%U A039654 47,167,167,167,71,97,53,167,71,167,79,89,59,167,61,167,103,311,83,167,67
%N A039654 a(n) = prime reached by iterating f(x) = sigma(x)-1 starting at n, or -1 if no prime is ever reached.
%C A039654 It appears nearly certain that a prime is always reached for n>1.
%C A039654 Since sigma(n) > n for n > 1, and sigma(n) = n + 1 only for n prime, the iteration either reaches a prime and loops there, or grows indefinitely. - _Franklin T. Adams-Watters_, May 10 2010
%C A039654 Guy (2004) attributes this conjecture to Erdos. See Erdos et al. (1990). - _N. J. A. Sloane_, Aug 30 2017
%D A039654 Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004. See Section B41, p. 149.
%H A039654 Franklin T. Adams-Watters, <a href="/A039654/b039654.txt">Table of n, a(n) for n=2..10000</a>
%H A039654 Lucilla Baldini and Josef Eschgfäller, <a href="http://arxiv.org/abs/1609.01750">Random functions from coupled dynamical systems</a>, arXiv preprint arXiv:1609.01750 [math.CO], 2016. Mentions the conjecture.
%H A039654 Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, <a href="http://math.dartmouth.edu/~carlp/iterate.pdf">On the normal behavior of the iterates of some arithmetic functions</a>, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204.
%H A039654 Paul Erdos, Andrew Granville, Carl Pomerance and Claudia Spiro, <a href="/A000010/a000010_1.pdf">On the normal behavior of the iterates of some arithmetic functions</a>, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204. [Annotated copy with A-numbers]
%H A039654 Math Overflow discussion, <a href="http://mathoverflow.net/questions/181019/does-iterating-a-certain-function-related-to-the-sums-of-divisors-eventually-alw/181032#181032">Does iterating a certain function related to the sums of divisors eventually always result in a prime value?</a>
%H A039654 N. J. A. Sloane, Three (No, 8) Lovely Problems from the OEIS, Experimental Mathematics Seminar, Rutgers University, Oct 05 2017, <a href="https://vimeo.com/237029685">Part I</a>, <a href="https://vimeo.com/237030304">Part 2</a>, <a href="https://oeis.org/A290447/a290447_slides.pdf">Slides.</a> (Mentions this sequence)
%t A039654 f[n_]:=Plus@@Divisors[n]-1;Table[Nest[f,n,6],{n,2,5!}] (* _Vladimir Joseph Stephan Orlovsky_, Mar 10 2010 *)
%t A039654 f[n_] := DivisorSigma[1,n]-1; Table[FixedPoint[f,n], {n,2,100}] (* _T. D. Noe_, May 10 2010 *)
%o A039654 (PARI) a(n)=local(m);if(n<2,0,while((m=sigma(n)-1)!=n,n=m);n) \\ _Franklin T. Adams-Watters_, May 10 2010
%o A039654 (PARI) A039654(n)=n>1&&until(n==n=sigma(n)-1,);n \\ _M. F. Hasler_, Sep 25 2017
%Y A039654 Cf. A039655 (the number of steps needed), A039649, A039650, A039651, A039652, A039653, A039656, A291301, A291302, A291776, A291777.
%Y A039654 For records see A292112, A292113.
%Y A039654 Cf. A177343: number of times the n-th prime occurs in this sequence.
%Y A039654 Cf. A292874: least k such that a(k) = prime(n).
%K A039654 nonn
%O A039654 2,1
%A A039654 _David W. Wilson_
%E A039654 Contingency for no prime reached added by _Franklin T. Adams-Watters_, May 10 2010
%E A039654 Changed escape value from 0 to -1 to be consistent with several related sequences. - _N. J. A. Sloane_, Aug 31 2017