I've been considering the sequence of natural numbers with prime factorization $pq^2$, $p\neq q$; it begins 12, 18, 20, 28, 44, 45, ... and is A054753 in OEIS. I have two questions:

  1. What is the longest run (a subsequence that consists of consecutive integers)?

    The first run of length 3 is 603, 604, 605. There are another 256 runs of length 3, and no longer runs, less than $10^7$. Can it be shown that runs of length 4 and 5 are not possible?

    All I've managed to work out is that runs of length 6 are impossible (because one of the numbers would have to have 6 as a factor), and that any run of length 5 needs to consist of the numbers $48k+i$ for some $k$ and $i=1 \dots 5$.

  2. Are there more even or odd numbers in the sequence? More specifically, what is the asymptotic ratio, $\rho=\lim\limits_{N\to\infty}E_N/O_N$, of the number of even elements to the number of odd elements less than $N$.

    The following two graphs suggest that $E_N$ exceeds $O_N$ for large $N$. The first plots $E_N-O_N$, and the second $E_N/O_N$, against $N$. It appears that even numbers finally gain the ascendancy for good at $N=222436$.

    Graph 1

    Graph 2

All I've managed to determine is that $E_N \sim\frac{N}{4 \log \left(\frac{N}{4}\right)}+\frac{\sqrt{2N}}{\log \left(\frac{N}{2}\right)}$. I'm also pretty sure than $O_N$ is also $\Theta(\frac{N}{\log N})$ and hence $\rho$ is a constant.

I'm not a number theory expert (more an amateur combinatorialist), so I've no idea how hard these questions are. Any insight would be gratefully received.

  • 1
    $\begingroup$ 2 Shouldn't be hard, its the hyperbola method. $\endgroup$ Commented Sep 15, 2011 at 21:16
  • 1
    $\begingroup$ Anyone got anything to say about question 1? $\endgroup$ Commented Sep 16, 2011 at 7:31
  • $\begingroup$ What's wrong with a number having $6$ as a factor? $\endgroup$
    – Nishant
    Commented Aug 4, 2014 at 23:49
  • $\begingroup$ @Nishant, the only numbers of the form $pq^2$ having $6$ as a factor are $12$ and $18$. $\endgroup$ Commented Sep 29, 2014 at 14:33
  • $\begingroup$ Ah, of course. Thanks! $\endgroup$
    – Nishant
    Commented Sep 29, 2014 at 16:56

3 Answers 3


To answer question 1, if $n = 266667848769941521$, then

$$\begin{align*} n & = 7^2 \cdot 5442200995304929,\\ n+1 & = 365149181^2 \cdot 2,\\ n+2 & = 3^2 \cdot 29629760974437947,\\ n+3 & = 2^2 \cdot 66666962192485381,\\ n+4 & = 5^2 \cdot 10666713950797661. \end{align*}$$

  • $\begingroup$ That's extraordinary! How did you go about finding a solution? $\endgroup$ Commented Sep 17, 2011 at 9:25
  • $\begingroup$ The first run of length four begins at $n=17042641441$: $n=7^2 \times 347809009$; $n+1=2 \times 92311^2$; $n+2=3^2 \times 1893626827$; $n+3=2^2 \times 4260660361 $. $\endgroup$ Commented Sep 17, 2011 at 12:33
  • $\begingroup$ And the first run of length 5 begins at $n=10093613546512321$: $\ n=7^2 \times 205992113194129$; $\ n+1=2 \times 71040881^2$; $\ n+2=3^2 \times 1121512616279147$; $\ n+3=2^2 \times 2523403386628081$; $\ n+4=5^2 \times 403744541860493$. $\endgroup$ Commented Sep 17, 2011 at 12:52

Edit: The outline of the proof which I posted previously was hard to follow, and omitted an enormous amount of details. This has now been updated and much has been added, however some details are still omitted.

Question 2:

Since we know $$E_n\sim \frac{1}{4}\frac{x}{\log x},$$ we need only find an asymptotic for $\sum_{pq^2\leq x} 1$, the number of integers of the form $pq^2$ less then $x$.

Theorem: We have that $$\sum_{\begin{array}{c} n\leq x\\ n=pq^{2} \end{array}}1=\sum_{pq^2\leq x} 1 \sim \frac{x}{\log x}\sum_{p} \frac{1}{p^2}. $$

Heuristic: If we looked at the case where one of the primes was $2$, we got the asymptotic $\frac {1}{4} \frac{x}{\log x}$. In the same way, if one of the primes must be $3$ we get $\frac {1}{9} \frac{x}{\log x}$ and if one of the primes must be $5$ we get $\frac {1}{25} \frac{x}{\log x}$. Summing over everything then gives $\sum_p \frac{1}{p^2}$ as the constant.


