cp's OEIS Frontend

A365737 Length of the longest subsequence of 1,...,n on which the Euler totient function phi A000010 is nonincreasing.

%I A365737 #19 Oct 13 2023 11:46:21
%S A365737 1,2,2,2,2,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,6,6,6,6,6,
%T A365737 6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,
%U A365737 8,8,8,9,9,9,9,9,9,10,10,10,10,10,10,11
%N A365737 Length of the longest subsequence of 1,...,n on which the Euler totient function phi A000010 is nonincreasing.
%H A365737 Chai Wah Wu, <a href="/A365737/b365737.txt">Table of n, a(n) for n = 1..10000</a>
%H A365737 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 M↓(n).
%H A365737 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 A365737 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.
%o A365737 (Python)
%o A365737 from bisect import bisect
%o A365737 from sympy import totient
%o A365737 def A365737(n):
%o A365737     plist, qlist, c = tuple(-totient(i) for i in range(1,n+1)), [0]*(n+1), 0
%o A365737     for i in range(n):
%o A365737         qlist[a:=bisect(qlist,plist[i],lo=1,hi=c+1,key=lambda x:plist[x])]=i
%o A365737         c = max(c,a)
%o A365737     return c
%Y A365737 Cf. A000010, A000720.
%Y A365737 Cf. A365339, A365398, A365399, A365400, A365474, A061070.
%K A365737 nonn
%O A365737 1,2
%A A365737 _Chai Wah Wu_, Sep 17 2023