OFFSET
1,1
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.
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
PROG
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
Peter Luschny, Sep 08 2023
STATUS
approved