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

Author

Terence Tao, Sep 01 2023

Keywords

• nonn
• easy

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

Examples

			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.
		

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.

Crossrefs

Cf. A000010, A000720.

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

Programs

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

Mathematica

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

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

Formula

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