Step 1: First, we show that $$\log x\sum_{pq^2\leq x} 1\sim \sum_{pq^2\leq x} \log (pq^2).$$ Clearly $\log x\sum_{pq^2\leq x}1\geq \sum_{pq^2\leq x} \log (pq^2)$. For the other direction let $2\leq f(x)\leq x$ be some soon to be chosen function. Then $$\sum_{pq^{2}\leq x}\log(pq^{2})\geq\sum_{f(x)<pq^{2}\leq x}\log(pq^{2})\geq\log\left(f(x)\right)\sum_{f(x)<pq^{2}\leq x}1.$$ Taking $f(x)=\frac{x}{\log^{2}x}$ we see that $$\log\left(f(x)\right)\sum_{f(x)<pq^{2}\leq x}1\sim\log x\sum_{pq^{2}\leq x}1.$$ Since $\sum_{pq^2\leq x} \log (pq^2)$ is bounded above and below by something asymptotic to $\log x\sum_{pq^2\leq x} 1$ we conclude the desired asymptotic.

Step 2: We prove that $$\sum_{pq^2\leq x} \log (q^2) =o(x).$$ Rearranging we have $$\sum_{pq^{2}\leq x}\log\left(q^{2}\right)=2\sum_{p\leq x}\sum_{q\leq\sqrt{\frac{x}{p}}}\log\left(q\right).$$ Chebyshevs estimate gives $\sum_{q\leq u}\log\left(q\right)\ll u $ so that $$\sum_{pq^{2}\leq x}\log\left(q^{2}\right)\ll\sum_{p\leq x}\sqrt{\frac{x}{p}}=\sqrt{x}\sum_{p\leq x}\frac{1}{\sqrt{p}}.$$ Let $2\leq f(x)\leq x$ be some soon to be chosen function. Then splitting we see that $$\sqrt{x}\sum_{p\leq x}\frac{1}{\sqrt{p}}\leq\sqrt{x}\sum_{n\leq f(x)}\frac{1}{\sqrt{n}}+\sqrt{x}\sum_{f(x)<p\leq x}\frac{1}{\sqrt{p}}.$$ By the prime number theorem and partial summation $$\sqrt{x}\sum_{f(x)<p\leq x}\frac{1}{\sqrt{p}}=\sqrt{x}\int_{f(x)}^{x}\frac{1}{\sqrt{t}\log t}dt+O\left(xe^{-c\sqrt{\log f(x)}}\right)$$ so that if we take $f(x)=\frac{x}{\log^{2}x}$ with some computation we find $$\sqrt{x}\sum_{p\leq x}\frac{1}{\sqrt{p}}\ll\frac{x}{\log x}=o(x).$$

Step 3: We use the hyperbola method to show that $$\sum_{pq^2\leq x} \log (p)\sim x \sum_{p} \frac{1}{p^2}.$$ Although it is straightforward why we should have this asymptotic, the hyperbola method and splitting the sum must be used to control the error term. We have that $$\sum_{pq^{2}\leq x}\log(p)=\sum_{q^{2}\leq x}\sum_{p\leq\frac{x}{q^{2}}}\log p=\sum_{q^{2}\leq f(x)}\sum_{p\leq\frac{x}{q^{2}}}\log p+\sum_{f(x)<q^{2}\leq x}\sum_{p\leq\frac{x}{q^{2}}}\log p $$

$$=\sum_{q^{2}\leq f(x)}\sum_{p\leq\frac{x}{q^{2}}}\log p+\sum_{p\leq\frac{x}{f(x)}}\log p\sum_{f(x)<q^{2}\leq\frac{x}{p}}1.$$

By the prime number theorem $$\sum_{p\leq\frac{x}{q^{2}}}\log p=\frac{x}{q^{2}}+O\left(\frac{x}{q^{2}\log\left(\frac{x}{q^{2}}\right)}\right)=\frac{x}{q^{2}}+O\left(\frac{x}{q^{2}\log\left(\frac{x}{f(x)}\right)}\right)$$ where the last term comes from the fact that $q^{2}\leq f(x)$. Then

$$\sum_{q^{2}\leq f(x)}\sum_{p\leq\frac{x}{q^{2}}}\log p=x\sum_{q^{2}\leq f(x)}\frac{1}{q^{2}}+O\left(\frac{x}{\log\left(\frac{x}{f(x)}\right)}\sum_{q\leq f(x)}\frac{1}{q^{2}}\right)=x\sum_{q}\frac{1}{q^{2}}+O\left(\frac{x}{\log\left(\frac{x}{f(x)}\right)}+\frac{x}{\sqrt{f(x)}}\right).$$

For the other sum, by chebyshevs estimate $$\sum_{p\leq\frac{x}{f(x)}}\log p\sum_{f(x)<q^{2}\leq\frac{x}{p}}1\ll\frac{1}{\log\left(\sqrt{f(x)}\right)}\sum_{p\leq\frac{x}{f(x)}}\log p\left(\sqrt{\frac{x}{p}}\right).$$ Taking $f(x)=\frac{x}{\log x}$ we obtain $$\sum_{pq^{2}\leq x}\log(p)=x\sum_{q}\frac{1}{q^{2}}+o(x)$$ as desired.

