A365400 a(n) = 64 + A000720(n) - A365339(n).

63, 63, 63, 62, 62, 62, 62, 62, 61, 61, 61, 61, 61, 61, 60, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 58, 58, 58, 58, 58, 58, 58, 58, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 56

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

Table of n, a(n) for n=1..65.

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

Cf. A000720, A365339, A365474.

Sequence in context: A086859 A278827 A125638 * A365397 A332926 A112816

Adjacent sequences: A365397 A365398 A365399 * A365401 A365402 A365403

Keyword

nonn

Author

Peter Luschny, Sep 06 2023

Status

approved