A039650 -id:A039650 - cp's OEIS frontend

A069974 Duplicate of 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, 29

Offset: 1

dead

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

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 *)

A039652 Becomes prime after n iterations of f(x) = phi(x)+1 (least inverse of A039651).

Original entry on oeis.org

2, 1, 15, 35, 69, 255, 535, 949, 1957, 2513, 2923, 4531, 17701, 22957, 54589, 79421, 80029, 84493, 98581, 102827, 115243, 239111, 291149, 310813, 362621, 398893, 598341, 801923, 838307, 1063493, 1079833, 1123813, 1311121, 1329403, 1582439

Offset: 0

David W. Wilson

Of the terms n <= 66, all are semiprimes except those for n = 0, 1, 5, and 19. Why? - T. D. Noe, Oct 17 2013

T. D. Noe, Table of n, a(n) for n = 0..66

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

nn = 34; t = Table[0, {nn}]; found = 0; n = 0; While[found < nn, n++; len = Length[NestWhileList[EulerPhi[#] + 1 &, n, UnsameQ, All]] - 2; If[len <= nn && t[[len]] == 0, t[[len]] = n; found++]]; t = Join[{2}, t] (* 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

A221740 a(n) = -4((n-1)(n+1)^(n+1)+1)/(((-1)^n-3)*n^3).

Original entry on oeis.org

1, 7, 19, 293, 1493, 38127, 293479, 10593529, 109739369, 5135610071, 66987982331, 3856048810781, 60693710471869, 4149140360751583, 76519827268721103, 6058888636862818097, 128138108936443028945, 11533996620790579909159

Offset: 1

Alexander R. Povolotsky, Jan 23 2013

nonn

Per exhaustive program, written for bases from 2 to 10, the number of permutations pairs, which have the same ratio, equal to A221740(n)/A221741(n) = (n^2*(n+1)^n - (n+1)^n + 1) / (-n^2 + n*(n+1)^n + (n+1)^n - n - 1), is: {2,2,3,3,5,3,7,5,7,...} for n >= 1 where n = r-1 and r is the base radix. Judging by above sequence it appears that the number of such permutations pairs is related to phi, which is the Euler totient function - according to A039649, A039650, A214288 (see bullet 1 of the analysis in the answer section of the Mathematics StackExchange link). - Alexander R. Povolotsky, Jan 26 2013

G. C. Greubel, Table of n, a(n) for n = 1..385
Mathematics StackExchange, Permutations (with no duplicates) of decimal base digits 1,2,...,8,9,0.
NMBRTHRY, Number of specific permutations pairs relates to Euler Phi totient function?

Cf. A221741, A051846.

Table[-4*((n - 1)*(n + 1)^(n + 1) + 1)/(((-1)^n - 3)*n^3), {n,1,50}] (* G. C. Greubel, Feb 19 2017 *)

makelist(-4*((n-1)*(n+1)^(n+1)+1)/(((-1)^n-3)*n^3),n,1,20); /* Martin Ettl, Jan 25 2013 */

for(n=1,25, print1(-4*((n - 1)*(n + 1)^(n + 1) + 1)/(((-1)^n - 3)*n^3), ", ")) \\ G. C. Greubel, Feb 19 2017

a(n) = -4*A051846(n)/((-3 + (-1)^n)*n).
From Alexander R. Povolotsky, Oct 12 2022: (Start)
floor(a(n+1)/A221741(n+1)) = n.
Limit_{n->oo} (a(n)/A221741(n) - floor(a(n)/A221741(n))) = 0. (End)

cp's OEIS Frontend

A069974 Duplicate of A039650.

Views

Author

Keywords

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

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

A039652 Becomes prime after n iterations of f(x) = phi(x)+1 (least inverse of A039651).

Views

Author

Keywords

Comments

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

A221740 a(n) = -4((n-1)(n+1)^(n+1)+1)/(((-1)^n-3)*n^3).