4
$\begingroup$

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.

$\endgroup$
9
  • 1
    $\begingroup$ The function $f(n)$ is tabulated at oeis.org/A006530 with many references and links. $\endgroup$ Commented Feb 7, 2017 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$ Commented Feb 7, 2017 at 22:23
  • 2
    $\begingroup$ oeis.org/A079749 is the sequence this question is asking about. $\endgroup$ Commented Feb 7, 2017 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$ Commented Feb 7, 2017 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$ Commented Feb 8, 2017 at 3:01

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .