Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

3 Answers 3

up vote 13 down vote accepted

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.

share|improve this answer
3  
Numerically, this means $O_N/E_N \sim 0.8089 \cdots$. –  Michael Lugo Sep 16 '11 at 0:16
    
Thanks, that's very helpful. –  David Bevan Sep 16 '11 at 7:31
    
@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}$ ? –  Shivam Patel May 30 at 7:30

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

share|improve this answer
    
That's extraordinary! How did you go about finding a solution? –  David Bevan Sep 17 '11 at 9:25
    
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 $. –  David Bevan Sep 17 '11 at 12:33
    
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$. –  David Bevan Sep 17 '11 at 12:52

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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