A039652 -id:A039652 - cp's OEIS frontend

A039649 a(n) = phi(n)+1.

2, 2, 3, 3, 5, 3, 7, 5, 7, 5, 11, 5, 13, 7, 9, 9, 17, 7, 19, 9, 13, 11, 23, 9, 21, 13, 19, 13, 29, 9, 31, 17, 21, 17, 25, 13, 37, 19, 25, 17, 41, 13, 43, 21, 25, 23, 47, 17, 43, 21, 33, 25, 53, 19, 41, 25, 37, 29, 59, 17, 61, 31, 37, 33, 49, 21, 67, 33, 45, 25, 71, 25, 73, 37, 41

Offset: 1

David W. Wilson

a(p) = p for p prime.
Records give A000040. - Omar E. Pol, Jul 10 2014
Which n are divisible by phi(n)+1? See A085118 for a possible answer and references. - Peter Munn, Jun 03 2021

Vincenzo Librandi, Table of n, a(n) for n = 1..10000
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)

Cf. A000010, A039650, A039651, A039652, A039653, A039654, A039655, A039656, A085118.

a039649 = (+ 1) . a000010  -- Reinhard Zumkeller, Oct 07 2015

[EulerPhi(n)+1: n in [1..100]]; // Vincenzo Librandi, Aug 13 2013

Table[EulerPhi[n] + 1, {n, 100}] (* Vincenzo Librandi, Aug 13 2013 *)

a(n)=eulerphi(n)+1 \\ Charles R Greathouse IV, Mar 04 2017

a(n) = A000010(n) + 1.
a(n) <= n for n > 1.
G.f.: x/(1 - x) + Sum_{k>=1} mu(k)*x^k/(1 - x^k)^2. - Ilya Gutkovskiy, Mar 16 2017

Edited by Charles R Greathouse IV, Mar 18 2010.

A039653 a(0) = 0; for n > 0, a(n) = sigma(n)-1.

Original entry on oeis.org

0, 0, 2, 3, 6, 5, 11, 7, 14, 12, 17, 11, 27, 13, 23, 23, 30, 17, 38, 19, 41, 31, 35, 23, 59, 30, 41, 39, 55, 29, 71, 31, 62, 47, 53, 47, 90, 37, 59, 55, 89, 41, 95, 43, 83, 77, 71, 47, 123, 56, 92, 71, 97, 53, 119, 71, 119, 79, 89, 59, 167, 61, 95, 103, 126, 83, 143, 67, 125, 95

Offset: 0

David W. Wilson

nonn

Call an integer k between 1 and n a "semi-divisor" of n if n leaves a remainder of 1 when divided by k, i.e., n == 1 (mod k). a(n) gives the sum of the semi-divisors of n+1. - Joseph L. Pe, Sep 11 2002

a(n) is also the sum of the strong divisors of n, for n >= 1. - Omar E. Pol, May 01 2015

Antti Karttunen, Table of n, a(n) for n = 0..10000
OEIS Wiki, Cyclotomic Polynomials at x=n, n! and sigma(n)

Cf. A000203, A039649, A039650, A039651, A039652, A039653, A039654, A039655, A039656, A032741.

[0] cat [DivisorSigma(1, n)-1: n in [1..100]]; // Vincenzo Librandi, May 02 2015

with(numtheory): A039653:=n->sigma(n)-1: (0, seq(A039653(n), n=1..100)); # Wesley Ivan Hurt, Jul 09 2015

Join[{0}, Table[DivisorSigma[1, n] - 1, {n, 90}]] (* Vincenzo Librandi, May 02 2015 *)

A039653(n) = if(!n,n,sigma(n)-1); \\ Antti Karttunen, May 26 2017

from sympy import divisor_sigma
def A039653(n): return divisor_sigma(n)-1 if n else 0 # Chai Wah Wu, Mar 14 2023

a(p) = p for p prime.
G.f.: -2*x^2/(Q(0) - 2*x^2 + 2*x), where Q(k) = (2*x^(k+2) - x - 1)*k - 1 - 2*x + 3*x^(k+2) - x*(k+3)*(k+1)*(1-x^(k+2))^2/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 16 2013
Let A(x) be the g.f. of A039653 and B(x) the g.f. of A155085. Then B(x) = 1/(1-x) + 1/(1-x)^2 + A(x)/x. - Sergei N. Gladkovskii, May 16 2013

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

Original entry on oeis.org

