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,2

Comments

The sequence was inspired by A365339.

Links

Peter Luschny, Table of n, a(n) for n = 1..10000

Plot2, A365399 vs A365339.

Formula

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

Example

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.

Prog

(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

Crossrefs

Cf. A000005, A365339, A365398.

Sequence in context: A302778 A203967 A365398 * A267530 A050292 A181627

Adjacent sequences: A365396 A365397 A365398 * A365400 A365401 A365402

Keyword

nonn

Author

Peter Luschny, Sep 03 2023

Status

approved