A365740 Length of the longest subsequence of {m: 1<=m<=n, m not prime} on which the Euler totient function phi A000010 is nondecreasing.

1, 1, 1, 2, 2, 3, 3, 4, 5, 5, 5, 6, 6, 7, 8, 9, 9, 9, 9, 10, 11, 11, 11, 11, 12, 12, 13, 13, 13, 13, 13, 14, 15, 15, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 20, 20, 21, 21, 21, 21, 21, 22, 23, 23, 24, 24, 24, 24, 25, 25

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 M2(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, A365737, A061070.

Programs

Python

from bisect import bisect
from sympy import totient, isprime
def A365740(n):
    plist = tuple(totient(i) for i in range(1,n+1) if not isprime(i))
    m = len(plist)
    qlist, c = [0]*(m+1), 0
    for i in range(m):
        qlist[a:=bisect(qlist,plist[i],lo=1,hi=c+1,key=lambda x:plist[x])]=i
        c = max(c,a)
    return c

Formula

Pollack et al. conjectured that a(n) < A365339(n)-2 for all n >= 31957.