A365737 Length of the longest subsequence of 1,...,n on which the Euler totient function phi A000010 is nonincreasing.

1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 11

Offset

1,2

Links

Chai Wah Wu, Table of n, a(n) for n = 1..10000

Paul Pollack, Carl Pomerance and Enrique Treviño, Sets of monotonicity for Euler's totient function, preprint. See M↓(n).

Paul Pollack, Carl Pomerance and Enrique Treviño, Sets of monotonicity for Euler's totient function, Ramanujan J. 30 (2013), no. 3, 379--398.

Terence Tao, Monotone non-decreasing sequences of the Euler totient function, arXiv:2309.02325 [math.NT], 2023.

Prog

(Python)
from bisect import bisect
from sympy import totient
def A365737(n):
    plist, qlist, c = tuple(-totient(i) for i in range(1, n+1)), [0]*(n+1), 0
    for i in range(n):
        qlist[a:=bisect(qlist, plist[i], lo=1, hi=c+1, key=lambda x:plist[x])]=i
        c = max(c, a)
    return c

Crossrefs

Cf. A000010, A000720.

Cf. A365339, A365398, A365399, A365400, A365474, A061070.

Sequence in context: A242768 A365742 A064557 * A023967 A278163 A347635

Adjacent sequences: A365734 A365735 A365736 * A365738 A365739 A365740

Keyword

nonn

Author

Chai Wah Wu, Sep 17 2023

Status

approved