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

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, 14, 15, 15, 15, 15, 15, 16, 17, 17, 17, 18, 19, 19, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 23, 23, 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 27, 27, 27, 27

Offset: 1

Author

Peter Luschny, Sep 03 2023

Keywords

• nonn

Comments

The sequence was inspired by A365339.

Examples

			The terms of the subsequences of A000005 are marked by '*'. They start:
  1*, 2,  2 , 3,  2, 4,  2, 4,  ... -> a(1) = 1
  1*, 2*, 2 , 3,  2, 4,  2, 4,  ... -> a(2) = 2
  1*, 2*, 2*, 3,  2, 4,  2, 4,  ... -> a(3) = 3
  1*, 2*, 2*, 3*, 2, 4,  2, 4,  ... -> a(4) = 4
  1*, 2*, 2*, 3*, 2, 4,  2, 4,  ... -> a(5) = 4
  1*, 2*, 2*, 3*, 2, 4*, 2, 4,  ... -> a(6) = 5
  1*, 2*, 2*, 3*, 2, 4*, 2, 4,  ... -> a(7) = 5
  1*, 2*, 2*, 3*, 2, 4*, 2, 4*, ... -> a(8) = 6
Example: a(2000000) = 450033.
		

Links

• Peter Luschny, Table of n, a(n) for n = 1..10000
• Plot2, A365399 vs A365339.

Crossrefs

Cf. A000005, A365339, A365398.

Programs

Julia

# Computes the first N terms of the sequence using function tau from A000005.
function LLS_list(seq, N)
    lst = zeros(Int64, N)
    dyn = zeros(Int64, N)
    for n in 1:N
        p = seq(n)
        nxt = dyn[p] + 1
        while p <= N && dyn[p] < nxt
            dyn[p] = nxt
            p += 1
        end
        lst[n] = dyn[n]
    end
    return lst
end
A365399List(N) = LLS_list(tau, N)
println(A365399List(69))

Python

from bisect import bisect
from sympy import divisor_count
def A365399(n):
    plist, qlist, c = tuple(divisor_count(i) for i in range(1,n+1)), [0]*(n+1), 0
    for i in range(n):
        qlist[a:=bisect(qlist,plist[i],lo=1,hi=c+1,key=lambda x:plist[x])]=i
        c = max(c,a)
    return c # Chai Wah Wu, Sep 04 2023

Formula

a(n+1) - a(n) <= 1.