OFFSET
1,1
COMMENTS
It is conjectured that A365339(n) = PrimePi(n) + 64 for all n >= 31957 (Pollack et al.). Assuming this conjecture a(n) = 0 for n > 31956.
a is not monotonically decreasing.
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.
PROG
(Julia) # Computes the first N terms of the sequence.
using Nemo
function A365400List(N)
phi = Int64[i for i in 1:N + 1]
for i in 2:N + 1
if phi[i] == i
for j in i:i:N + 1
phi[j] -= div(phi[j], i)
end end end
lst = zeros(Int64, N)
dyn = zeros(Int64, N)
pi = 64
for n in 1:N
p = phi[n]
nxt = dyn[p] + 1
while p <= N && dyn[p] < nxt
dyn[p] = nxt
p += 1
end
pi += is_prime(n) ? 1 : 0
lst[n] = pi - dyn[n]
end
return lst
end
println(A365400List(32000))
(Python)
from bisect import bisect
from sympy import totient, primepi
def A365400(n):
plist, qlist, c = tuple(totient(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 06 2023
CROSSREFS
KEYWORD
nonn
AUTHOR
Peter Luschny, Sep 06 2023
STATUS
approved