A390521 a(n) = limiting prime of the recurrence x(k) = 1 + (phi(x(k-1)) + phi(x(k-2))) / 2 started at x(0) = x(1) = n.

2, 2, 3, 3, 5, 3, 7, 5, 7, 5, 11, 5, 13, 7, 3, 3, 17, 7, 19, 3, 13, 11, 23, 3, 5, 13, 19, 13, 29, 3, 31, 17, 5, 17, 3, 13, 37, 19, 3, 17, 41, 13, 43, 5, 3, 23, 47, 17, 43, 5, 3, 3, 53, 19, 41, 3, 37, 29, 59, 17, 61, 31, 37, 3, 3, 5, 67, 3, 3, 3, 71, 3, 73, 37, 41, 37, 61, 3, 79, 3, 3, 41, 83

Offset

1,1

Comments

a(n) is always prime. a(p) = p for every prime p. The prime number 2 appears just two times (n = 1, 2). For composite n, a(n) is typically a smaller prime; numerics suggest strong bias toward primes p with p-1 having only small factors (notably 2 and 3). For 1 <= n <= 5000, the most frequent limiting primes are: 3 (1057 times), 5 (946), 13 (234), 73 (224), 433 (65), 1153 (52), etc.

The sequence generalizes in two dimensions A039650 ("Prime reached by iterating f(x) = phi(x)+1 on n"), because it could be extended to an infinite two-dimensional matrix T(i,j), so as to start with a generic pair of seeds x(0), x(1) (both greater than 2, to ensure that the result is always integer). In this case, the sequence in question would represent the diagonal T(n,n) of the matrix.

Links

Augusto Santi, Table of n, a(n) for n = 1..5000

Thomas Bloom, Problem 409, Erdős Problems.

Augusto Santi, A sequence based on Euler's totient function that always converges to prime numbers, Mathematics StackExchange, 2025.

Example

For n = 4, 1+(phi(4)+phi(4))/2 = 1+(2+2)/2 = 3; 1+(phi(3)+phi(4))/2 = 1+(2+2)/2 = 3; 1+(phi(3)+phi(3))/2 = 1+(2+2)/2 = 3, therefore a(4) = 3.

Mathematica

a[n_] := NestWhile[{Last[#], 1 + Total[EulerPhi[#]]/2} &, {n, n}, ! (Equal @@ # && PrimeQ[First[#]]) &][[1]]; Array[a, 100] (* Amiram Eldar, Nov 10 2025 *)

Crossrefs

Cf. A000010 (phi), A039650, A229487, A039651.

Sequence in context: A340265 A339696 A263027 * A069974 A039650 A039649

Adjacent sequences: A390518 A390519 A390520 * A390522 A390523 A390524

Keyword

nonn

Author

Augusto Santi, Nov 09 2025

Status

approved