A039649 -id:A039649 - cp's OEIS frontend

A140141 Positions of second appearances of primes in A039649.

2, 4, 8, 9, 22, 21, 32, 27, 46, 58, 62, 57, 55, 49, 94, 106, 118, 77, 134, 142, 91, 158, 166, 115, 119, 125, 206, 214, 133, 145, 254, 262, 274, 278, 298, 302, 169, 243, 334, 346, 358, 209, 382, 221, 394, 398, 422, 446, 454, 458, 295, 478, 287, 502, 512, 526, 538

Offset: 1

Vladimir Shevelev, May 10 2008

nonn

The first occurrence of a prime p in A039649 is not interesting because for an odd prime p it is evidently p.
Since phi(p) = phi(2p) = p-1 for odd prime p, then for n > 1 we have prime(n) < a(n) <= 2*prime(n).
For n > 1, a(n) is the smallest composite k such that phi(k) = prime(n)-1. - Thomas Ordowski, Jan 02 2017
If prime(n) > 7 is in A005385, then a(n) = 2*prime(n). - Thomas Ordowski (conjecture) and Robert Israel (proof), Jan 04 2017

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A000010, A000040, A039649.

Table[Function[p, First@ Drop[Lookup[#, p], 1]]@ Prime@ n, {n, 57}] &@ PositionIndex@ Table[EulerPhi@ n + 1, {n, 10^5}] (* Michael De Vlieger, Jan 02 2017, Version 10 *)

Corrected and extended by Ray Chandler, May 20 2008

A140607 (A039649(2n+1)+A137576(n))/2.

Original entry on oeis.org

3, 5, 7, 10, 11, 13, 13, 17, 19, 22, 23, 31, 37, 29, 31, 31, 43, 37, 37, 41, 43, 55, 47, 64, 45, 53, 61, 55, 59, 61, 55, 61, 67, 78, 71, 73, 91, 106, 79, 136, 83, 77, 85, 89, 91, 96, 109, 97, 136, 101, 103, 109, 107, 109, 109, 113, 155, 103, 145, 166, 111, 201, 127, 113

Offset: 1

Vladimir Shevelev, May 18 2008

nonn

If 2n+1 is a prime then a(n) = 2n+1.

Ray Chandler, Table of n, a(n) for n=1..10000

Cf. A039649, A137576, A000010, A000040, A140140, A138193, A138217, A138227, A138535, A138536, A138537, A138539, A140141, A140608, A138786, A140667.

Extended by Ray Chandler, May 20 2008, May 24 2008

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

A066071 Nonprime numbers k such that phi(k) + 1 is prime.

Original entry on oeis.org

1, 4, 6, 8, 9, 10, 12, 14, 18, 21, 22, 26, 27, 28, 32, 34, 36, 38, 40, 42, 46, 48, 49, 54, 55, 57, 58, 60, 62, 63, 74, 75, 76, 77, 82, 86, 88, 91, 93, 94, 95, 98, 99, 100, 106, 108, 110, 111, 114, 115, 117, 118, 119, 122, 124, 125, 126, 132, 133, 134, 135, 142, 145, 146

Offset: 1

Labos Elemer, Dec 03 2001

nonn

A039698 with the primes removed. For every prime p, 2p is in the sequence. - Ray Chandler, May 26 2008

Includes 3*p for p in A005382 and p^2 for p in A065508. - Robert Israel, Dec 29 2017

			Solutions to 1+phi(x)=13 are {13, 21, 26, 28, 36, 42} of which the 5 composites are in the sequence.

Iain Fox, Table of n, a(n) for n = 1..10000 (first 1000 terms from Harry J. Smith)

Cf. A000010, A000040, A005382, A006093, A039649, A039698, A058339, A058340, A065508, A066072, A066073, A066074, A066075, A066076, A066077, A066080.

[n: n in [1..200] |not IsPrime(n) and IsPrime(EulerPhi(n)+1)]; // Vincenzo Librandi, Jul 02 2016

select(n -> not isprime(n) and isprime(1+numtheory:-phi(n)), [$1..1000]); # Robert Israel, Dec 29 2017

Select[Complement[Range@ #, Prime@ Range@ PrimePi@ #] &@ 150, PrimeQ[EulerPhi@ # + 1] &] (* Michael De Vlieger, Jul 01 2016 *)

isok(k) = { !isprime(k) && isprime(eulerphi(k) + 1) } \\ Harry J. Smith, Nov 10 2009

A013596 Irregular triangle of coefficients of cyclotomic polynomial Phi_n(x) (exponents in decreasing order).

Original entry on oeis.org

1, 0, 1, -1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, -1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, -1, 1, 1, -1, 0, 1, -1, 1, 0, -1, 1, 1, 0, 0, 0, 0

Offset: 0

N. J. A. Sloane

We follow Maple in defining Phi_0 to be x; it could equally well be taken to be 1.

			Phi_0 = x             --> Row 0: [1, 0]
Phi_1 = x - 1         --> Row 1: [1, -1]
Phi_2 = x + 1         --> Row 2: [1, 1]
Phi_3 = x^2 + x + 1   --> Row 3: [1, 1, 1]
Phi_4 = x^2 + 1       --> Row 4: [1, 0, 1]
etc. After row zero, each row n has A039649(n) terms.

E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, 1968; see p. 90.
Z. I. Borevich and I. R. Shafarevich, Number Theory. Academic Press, NY, 1966, p. 325.
K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, Springer, 1982, p. 194.

Antti Karttunen, Table of n, a(n) for n = 0..45566, rows 0..385 flattened

Version with reversed rows: A013595.

Cf. A039649, A160340.

with(numtheory): [ seq(cyclotomic(n,x), n=0..48) ];

Join[{1, 0}, Table[ CoefficientList[ Cyclotomic[n, x], x] // Reverse, {n, 1, 16}] // Flatten] (* Jean-François Alcover, Dec 11 2012 *)

A013595row(n) = { if(!n, p=x, p = polcyclo(n)); Vecrev(p); }; \\ This function from Michel Marcus's code for A013595.
n=0; for(r=0,385,v=A013595row(r);k=length(v);while(k>0,write("b013596.txt", n, " ", v[k]);n=n+1;k=k-1)); \\ Antti Karttunen, Aug 13 2017

Example section edited by Antti Karttunen, Aug 13 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 *)

A039698 Numbers k such that phi(k) + 1 is prime.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 17, 18, 19, 21, 22, 23, 26, 27, 28, 29, 31, 32, 34, 36, 37, 38, 40, 41, 42, 43, 46, 47, 48, 49, 53, 54, 55, 57, 58, 59, 60, 61, 62, 63, 67, 71, 73, 74, 75, 76, 77, 79, 82, 83, 86, 88, 89, 91, 93, 94, 95, 97, 98, 99, 100, 101, 103

Offset: 1

Olivier Gérard

Positive integers k for which values of A039649(k) are primes. - Vladimir Shevelev, May 10 2008
For every prime p, the numbers p and 2p are terms of this sequence. - Vladimir Shevelev, May 10 2008
Union of A000040 and A066071. - Ray Chandler, May 26 2008

			phi(10)+1 = 4+1 = 5, a prime number, so 10 is a term.

Antti Karttunen, Table of n, a(n) for n = 1..26197 (first 1000 terms from Vincenzo Librandi)

Cf. A000010, A000040, A006093, A039649, A066071, A007614.
Cf. A039689 (complement), A296079 (characteristic function).
Cf. also A065512, A078892, A263028, A248792.

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

Select[Range[300], PrimeQ[EulerPhi[#] + 1]&] (* Vincenzo Librandi, Aug 13 2013 *)

Edited by N. J. A. Sloane, May 21 2008 at the suggestion of R. J. Mathar

cp's OEIS Frontend

A140141 Positions of second appearances of primes in A039649.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A140607 (A039649(2n+1)+A137576(n))/2.

Views

Author

Keywords

Comments

Links

Crossrefs

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

A066071 Nonprime numbers k such that phi(k) + 1 is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica