A365398 -id:A365398 - cp's OEIS frontend

A365397 a(n) = 64 + A000720(n) - A365398(n).

63, 63, 63, 62, 63, 62, 63, 62, 62, 61, 62, 61, 62, 62, 61, 60, 61, 60, 61, 60, 60, 60, 61, 60, 60, 60, 60, 59, 60, 59, 60, 60, 60, 60, 60, 59, 60, 60, 60, 59, 60, 59, 60, 60, 60, 60, 61, 60, 60, 60, 60, 60, 61, 60, 60, 59, 59, 59, 60, 59, 60, 60, 59, 58, 58

Offset: 1

Peter Luschny, Sep 08 2023

nonn

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)

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.

Cf. A000720, A000203, A365398, A365400.

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

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

A365399 Length of the longest subsequence of 1, ..., n on which the number of divisors function tau A000005 is nondecreasing.

Original entry on oeis.org

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

Offset: 1

Peter Luschny, Sep 03 2023

nonn

The sequence was inspired by A365339.

			The terms of the subsequences of A000005 are marked by '*'. They start:
  1*, 2,  2 , 3,  2, 4,  2, 4,  ... -> a(1) = 1
  1*, 2*, 2 , 3,  2, 4,  2, 4,  ... -> a(2) = 2
  1*, 2*, 2*, 3,  2, 4,  2, 4,  ... -> a(3) = 3
  1*, 2*, 2*, 3*, 2, 4,  2, 4,  ... -> a(4) = 4
  1*, 2*, 2*, 3*, 2, 4,  2, 4,  ... -> a(5) = 4
  1*, 2*, 2*, 3*, 2, 4*, 2, 4,  ... -> a(6) = 5
  1*, 2*, 2*, 3*, 2, 4*, 2, 4,  ... -> a(7) = 5
  1*, 2*, 2*, 3*, 2, 4*, 2, 4*, ... -> a(8) = 6
Example: a(2000000) = 450033.

Peter Luschny, Table of n, a(n) for n = 1..10000
Plot2, A365399 vs A365339.

Cf. A000005, A365339, A365398.

