I hope this is okay for the site, I asked on math exchange with no answer.

Consider the function $f(n)$ defined on the natural integers which returns the largest prime factor of $n$, and is $0$ for $1$. For example, $f(9)=3$,$f(15)=5$.

A beautiful riddle says that there are infinitely many $n$ so that $f(n)<f(n+1)<f(n+2)$.

I have 2 questions:

1.Given $k$, are there infinitely many $n$ so that $f(n)<f(n+1)...<f(n+k)$?

2.How often is $f(n)<f(n+1)$?

I'd guess is true because we can take large primes that are near each other, and with chinese reminder theorm make $n+i$ be divisible by $p_i$ and hope that after we divide all the other prime factors are small.

Proof of the riddle:

Lemma 1, if $f(a)<c, f(b)<c$, then $f(ab)<c$.

For any odd prime $q$ we find such different $n$, as there are infinitely many different odd primes we're done.

Choose an odd prime $q$, try $n+1=q$. Obviously $f(n)<f(n+1)$.

If $f(n+1)<f(n+2)$ we're done. Otherwise, choose $n+1$=$q^2$. Now $f(n)=f(q^2-1)=f((q−1)(q+1))$, so by lemma 1, by setting $a=q-1$, $b=q+1$, $c=q$ we get $f(n)<f(n+1)$. Again if $f(n+1)<f(n+2)$ we're done, otherwise choose $n+1=q^4$ and keep going like that. Assume by contradiction this goes on forever, then $q=f(q^{2^k})>f(q^{2^k}+1)$ for all $k$, but $gcd(q^{2^k}+1,q^{2^m}+1) = 1$ for all different $m,n$, and so eventually they contain primes larger than $q$, contradiction.

  • 1
    $\begingroup$ The function $f(n)$ is tabulated at oeis.org/A006530 with many references and links. $\endgroup$ – Gerry Myerson Feb 7 '17 at 22:19
  • 1
    $\begingroup$ Also related are oeis.org/A070087 ($P(n) > P(n+1)$ where $P(n)$ is the largest prime factor of $n$.) and oeis.org/A070089 ($P(n) < P(n+1)$ where $P(n)$ is the largest prime factor of $n$.). $\endgroup$ – Gerry Myerson Feb 7 '17 at 22:23
  • 2
    $\begingroup$ oeis.org/A079749 is the sequence this question is asking about. $\endgroup$ – Kevin Buzzard Feb 7 '17 at 22:25
  • 1
    $\begingroup$ Or possibly oeis.org/A100384 , the difference being whether or not you count e.g. the smallest run of 8 as being the same as the smallest run of 9 (the smallest run of 9 occurs before the smallest run of 8!) $\endgroup$ – Kevin Buzzard Feb 7 '17 at 22:28
  • 3
    $\begingroup$ Erdos and Pomerance, On the largest prime factors of $n$ and $n+1$, Aequationes Mathematicae 17 (1978) 311-321 give the same construction of infinitely many triples with $f(n)<f(n+1)<f(n+2)$. "On the other hand, we cannot find infinitely many $n$ for which [$f(n)>f(n+1)>f(n+2)$], but perhaps we overlook a simple proof." A proof is given by Balog, On triplets with descending largest prime factors, Studia Sci Math Hungar 38 (2001) 45-50 (but I wouldn't call it a simple proof). $\endgroup$ – Gerry Myerson Feb 8 '17 at 3:01

As Kevin Buzzard suggests in a comment, this would be a consequence of one of the "standard conjectures on primes", namely the first Hardy-Littlewood conjecture (which is the special case of Schinzel's hypothesis H where all the polynomials are linear). If $N$ is sufficiently divisible, say $N = {\rm lcm}(1,2,3,\ldots,k)^2$, then each of $(Nx-i)/i$ for $i=1,2,3,\ldots,k$ is a linear polynomial in $x$ that always takes integer values not divisible by any prime $\leq k$, so Hardy-Littlewood predicts the existence of infinitely many $x$such that each of these $(Nx-i)/i$ is prime; then the largest prime factors of the $k$ integers in $[Nx-k,Nx)$ are in increasing order. The same argument applied to $(Nx+i)/i$ would likewise produce infinitely many runs of $k$ integers $Nx+i$ ($i=1,\ldots,k$) whose largest prime factors are $(Nx+i)/i$ and are thus in decreasing order.


I think at this point it is safe to say that the answer to question 1 is, conjecturally yes but nothing has been proved for any $k\ge3$, and the answer to question 2 is, conjecturally half the time (in the limit, as $n\to\infty$) but this too has not been proved.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.