cp's OEIS Frontend

A365399 Length of the longest subsequence of 1, ..., n on which the number of divisors function tau A000005 is nondecreasing.

%I A365399 #22 Sep 17 2023 21:22:02
%S A365399 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 A365399 14,15,15,15,15,15,16,17,17,17,18,19,19,20,20,20,20,20,20,21,21,21,21,
%U A365399 22,22,23,23,24,24,24,24,25,25,25,25,26,26,27,27,27,27
%N A365399 Length of the longest subsequence of 1, ..., n on which the number of divisors function tau A000005 is nondecreasing.
%C A365399 The sequence was inspired by A365339.
%H A365399 Peter Luschny, <a href="/A365399/b365399.txt">Table of n, a(n) for n = 1..10000</a>
%H A365399 Plot2, <a href="https://oeis.org/plot2a?name1=A365399&amp;name2=A365339&amp;tform1=untransformed&amp;tform2=untransformed&amp;shift=0&amp;radiop1=ratio&amp;drawlines=true">A365399 vs A365339</a>.
%F A365399 a(n+1) - a(n) <= 1.
%e A365399 The terms of the subsequences of A000005 are marked by '*'. They start:
%e A365399   1*, 2,  2 , 3,  2, 4,  2, 4,  ... -> a(1) = 1
%e A365399   1*, 2*, 2 , 3,  2, 4,  2, 4,  ... -> a(2) = 2
%e A365399   1*, 2*, 2*, 3,  2, 4,  2, 4,  ... -> a(3) = 3
%e A365399   1*, 2*, 2*, 3*, 2, 4,  2, 4,  ... -> a(4) = 4
%e A365399   1*, 2*, 2*, 3*, 2, 4,  2, 4,  ... -> a(5) = 4
%e A365399   1*, 2*, 2*, 3*, 2, 4*, 2, 4,  ... -> a(6) = 5
%e A365399   1*, 2*, 2*, 3*, 2, 4*, 2, 4,  ... -> a(7) = 5
%e A365399   1*, 2*, 2*, 3*, 2, 4*, 2, 4*, ... -> a(8) = 6
%e A365399 Example: a(2000000) = 450033.
%o A365399 (Julia)
%o A365399 # Computes the first N terms of the sequence using function tau from A000005.
%o A365399 function LLS_list(seq, N)
%o A365399     lst = zeros(Int64, N)
%o A365399     dyn = zeros(Int64, N)
%o A365399     for n in 1:N
%o A365399         p = seq(n)
%o A365399         nxt = dyn[p] + 1
%o A365399         while p <= N && dyn[p] < nxt
%o A365399             dyn[p] = nxt
%o A365399             p += 1
%o A365399         end
%o A365399         lst[n] = dyn[n]
%o A365399     end
%o A365399     return lst
%o A365399 end
%o A365399 A365399List(N) = LLS_list(tau, N)
%o A365399 println(A365399List(69))
%o A365399 (Python)
%o A365399 from bisect import bisect
%o A365399 from sympy import divisor_count
%o A365399 def A365399(n):
%o A365399     plist, qlist, c = tuple(divisor_count(i) for i in range(1,n+1)), [0]*(n+1), 0
%o A365399     for i in range(n):
%o A365399         qlist[a:=bisect(qlist,plist[i],lo=1,hi=c+1,key=lambda x:plist[x])]=i
%o A365399         c = max(c,a)
%o A365399     return c # _Chai Wah Wu_, Sep 04 2023
%Y A365399 Cf. A000005, A365339, A365398.
%K A365399 nonn
%O A365399 1,2
%A A365399 _Peter Luschny_, Sep 03 2023