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