Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #10 Sep 18 2023 14:09:28
%S 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,
%T 13,13,14,15,15,16,16,16,16,17,17,17,17,17,17,18,18,18,18,19,19,19,19,
%U 19,19,20,20,21,21,21,21,21,22,23,23,24,24,24,24,25,25
%N Length of the longest subsequence of {m: 1<=m<=n, m not prime} on which the Euler totient function phi A000010 is nondecreasing.
%H Chai Wah Wu, <a href="/A365740/b365740.txt">Table of n, a(n) for n = 1..10000</a>
%H Paul Pollack, Carl Pomerance and Enrique Treviño, <a href="https://math.dartmouth.edu/~carlp/MonotonePhi.pdf">Sets of monotonicity for Euler's totient function</a>, preprint. See M2(n).
%H Paul Pollack, Carl Pomerance and Enrique Treviño, <a href="https://doi.org/10.1007/s11139-012-9386-6">Sets of monotonicity for Euler's totient function</a>, Ramanujan J. 30 (2013), no. 3, 379--398.
%H Terence Tao, <a href="https://arxiv.org/abs/2309.02325">Monotone non-decreasing sequences of the Euler totient function</a>, arXiv:2309.02325 [math.NT], 2023.
%F Pollack et al. conjectured that a(n) < A365339(n)-2 for all n >= 31957.
%o (Python)
%o from bisect import bisect
%o from sympy import totient, isprime
%o def A365740(n):
%o plist = tuple(totient(i) for i in range(1,n+1) if not isprime(i))
%o m = len(plist)
%o qlist, c = [0]*(m+1), 0
%o for i in range(m):
%o qlist[a:=bisect(qlist,plist[i],lo=1,hi=c+1,key=lambda x:plist[x])]=i
%o c = max(c,a)
%o return c
%Y Cf. A000010, A000720.
%Y Cf. A365339, A365398, A365399, A365400, A365474, A365737, A061070.
%K nonn
%O 1,4
%A _Chai Wah Wu_, Sep 17 2023