login
A365740
Length of the longest subsequence of {m: 1<=m<=n, m not prime} on which the Euler totient function phi A000010 is nondecreasing.
7
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
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
KEYWORD
nonn
AUTHOR
Chai Wah Wu, Sep 17 2023
STATUS
approved