cp's OEIS Frontend

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

%I A365740 #10 Sep 18 2023 14:09:28
%S A365740 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 A365740 13,13,14,15,15,16,16,16,16,17,17,17,17,17,17,18,18,18,18,19,19,19,19,
%U A365740 19,19,20,20,21,21,21,21,21,22,23,23,24,24,24,24,25,25
%N A365740 Length of the longest subsequence of {m: 1<=m<=n, m not prime} on which the Euler totient function phi A000010 is nondecreasing.
%H A365740 Chai Wah Wu, <a href="/A365740/b365740.txt">Table of n, a(n) for n = 1..10000</a>
%H A365740 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 A365740 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 A365740 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 A365740 Pollack et al. conjectured that a(n) < A365339(n)-2 for all n >= 31957.
%o A365740 (Python)
%o A365740 from bisect import bisect
%o A365740 from sympy import totient, isprime
%o A365740 def A365740(n):
%o A365740     plist = tuple(totient(i) for i in range(1,n+1) if not isprime(i))
%o A365740     m = len(plist)
%o A365740     qlist, c = [0]*(m+1), 0
%o A365740     for i in range(m):
%o A365740         qlist[a:=bisect(qlist,plist[i],lo=1,hi=c+1,key=lambda x:plist[x])]=i
%o A365740         c = max(c,a)
%o A365740     return c
%Y A365740 Cf. A000010, A000720.
%Y A365740 Cf. A365339, A365398, A365399, A365400, A365474, A365737, A061070.
%K A365740 nonn
%O A365740 1,4
%A A365740 _Chai Wah Wu_, Sep 17 2023