Sequence of numbers with prime factorization $pq^2$

Question

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$.

   

   

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.

Answer 1

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*}$$

Answer 2

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.

Proof:

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.

Answer 3

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*} $$