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,4

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.

Formula

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

Prog

(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

Crossrefs

Cf. A000010, A000720.

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

Sequence in context: A338365 A194249 A285759 * A082997 A085970 A355538

Adjacent sequences: A365737 A365738 A365739 * A365741 A365742 A365743

Keyword

nonn

Author

Chai Wah Wu, Sep 17 2023

Status

approved