A039654 -id:A039654 - cp's OEIS frontend

A292112 Records in A039654.

2, 3, 11, 23, 71, 167, 233, 311, 359, 599, 743, 983, 1487, 1823, 2063, 4943, 6719, 11423, 16103, 24623, 42407, 48527, 51599, 55823, 58967, 105239, 249287, 384143, 443039, 465743, 494759, 511487, 692663, 908927, 957599, 1124639, 1432679

Offset: 1

N. J. A. Sloane, Sep 22 2017

nonn

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

Cf. A039654, A039655, A292113.

More terms from Hugo Pfoertner, Sep 22 2017

A292113 List of numbers n such that A039654(n) reaches a new record high.

Original entry on oeis.org

2, 3, 4, 8, 9, 32, 36, 64, 81, 100, 121, 144, 228, 256, 300, 400, 441, 468, 800, 1200, 2964, 5202, 5408, 6084, 6400, 7500, 8100, 9216, 24556, 28092, 31329, 32176, 32400, 37296, 49017, 49152, 57600, 72156, 80400, 83161, 86352, 88200, 133200

Offset: 1

N. J. A. Sloane, Sep 22 2017

nonn

Naively, one might have expected these numbers to have some other distinguishing property (primorials, perhaps), but that seems not to be the case.

Except for 3 of the listed terms, a(n)-1 or a(n)+1 has at most 2 prime divisors. The same is true for many of the terms themselves, often of the form 2^k, 3^k, 2^k*3^k' or 2^k*5^k'. (Factorization of the terms: 2, 3, 2^2, 2^3, 3^2, 2^5, 2^2*3^2, 2^6, 3^4, 2^2*5^2, 11^2, 2^4*3^2, 2^2*3*19, 2^8, 2^2*3*5^2, 2^4*5^2, 3^2*7^2, 2^2*3^2*13, 2^5*5^2, ...) - M. F. Hasler, Sep 25 2017

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

Cf. A039654, A039655, A292112.

m=-n=1; until(print1(n","), until(A039654(n++)>m,); m=A039654(n)) \\ M. F. Hasler, Sep 25 2017

A177343 Number of times the n-th prime occurs in A039654.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 4, 2, 4, 1, 1, 12, 1, 2, 3, 3, 2, 1, 2, 2, 1, 2, 2, 2, 1, 2, 1, 3, 1, 1, 25, 1, 4, 2, 10, 1, 1, 1, 1, 3, 5, 1, 4, 10, 1, 7, 1, 8, 3, 2, 1, 1, 1, 4, 2, 5, 1, 1, 1, 1, 1, 1, 1, 18, 1, 1, 1, 10, 2, 1, 1, 1, 6, 1, 16, 4, 2, 2, 3, 1, 1, 1, 3, 11, 1, 2, 1, 18, 1, 2, 1, 1, 1, 3

Offset: 1

Franklin T. Adams-Watters, May 06 2010

nonn

Record values for primes up to 10000:
    n  p(n) a(n)
  2   1
 11   3
 23   4
 71  12
167  25
743  58
1487  62
2879  71
5039 125
6719 168
The function A039653(n) = sigma(n)-1 iterated in A039654 satisfies A039653(n) >= n (with equality iff n is a prime), therefore the prime p cannot appear beyond index p in A039654, and it is sufficient to count how many times p = A039654(n) with n < p, cf. Formula. - M. F. Hasler, Sep 25 2017

Franklin T. Adams-Watters, Table of n, a(n) for n=1..1229 (primes through 10000)

Cf. A039654, A039653, A292112, A292113.

a(n)=sum(k=2,n=prime(n),A039654(k)==n) \\ M. F. Hasler, Sep 25 2017

a(n) = 1 + # { k < prime(n) | A039654(k) = prime(n) } . - M. F. Hasler, Sep 25 2017

A292874 Least k such that A039654(k) = prime(n).

Original entry on oeis.org

2, 3, 5, 7, 4, 13, 10, 19, 8, 29, 21, 37, 20, 43, 22, 34, 18, 61, 67, 9, 73, 57, 44, 40, 52, 101, 63, 85, 109, 74, 93, 86, 137, 76, 149, 91, 157, 163, 32, 173, 88, 117, 68, 193, 197, 199, 211, 84, 80, 229, 36, 104, 241, 96, 257, 102, 136

Offset: 1

M. F. Hasler, Sep 25 2017

nonn

We have A039653(k) >= k, thus also A039654(k) >= k, with equality if k is prime, therefore a(n) <= prime(n), and the largest k for which A039654(k) = prime(n) is always k = prime(n).

Cf. A039653, A039654, A177343, A292112, A292113.

a039654(n) = if(n<2, 0, my(m); while((m=sigma(n)-1)!=n, n=m); n);
a(n) = my(k=0, p=prime(n)); while(a039654(k) != p, k++); k; \\ Michel Marcus, Sep 26 2017

A292876 Irregular table whose n-th row lists all k such that A039654(k) = prime(n).

Original entry on oeis.org

2, 3, 5, 7, 4, 6, 11, 13, 10, 17, 19, 8, 14, 15, 23, 29, 21, 31, 37, 20, 26, 41, 43, 22, 33, 35, 47, 34, 53, 18, 24, 38, 59, 61, 67, 9, 12, 16, 25, 27, 28, 30, 39, 46, 51, 55, 71, 73, 57, 79, 44, 65, 83, 40, 58, 89

Offset: 1

M. F. Hasler, Sep 25 2017

This can also be considered as a list of all orbits of A039653, ordered by their maximal element p = A039654(k) for any k of this orbit.
Indeed, A039653(x) >= x with equality iff x is prime, and all orbits of A039653 are conjectured to end in such a fixed point prime p = A039654(k) for any k in this orbit.
Row lengths are given by A177343.
This sequence is also a permutation of all integers > 1, where each prime p(k) is immediately preceded by A177343(k)-1 composite numbers less than p(k). It follows that each composite is preceded either by a smaller composite or by a larger prime, and followed by a larger composite or prime. Thus, the primes appear in their natural order, but the composites do not.
The first element of each row (i.e., the first column of this table) is given by A292874.
We see (cf. a-file) that powers of 2 are often the first element (or at least part) of relatively long orbits: A177343(A000720(A039654(2^k))) = (1, 3, 4, 12, 25, 5, 10, 35, 61, 143, 143, 220, 365, ...)

			The table starts:
    n  p(n)  { k | A039654(k) = p(n) }
    1    2   { 2 }
    2    3   { 3 }
    3    5   { 5 }
    4    7   { 7 }
    5   11   { 4, 6, 11 }
    6   13   { 13 }
    7   17   { 10, 17 }
    8   19   { 19 }
    9   23   { 8, 14, 15, 23 }

M. F. Hasler, Table rows n = 1..1229

Cf. A039654, A039653, A177343, A292874, A292112, A292113.

A292876(n,p=prime(n))=select(k->A039654(k)==p,[2..p]) \\ Not optimized nor efficient; mainly for illustrational purpose. - M. F. Hasler, Sep 25 2017

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

Original entry on oeis.org

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

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

cp's OEIS Frontend

A292112 Records in A039654.

Views

Author

Keywords

Links

Crossrefs

Extensions

A292113 List of numbers n such that A039654(n) reaches a new record high.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A177343 Number of times the n-th prime occurs in A039654.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A292874 Least k such that A039654(k) = prime(n).

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

A292876 Irregular table whose n-th row lists all k such that A039654(k) = prime(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

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

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

Views

Author

Keywords

Comments

Examples

References