Combining Steps 1-3:

By step 1 we have $$\sum_{pq^2\leq x} 1\sim \frac{1}{\log x}\sum_{pq^2\leq x} \log(pq^2) =\frac{1}{\log x}\sum_{pq^2\leq x} \log(p)+\frac{1}{\log x}\sum_{pq^2\leq x} \log(q^2).$$ Applying steps 2 and 3 to the right hand side we see that $$\sum_{pq^2\leq x} 1 \sim \frac{x}{\log x} \sum_p \frac{1}{p^2}$$ proving our asymptotic.

Consequences: We then have that $$O_N\sim \frac{N}{\log N} \sum_{p>2} \frac{1}{p^2}.$$ Notice this means that $E_N>O_N$, and the ratio is $$\frac{O_N}{E_N}\sim 4\sum_{p>2} \frac{1}{p^2}.$$

To keep in line with your graph above, $$\frac{E_N}{O_N}\sim \frac{1}{4\sum_{p>2} \frac{1}{p^2}}$$

Remark about the proof: The proof of this fact is loosely based on some ideas in E. M. Wright's 1951 paper "A Simple Proof of a Theorem of Landau." That paper looks at $\sum_{pq\leq x} 1$ and the higher products.

  • 3
    $\begingroup$ Numerically, this means $O_N/E_N \sim 0.8089 \cdots$. $\endgroup$ Commented Sep 16, 2011 at 0:16
  • $\begingroup$ @Eric Naslund This was for $p q^2$ ..if we consider $pq ^k$ does the sum became $\frac{O_N}{E_N}\sim 4\sum_{p>2} \frac{1}{p^k}$ ? $\endgroup$ Commented May 30, 2014 at 7:30

Question 1:

The following approach can be used to find runs of length 4 or 5:

Any run of length 4 or more contains an element $a$ such that $a \bmod 4 \equiv 2$, so $a=2p^2$ for some prime $p$.

Since, for all prime $p>5$, $p^2\bmod120\in\{1,49\}$, we have that $a=240k+2$ or $240k+98$ for some $k$.

We also have that either $a-2$ or $a+2$ is in the run and equals $4q$ for some prime $q$. Since none of $240k/4$, $(240k+96)/4$ and $(240k+100)/4$ is prime, we know that $a=240k+2$ and that the run contains $a$, $a+1$ and $a+2$, with $a+1=9r$ or $3r^2$ for some prime $r$. Also, if $a+3$ is in the run, it equals $25s$ or $5s^2$ for some prime $s$.

For each prime $p$, with $a=2p^2$, we check the following:

  1. Is $a\equiv2\pmod{240}$?
  2. Is $(a+2)/4$ prime?
  3. Is $(a+1)/9$ or $\sqrt{(a+1)/3}$ a prime?
  4. Is $(a+3)/25$ or $\sqrt{(a+3)/5}$ a prime?
  5. Does $a-1$ have prime decomposition of the form $uv^2$?

If all 5 tests succeed, we have a run of length 5; if tests 1-4, or tests 1-3 and 5, succeed, we have a run of length 4.

The 16 runs of length five less than $7 \times 10^{18}$ begin with the numbers:

$$ \begin{align*} 10093613546512321&=7^2\times 205992113194129 \\ 14414905793929921&=7^2\times 294181750896529 \\ 266667848769941521&=7^2\times 5442200995304929 \\ 562672865058083521&=7^2\times 11483119695062929 \\ 1579571757660876721&=7^2\times 32236158319609729 \\ 1841337567664174321&=7^2\times 37578317707432129 \\ 2737837351207392721&=7^2\times 55874231657293729 \\ 4456162869973433521&=7^2\times 90942099387212929 \\ 4683238426747860721&=7^2\times 95576294423425729 \\ 4993613853242910721&=7^2\times 101910486800875729 \\ 5037980611623036721&=7^2\times 102815930849449729 \\ 5174116847290255921&=7^2\times 105594221373270529 \\ 5344962129269790721&=23^2\times 10103898164971249 \\ 5415192610051711921&=7^2\times 110514134899014529 \\ 6478494344271550321&=7^2\times 132214170291256129 \\ 6644601589030969921&=7^2\times 135604114061856529 \end{align*} $$

  • $\begingroup$ You can probably find all integers (not even primes) p where a+1 is 3 times a square, or a+3 is 5 times a square, very quickly, and there won't be many; that will simplify the problem. Then you have three numbers that must all be prime. That's fastest to disprove if you check that small numbers divide one of them which is quite likely. This should throw out many non-solutions very quickly. $\endgroup$
    – gnasher729
    Commented Jul 18, 2017 at 11:57

You must log in to answer this question.

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