A365397 -id:A365397 - 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.

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

Offset: 1

Peter Luschny, Sep 08 2023

nonn

The sequence was inspired by A365339. In particular, note remark (4.4) by Terence Tao in the linked paper.

Chai Wah Wu, Table of n, a(n) for n = 1..10000
Plot2, A365398 vs A365339.
Terence Tao, Monotone non-decreasing sequences of the Euler totient function, arXiv:2309.02325 [math.NT], 2023.

Cf. A000203, A000720, A365339, A365399, A365397.

Cf. A061069.

from bisect import bisect
from sympy import divisor_sigma
def A365398(n):
    plist, qlist, c = tuple(divisor_sigma(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 08 2023

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

a(n) >= A000720(n)+1 since A000203(p) = p+1 for p prime. - Chai Wah Wu, Sep 08 2023

A371156 Length of the longest subsequence of 1, ..., n on which the Dedekind psi function (A001615) is nondecreasing.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 6, 7, 8, 9, 9, 10, 10, 11, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 17, 17, 18, 18, 19, 19, 19, 20, 21, 21, 22, 22, 22, 22, 23, 23, 24, 24, 24, 25, 26, 26, 27, 27, 27, 27, 28, 28, 29, 29, 29, 29, 30, 30, 31, 31, 31, 32, 33, 33, 34, 34, 34

Offset: 1

Chai Wah Wu, Apr 10 2024

nonn

The envelope max_{i<=n} (a(i)-A000720(i)) appears to be slowly increasing as n increases. For instance, a(1)-A000720(1)=1, whereas a(374598)-A000720(374598)=91 and a(642852)-A000720(642852)=96.

			a(7) = 6 because A001615 is nondecreasing on 1,2,3,4,5,6 or 1,2,3,4,5,7 but not on 1,2,3,4,5,6,7.

Chai Wah Wu, Table of n, a(n) for n = 1..10000
Terence Tao, Monotone non-decreasing sequences of the Euler totient function, arXiv:2309.02325 [math.NT], 2023. See Remark 4.7.

Cf. A000720, A001615, A365339, A365399, A365397, A365398, A365740.

Length[LongestOrderedSequence[#]] & /@ Rest[FoldList[Append, {}, Table[n DivisorSum[n, MoebiusMu[#]^2/# &], {n, 20}]]] (* Eric W. Weisstein, Mar 09 2025 *)

from math import prod
from bisect import bisect
from sympy import primefactors
def A371156(n):
    def f(n):
        r = primefactors(n)
        return n*prod(p+1 for p in r)//prod(r)
    plist, qlist, c = tuple(f(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

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

a(n) >= A000720(n)+1 since A001615(p) = p+1 for p prime.

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.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Formula