# Computes the first N terms of the sequence using function tau from A000005.
function LLS_list(seq, N)
    lst = zeros(Int64, N)
    dyn = zeros(Int64, N)
    for n in 1:N
        p = seq(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
A365399List(N) = LLS_list(tau, N)
println(A365399List(69))

from bisect import bisect
from sympy import divisor_count
def A365399(n):
    plist, qlist, c = tuple(divisor_count(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 04 2023

a(n+1) - a(n) <= 1.

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

Original entry on oeis.org

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

Terence Tao, Sep 01 2023

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

			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.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Thomas Bloom, Problem 49, Erdős Problems.
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.
Terence Tao, Erdős problem database, see no. 49.

Cf. A000010, A000720.

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

# 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

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

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)

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

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

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

Original entry on oeis.org

1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 11

Offset: 1

Chai Wah Wu, Sep 17 2023

nonn

Chai Wah Wu, 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.

Cf. A000010, A000720.

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

from bisect import bisect
from sympy import totient
def A365737(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

A365740 Length of the longest subsequence of {m: 1<=m<=n, m not prime} on which the Euler totient function phi A000010 is nondecreasing.

Original entry on oeis.org

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

Offset: 1

Chai Wah Wu, Sep 17 2023

nonn

Chai Wah Wu, 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 M2(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.

Cf. A000010, A000720.

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

from bisect import bisect
from sympy import totient, isprime
def A365740(n):
    plist = tuple(totient(i) for i in range(1,n+1) if not isprime(i))
    m = len(plist)
    qlist, c = [0]*(m+1), 0
    for i in range(m):
        qlist[a:=bisect(qlist,plist[i],lo=1,hi=c+1,key=lambda x:plist[x])]=i
        c = max(c,a)
    return c

Pollack et al. conjectured that a(n) < A365339(n)-2 for all n >= 31957.

A365741 a(n) = A365740(10^n).

Original entry on oeis.org

1, 5, 31, 189, 1261, 9595, 77681, 654249, 5650472

Offset: 0

Chai Wah Wu, Sep 17 2023

Pollack et al. listed a(4)-a(6).

Paul Pollack, Carl Pomerance and Enrique Treviño, Sets of monotonicity for Euler's totient function, preprint. See M2(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.

Cf. A000010, A000720.

Cf. A365398, A365399, A365400, A365474, A365737, A365740, A365742, A061070.

from bisect import bisect
from sympy import totient
def A365741(n):
    k = 10**n
    plist = tuple(totient(i) for i in range(1,k+1) if not isprime(i))
    m = len(plist)
    qlist, c = [0]*(m+1), 0
    for i in range(m):
        qlist[a:=bisect(qlist,plist[i],lo=1,hi=c+1,key=lambda x:plist[x])]=i
        c = max(c,a)
    return c

A365738 a(n) = A365737(10^n).

Original entry on oeis.org

1, 3, 12, 32, 92, 292, 995, 3029, 9651, 31817

Offset: 0

Chai Wah Wu, Sep 17 2023

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.

Cf. A000010, A000720.

Cf. A365398, A365399, A365400, A365474, A365737, A365740, A365741, A061070.

from bisect import bisect
from sympy import totient
def A365738(n):
    k = 10**n
    plist, qlist, c = tuple(-totient(i) for i in range(1,k+1)), [0]*(k+1), 0
    for i in range(k):
        qlist[a:=bisect(qlist,plist[i],lo=1,hi=c+1,key=lambda x:plist[x])]=i
        c = max(c,a)
    return c

a(9) from Chai Wah Wu, Oct 13 2023

A365742 Length of the largest subset of 1,...,n on which the Euler totient function phi A000010 is constant.

Original entry on oeis.org

1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10

Offset: 1

Chai Wah Wu, Sep 17 2023

nonn

Chai Wah Wu, Table of n, a(n) for n = 1..10000
R. C. Baker and G. Harman, Shifted primes without large prime factors, Acta Arith. 83 (1998), no. 4, 331-361.
Paul Erdős, On the normal number of prime factors of p - 1 and some related problems concerning Euler’s phi-function, Quart J. Math 6 (1935), 205-213.
Paul Pollack, Carl Pomerance and Enrique Treviño, Sets of monotonicity for Euler's totient function, preprint. See M0(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.

Cf. A000010, A000720.

Cf. A365398, A365399, A365400, A365474, A365737, A365738, A365740, A365741, A061070.

from collections import Counter
from sympy import totient
def A365742(n): return max(Counter(totient(i) for i in range(1,n+1)).values())

Pollack et al. showed that A365737(n)-a(n) > n^0.18 for large n.

A365748 a(n) = A365742(10^n).

Original entry on oeis.org

1, 3, 10, 30, 72, 247, 937, 2844, 9261, 30742

Offset: 0

Chai Wah Wu, Sep 17 2023

R. Baker and G. Harman, Shifted primes without large prime factors, Acta Arithmetica 83 (1998), pp. 331-361.
Paul Pollack, Carl Pomerance, and Enrique Treviño, Sets of monotonicity for Euler's totient function, preprint. See M0(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.

Cf. A000010, A000720.

Cf. A365398, A365399, A365400, A365474, A365737, A365738, A365740, A365741, A365742, A061070.

from collections import Counter
from sympy import totient
def A365748(n): return max(Counter(totient(i) for i in range(1,10**n+1)).values())

Baker and Harman showed that a(n) >= 10^(0.7038n) for all large enough n. - Chai Wah Wu, Oct 17 2023

A371156 Length of the longest subsequence of 1, ..., n on which the Dedekind psi function (A001615) is nondecreasing.

Original entry on oeis.org

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

Offset: 1

Chai Wah Wu, Apr 10 2024

nonn

The envelope max_{i<=n} (a(i)-A000720(i)) appears to be slowly increasing as n increases. For instance, a(1)-A000720(1)=1, whereas a(374598)-A000720(374598)=91 and a(642852)-A000720(642852)=96.

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

Chai Wah Wu, Table of n, a(n) for n = 1..10000
Terence Tao, Monotone non-decreasing sequences of the Euler totient function, arXiv:2309.02325 [math.NT], 2023. See Remark 4.7.

Cf. A000720, A001615, A365339, A365399, A365397, A365398, A365740.

Length[LongestOrderedSequence[#]] & /@ Rest[FoldList[Append, {}, Table[n DivisorSum[n, MoebiusMu[#]^2/# &], {n, 20}]]] (* Eric W. Weisstein, Mar 09 2025 *)

from math import prod
from bisect import bisect
from sympy import primefactors
def A371156(n):
    def f(n):
        r = primefactors(n)
        return n*prod(p+1 for p in r)//prod(r)
    plist, qlist, c = tuple(f(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

0 <= a(n+1) - a(n) <= 1.

a(n) >= A000720(n)+1 since A001615(p) = p+1 for p prime.

cp's OEIS Frontend

A365397 a(n) = 64 + A000720(n) - A365398(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Formula

A365399 Length of the longest subsequence of 1, ..., n on which the number of divisors function tau A000005 is nondecreasing.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Julia

Python

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Julia

Mathematica

Python

Python

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

Python

A365740 Length of the longest subsequence of {m: 1<=m<=n, m not prime} on which the Euler totient function phi A000010 is nondecreasing.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Formula

A365741 a(n) = A365740(10^n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

A365738 a(n) = A365737(10^n).

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Extensions

A365742 Length of the largest subset of 1,...,n on which the Euler totient function phi A000010 is constant.

Views

Author

Keywords

Links

Crossrefs

Programs

Python