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

Author

Chai Wah Wu, Sep 17 2023

Keywords

• nonn

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.

Crossrefs

Cf. A000010, A000720.

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

Programs

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