A391750 Maximum length of an increasing sequence, bounded by n, in which the largest prime divisors of the elements form a decreasing sequence.

1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 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, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8

Offset

2,3

Comments

First differs from A000523 at index 48.

References

Paul Erdős, Some problems in number theory. Octogon Math. Mag. (1995), 3-5.

Links

Table of n, a(n) for n=2..100.

Thomas Bloom, Problem #648, Erdős Problems.

Stijn Cambie, On Erdős problem #648, arXiv:2503.22691 [math.NT], 2025.

Formula

a(n) = Theta(sqrt(n / log n)) (Cambie).

Example

a(8)=3 because 5,6,8 is increasing, but the greatest prime factors 5,3,2 are decreasing. - Michael B. Porter, Dec 23 2025

Mathematica

gpfs[n_]:=FactorInteger[#][[-1, 1]]&/@Range[n];
a[n_]:=Length[LongestCommonSequence[gpfs[n], Reverse[Prime@Range[PrimePi[n]]]]]

Crossrefs

Cf. A391751 (record indices).

Cf. A000523.

Sequence in context: A029835 A074280 A000523 * A124156 A324965 A072749

Adjacent sequences: A391747 A391748 A391749 * A391751 A391752 A391753

Keyword

nonn

Author

Elijah Beregovsky, Dec 18 2025

Status

approved