cp's OEIS Frontend

A365398 Length of the longest subsequence of 1, ..., n on which sigma, the sum of the divisors of n (A000203), is nondecreasing.

%I A365398 #21 Sep 10 2023 13:14:46
%S A365398 1,2,3,4,4,5,5,6,6,7,7,8,8,8,9,10,10,11,11,12,12,12,12,13,13,13,13,14,
%T A365398 14,15,15,15,15,15,15,16,16,16,16,17,17,18,18,18,18,18,18,19,19,19,19,
%U A365398 19,19,20,20,21,21,21,21,22,22,22,23,24,24,25,25,25
%N A365398 Length of the longest subsequence of 1, ..., n on which sigma, the sum of the divisors of n (A000203), is nondecreasing.
%C A365398 The sequence was inspired by A365339. In particular, note remark (4.4) by Terence Tao in the linked paper.
%H A365398 Chai Wah Wu, <a href="/A365398/b365398.txt">Table of n, a(n) for n = 1..10000</a>
%H A365398 Plot2, <a href="https://oeis.org/plot2a?name1=A365398&amp;name2=A365339&amp;tform1=untransformed&amp;tform2=untransformed&amp;shift=0&amp;radiop1=ratio&amp;drawlines=true">A365398 vs A365339</a>.
%H A365398 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 A365398 a(n+1) - a(n) <= 1.
%F A365398 a(n) >= A000720(n)+1 since A000203(p) = p+1 for p prime. - _Chai Wah Wu_, Sep 08 2023
%o A365398 (Python)
%o A365398 from bisect import bisect
%o A365398 from sympy import divisor_sigma
%o A365398 def A365398(n):
%o A365398     plist, qlist, c = tuple(divisor_sigma(i) for i in range(1,n+1)), [0]*(n+1), 0
%o A365398     for i in range(n):
%o A365398         qlist[a:=bisect(qlist,plist[i],lo=1,hi=c+1,key=lambda x:plist[x])]=i
%o A365398         c = max(c,a)
%o A365398     return c # _Chai Wah Wu_, Sep 08 2023
%Y A365398 Cf. A000203, A000720, A365339, A365399, A365397.
%Y A365398 Cf. A061069.
%K A365398 nonn
%O A365398 1,2
%A A365398 _Peter Luschny_, Sep 08 2023