A365397 a(n) = 64 + A000720(n) - A365398(n).

63, 63, 63, 62, 63, 62, 63, 62, 62, 61, 62, 61, 62, 62, 61, 60, 61, 60, 61, 60, 60, 60, 61, 60, 60, 60, 60, 59, 60, 59, 60, 60, 60, 60, 60, 59, 60, 60, 60, 59, 60, 59, 60, 60, 60, 60, 61, 60, 60, 60, 60, 60, 61, 60, 60, 59, 59, 59, 60, 59, 60, 60, 59, 58, 58

Offset: 1

Author

Peter Luschny, Sep 08 2023

Keywords

• nonn

Comments

It is conjectured that A365339(n) - PrimePi(n) = 64 for all n >= 31957 (Pollack et al.). Does a similar relation apply if one replaces Euler's totient by the sum of divisors function in A365339? In particular, note remark (4.4) by Terence Tao in the linked paper.

From Chai Wah Wu, Sep 08 2023: (Start)

a(n) seems to be decreasing for n=10^i:

a(1) = 63

a(10) = 61

a(100) = 58

a(1000) = 58

a(10^4) = 54

a(10^5) = 53

a(10^6) = 48

a(10^7) = 46

a(10^8) = 43

(End)

Links

• Paul Pollack, Carl Pomerance, and Enrique Treviño, Sets of monotonicity for Euler's totient function, preprint. See M(n).
• Paul Pollack, Carl Pomerance, and Enrique Treviño, Sets of monotonicity for Euler's totient function, Ramanujan J. 30 (2013), no. 3, pp. 379-398.
• Terence Tao, Monotone non-decreasing sequences of the Euler totient function, arXiv:2309.02325 [math.NT], 2023.

Crossrefs

Cf. A000720, A000203, A365398, A365400.

Programs

Python

from bisect import bisect
from sympy import divisor_sigma, primepi
def A365397(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 64+primepi(n)-c # Chai Wah Wu, Sep 08 2023

Formula

a(n)<=63. This is due to the fact that A000203(p) = p+1 for p prime, and therefore A365398(n) >= A000720(n)+1. - Chai Wah Wu, Sep 08 2023