2, 3, 11, 5, 11, 7, 23, 71, 17, 11, 71, 13, 23, 23, 71, 17, 59, 19, 41, 31, 47, 23, 59, 71, 41, 71, 71, 29, 71, 31, 167, 47, 53, 47, 233, 37, 59, 71, 89, 41, 167, 43, 83, 167, 71, 47, 167, 167, 167, 71, 97, 53, 167, 71, 167, 79, 89, 59, 167, 61, 167, 103, 311, 83, 167, 67

Offset: 2

David W. Wilson

nonn

It appears nearly certain that a prime is always reached for n>1.
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
Guy (2004) attributes this conjecture to Erdos. See Erdos et al. (1990). - N. J. A. Sloane, Aug 30 2017

Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004. See Section B41, p. 149.

Franklin T. Adams-Watters, Table of n, a(n) for n=2..10000
Lucilla Baldini and Josef Eschgfäller, Random functions from coupled dynamical systems, arXiv preprint arXiv:1609.01750 [math.CO], 2016. Mentions the conjecture.
Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204.
Paul Erdos, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204. [Annotated copy with A-numbers]
Math Overflow discussion, Does iterating a certain function related to the sums of divisors eventually always result in a prime value?
N. J. A. Sloane, Three (No, 8) Lovely Problems from the OEIS, Experimental Mathematics Seminar, Rutgers University, Oct 05 2017, Part I, Part 2, Slides. (Mentions this sequence)

Cf. A039655 (the number of steps needed), A039649, A039650, A039651, A039652, A039653, A039656, A291301, A291302, A291776, A291777.
For records see A292112, A292113.
Cf. A177343: number of times the n-th prime occurs in this sequence.
Cf. A292874: least k such that a(k) = prime(n).

f[n_]:=Plus@@Divisors[n]-1;Table[Nest[f,n,6],{n,2,5!}] (* Vladimir Joseph Stephan Orlovsky, Mar 10 2010 *)
f[n_] := DivisorSigma[1,n]-1; Table[FixedPoint[f,n], {n,2,100}] (* T. D. Noe, May 10 2010 *)

a(n)=local(m);if(n<2,0,while((m=sigma(n)-1)!=n,n=m);n) \\ Franklin T. Adams-Watters, May 10 2010

A039654(n)=n>1&&until(n==n=sigma(n)-1,);n \\ M. F. Hasler, Sep 25 2017

Contingency for no prime reached added by Franklin T. Adams-Watters, May 10 2010

Changed escape value from 0 to -1 to be consistent with several related sequences. - N. J. A. Sloane, Aug 31 2017

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

Original entry on oeis.org

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, 29, 7, 31, 17, 13, 17, 13, 13, 37, 19, 13, 17, 41, 13, 43, 13, 13, 23, 47, 17, 43, 13, 13, 13, 53, 19, 41, 13, 37, 29, 59, 17, 61, 31, 37, 13, 43, 13, 67, 13, 13, 13, 71, 13, 73, 37, 41

Offset: 1

David W. Wilson

nonn

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
Sequence A229487 gives the conjectured largest number that converges to prime(n). - T. D. Noe, Oct 17 2013
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

			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.

Alexander S. Karpenko, Lukasiewicz Logics and Prime Numbers, Luniver Press, Beckington, 2006, p. 51.

T. D. Noe, Table of n, a(n) for n = 1..10000

Cf. A039649, A039650, A039651, A039652, A039653, A039654, A039655, A039656, A229487.

A039650 := proc(n)
    local nitr,niitr ;
    niitr := n ;
    while true do:
        nitr := 1+numtheory[phi](niitr) ;
        if nitr = niitr then
            return nitr ;
        end if;
        niitr := nitr ;
    end do:
end proc:
seq(A039650(n),n=1..40) ; # R. J. Mathar, Dec 11 2019

