A365339 Length of the longest subsequence of 1,...,n on which the Euler totient function phi A000010 is nondecreasing.

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

Offset

1,2

Comments

a(n+1) is equal to a(n) or a(n) + 1 for every n.

It is conjectured that a(n) = pi(n) + 64 for all n >= 31957, which has been verified up to n = 10^7 (Pollack et al.), where pi is A000720. We always have a(n) >= pi(n).

Conjecture is true for n = 10^8 and n = 10^9. - Chai Wah Wu, Sep 05 2023

Links

Alois P. Heinz, Table of n, a(n) for n = 1..10000

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, 379--398.

Terence Tao, Monotone non-decreasing sequences of the Euler totient function, arXiv:2309.02325 [math.NT], 2023.

Formula

Tao proves that a(n) ~ n/log n. a(n) >= pi(n) + 64 for all n >= 31957; conjecturally this is an equality. - Charles R Greathouse IV, Dec 08 2023

Example

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

Mathematica

Table[Length[LongestOrderedSequence[Table[EulerPhi[i], {i, n}]]], {n, 100}]

Prog

(Python)
import math
def phi(n):
    result = n
    for i in range(2, math.isqrt(n) + 1):
        if n % i == 0:
            while n % i == 0:
                n //= i
            result -= result // i
    if n > 1:
        result -= result // n
    return result
# This code uses dynamic programming to print the first N=100 values of M.
N=100
M = [0 for i in range(N)]
dynamic = [0 for i in range(N+1)]
for n in range(1, N+1):
    i = phi(n)
    new = dynamic[i] + 1
    while (i<=N and dynamic[i] < new):
        dynamic[i] = new
        i+= 1
    M[n-1] = dynamic[N]
print(M)
(Python)
from bisect import bisect
from sympy import totient
def A365339(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 c # Chai Wah Wu, Sep 03 2023
(Julia) # Computes the first N terms of the sequence.
function A365339List(N)
    phi = [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)
    for n in 1:N
        p = phi[n]
        nxt = dyn[p] + 1
        while p <= N && dyn[p] < nxt
            dyn[p] = nxt
            p += 1
        end
        lst[n] = dyn[n]
    end
    return lst
end
println(A365339List(69))  # Peter Luschny, Sep 02 2023

Crossrefs

Cf. A000010, A000720.

Cf. A365398, A365399, A365400, A365474, A061070.

Sequence in context: A354535 A276656 A309250 * A046108 A079411 A360744

Adjacent sequences: A365336 A365337 A365338 * A365340 A365341 A365342

Keyword

nonn,easy

Author

Terence Tao, Sep 01 2023

Status

approved