f[n_] := FixedPoint[1 + EulerPhi[ # ] &, n]; Table[ f[n], {n, 1, 75}]

A039655 Number of iterations of f(x) = sigma(x)-1 applied to n required to reach a prime, or -1 if no prime is ever reached.

Original entry on oeis.org

0, 0, 2, 0, 1, 0, 2, 5, 1, 0, 4, 0, 1, 1, 2, 0, 2, 0, 1, 1, 2, 0, 1, 2, 1, 3, 2, 0, 1, 0, 5, 1, 1, 1, 2, 0, 1, 2, 1, 0, 4, 0, 1, 5, 1, 0, 2, 4, 2, 1, 1, 0, 3, 1, 3, 1, 1, 0, 1, 0, 4, 1, 2, 1, 2, 0, 3, 4, 2, 0, 2, 0, 1, 2, 1, 4, 1, 0, 2, 2, 3, 0, 1, 1, 1, 3, 1, 0, 1, 2, 1, 1, 2, 3, 1, 0, 3, 2, 2, 0, 2, 0, 2, 1, 2

Offset: 2

David W. Wilson

nonn

Charles R Greathouse IV, Table of n, a(n) for n = 2..10000
MathOverflow, Does iterating a certain function related to the sums of divisors eventually always result in a prime value?, 2014
Hugo Pfoertner, Terms a(2)...a(1000000).
N. J. A. Sloane, Three (No, 8) Lovely Problems from the OEIS, Experimental Mathematics Seminar, Rutgers University, Oct 05 2017, Part I, Part 2, Slides. (Mentions this sequence)

Cf. A039654, A039649, A039650, A039651, A039652, A039653, A039655, A039656.

For records see A292114 and A292115.

f[n_] := Plus @@ Divisors@n - 1; g[n_] := Length@ NestWhileList[ f@# &, n, !PrimeQ@# &] - 1; Table[ g@n, {n, 2, 106}] (* Robert G. Wilson v, May 07 2010 *)

a(n)=my(t);while(!isprime(n),n=sigma(n)-1;t++);t \\ Charles R Greathouse IV, Sep 16 2014

Escape clause added by N. J. A. Sloane, Aug 31 2017

A039651 Number of iterations of f(x) = phi(x)+1 on n required to reach a prime.

Original entry on oeis.org

1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 2, 2, 0, 1, 0, 2, 1, 1, 0, 2, 2, 1, 1, 1, 0, 2, 0, 1, 2, 1, 3, 1, 0, 1, 3, 1, 0, 1, 0, 2, 3, 1, 0, 1, 1, 2, 3, 3, 0, 1, 1, 3, 1, 1, 0, 1, 0, 1, 1, 3, 2, 2, 0, 3, 4, 3, 0, 3, 0, 1, 1, 1, 1, 3, 0, 3, 2, 1, 0, 3, 3, 1, 2, 1, 0, 3, 1, 4, 1, 1, 1, 3, 0, 1, 1, 1, 0, 3, 0, 2, 2

Offset: 1

David W. Wilson

nonn

T. D. Noe, Table of n, a(n) for n = 1..1000

Cf. A039649, A039650, A039651, A039652, A039653, A039654, A039655, A039656.

Table[Length[NestWhileList[EulerPhi[#] + 1 &, n, UnsameQ, All]] - 2, {n, 100}] (* T. D. Noe, Oct 17 2013 *)

A039656 Becomes prime after n iterations of f(x) = sigma(x)-1 (least inverse of A039655).

Original entry on oeis.org

2, 6, 4, 27, 12, 9, 121, 301, 930, 484, 578, 441, 1273, 468, 4863, 3171, 9216, 8373, 19692, 19416, 25442, 13440, 19230, 16641, 16804, 83161, 100652, 226181, 203400, 133200, 419248, 380979, 744796, 553296, 634710, 539476, 505584, 674416, 634206

Offset: 0

David W. Wilson

nonn

Records: 2, 6, 27, 121, 301, 930, 1273, 4863, 9216, 19692, 25442, 83161, 100652, 226181, 419248, 744796, 3739690, 4238314, etc. - Robert G. Wilson v, Sep 23 2017
Indices of records: 0, 1, 3, 6, 7, 8, 12, 14, 16, 18, 20, 25, 26, 27, 30, 32, 46, 47, 48, 49, 50, 56, 57, 58, 59, 61, 63, 65, 67, 76, 77, 78, 82, 83, 84, 85, etc. - Robert G. Wilson v, Sep 23 2017
Checked through a(138)=60780636903. - Hugo Pfoertner, Nov 15 2017

Hugo Pfoertner, Table of n, a(n) for n = 0..138 (terms up to 66 from David W. Wilson, 67-100 from Robert G. Wilson v and Charles R Greathouse IV).

Cf. A039649, A039650, A039651, A039652, A039653, A039654, A039655, A292114, A292115.

f[n_] := Plus @@ Divisors@ n -1; g[n_] := Length@ NestWhileList[f@# &, n, !PrimeQ@# &] - 1; t[] := -1; k = 2; While[k < 10000001, a = g[k]; If[ t@ a == -1, t@ a = k; Print[{a, k}]]; k++]; t@# & /@ Range[0, 50] (* _Robert G. Wilson v, Sep 22 2017 *)

A175177 Conjectured number of numbers for which the iteration x -> phi(x) + 1 terminates at prime(n). Cardinality of rooted tree T_p (where p is n-th prime) in Karpenko's book.

Original entry on oeis.org

2, 3, 4, 9, 2, 31, 6, 4, 2, 2, 2, 11, 24, 41, 2, 2, 2, 57, 2, 2, 58, 2, 2, 6, 17, 4, 2, 2, 39, 67, 2, 2, 2, 2, 2, 2, 25, 4, 2, 2, 2, 158, 2, 61, 2, 2, 2, 2, 2, 2, 54, 2, 186, 2, 10, 2, 2, 2, 18, 8, 2, 2, 2, 2, 96, 2, 2, 18, 2, 6, 15, 2, 2, 2, 2, 2, 2, 44, 34, 6, 2, 16, 2, 105, 2, 2, 60, 5, 4, 2, 2, 2, 4

Offset: 1

Artur Jasinski, Mar 01 2010

nonn

			a(3) = 4 because x = { 5, 8, 10, 12 } are the 4 numbers from which the iteration x -> phi(x) + 1 terminates at prime(3) = 5.
a(4) = 8 because x = { 7, 9, 14, 15, 16, 18, 20, 24, 30 } are the 9 numbers from which the iteration x -> phi(x) + 1 terminates at prime(4) = 7.

Richard K. Guy, Unsolved Problems in Number Theory, Third Edition, Springer, New York 2004. Chapter B41, Iterations of phi and sigma, page 148.
A. S. Karpenko, Lukasiewicz's Logics and Prime Numbers, (English translation), 2006. See Table 2 on p.125 ff.
A. S. Karpenko, Lukasiewicz's Logics and Prime Numbers, (Russian), 2000.

Hugo Pfoertner, Table of n, a(n) for n = 1..1000

Cf. A039649, A039650, A039651, A039652, A096827, A175178.

iterat(x) = {my(k,s); if ( isprime(x),return(x)); s=x;
for (k=1,1000000000,s=eulerphi(s)+1;if(isprime(s),return(s)));
return(s); }
check(y,endrange) = {my(count,start); count=0;
for(start=1,endrange,if(iterat(start)==y,count++;));
return(count); }
for (n=1,93,x=prime(n);print1(check(x,1000000),", "))
\\ Hugo Pfoertner, Sep 23 2017

Name clarified by Hugo Pfoertner, Sep 23 2017

A229487 Conjectured greatest number that converges to prime(n) under the iteration x -> phi(x) + 1, where phi is Euler's totient function.

Original entry on oeis.org

2, 6, 12, 30, 22, 138, 60, 54, 46, 58, 62, 174, 498, 510, 94, 106, 118, 4314, 134, 142, 1038, 158, 166, 276, 420, 250, 206, 214, 750, 1758, 254, 262, 274, 278, 298, 302, 1182, 486, 334, 346, 358, 6360, 382, 1614, 394, 398, 422, 446, 454, 458, 5898, 478, 54582

Offset: 1

T. D. Noe, Oct 16 2013

nonn

Many terms are just twice a prime: 6, 22, 46, 58, 62, 94,....

			The number 138 has trajectory {138, 45, 25, 21, 13}, which is conjecturally the last number that terminates with 13 = prime(6). Hence a(6) = 138.

Donovan Johnson, Table of n, a(n) for n = 1..1000

Cf. A039650, A039651, A039652.

t = Table[NestWhileList[EulerPhi[#] + 1 &, n, UnsameQ, All][[-1]], {n, 100000}]; Table[Position[t, p][[-1]], {p, Prime[Range[53]]}]

cp's OEIS Frontend

A039649 a(n) = phi(n)+1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

Formula

Extensions

A039653 a(0) = 0; for n > 0, a(n) = sigma(n)-1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

A039655 Number of iterations of f(x) = sigma(x)-1 applied to n required to reach a prime, or -1 if no prime is ever reached.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A039651 Number of iterations of f(x) = phi(x)+1 on n required to reach a prime.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A039656 Becomes prime after n iterations of f(x) = sigma(x)-1 (least inverse of A039655).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs