So the question goes like this :

A positive integer $n$ is called square-full if for every prime $p$, $p \, | \, n$ implies $p^2 \, | \, n$, i.e. every prime power factor of $n$ occurs at least at the second power. This is equivalent to saying that there is no prime $p$ such that $p \, \| \, n$.

Show that there are infinitely many consecutive pairs of square-full numbers, i.e. infinitely many $n$ such that $n$ and $n+1$ are square-full.

The context of the question highly suggests that this can be proved by induction and it is the solution that I am looking for. It is not a homework, just something that caught my attention because I couldn't find any natural answer to it... I hope I'm not missing something trivial!

I've tried assuming $n_1, n_2, \dots, n_k$ were the first $n_k$ integers such that $n_i$ and $n_i+1$ are square-full, and then generate some polynomial in those $2k$ integers to get a new couple $n_{k+1}$, $n_{k+1} + 1$ but after a few natural tries I got nothing good out of it. Any ideas?


Any product of square-full numbers is square-full.

$4n(n+1) $ is square-full if n, n+1 are.

list of square-full numbers at http://oeis.org/A060355

  • 1
    $\begingroup$ You might want to add an initial pair to show existence :-) $\endgroup$ – robjohn Nov 10 '11 at 14:42
  • $\begingroup$ She added a list of square-full numbers, that is an initial pair enough. Anyway at this point I was not looking for a full proof but rather for ideas. The idea here is good enough. $\endgroup$ – Patrick Da Silva Nov 10 '11 at 18:46
  • 1
    $\begingroup$ @Patrick: Since Angela had given the inductive step, I was simply suggesting that an initial pair would make for a nice completion. I wasn't suggesting that her answer was wrong in any way. $\endgroup$ – robjohn Nov 11 '11 at 0:19
  • 1
    $\begingroup$ Read comments better : isn't a list of square-full numbers an initial pair enough?... $\endgroup$ – Patrick Da Silva Nov 11 '11 at 0:20
  • 2
    $\begingroup$ Putting aside the rudeness of the last comment, there is an inconsistency here: the OEIS contains the initial step of the recursion (there exist (nonzero) solutions) and the inductive step (if n is a solution, then 4n(n+1) is). Why reproduce the latter and not the former? (And why omit the argument that 4n(n+1)>n...) Additionally, I seem to remember that non self-contained answers are frowned upon on the site (and for very good reasons, if you ask me). Hence (as explained by @robjohn), mentioning at least one solution (and giving the link, of course) was clearly a better option. $\endgroup$ – Did Nov 11 '11 at 7:36

Suppose that $a_0=1$, $a_1=3$, $b_0=0$, and $b_1=2$. Let $a_n=6a_{n-1}-a_{n-2}$ and $b_n=6b_{n-1}-b_{n-2}$. Then $a_n^2-2b_n^2=1$ and $a_na_{n-1}-2b_nb_{n-1}=3$.

This means that $a_n^2$ and $2b_n^2$ are adjacent integers, and since $b_n$ is even both are obviously square-full for $n>0$.

Inductive Verification: $$ \begin{align} a_n^2-2b_n^2 &=(6a_{n-1}-a_{n-2})^2-2(6b_{n-1}-b_{n-2})^2\\ &=(36a_{n-1}^2-12a_{n-1}a_{n-2}+a_{n-2}^2)-2(36b_{n-1}^2-12b_{n-1}b_{n-2}+b_{n-2}^2)\\ &=36(a_{n-1}^2-2b_{n-1}^2)+(a_{n-2}^2-2b_{n-2}^2)-12(a_{n-1}a_{n-2}-2b_{n-1}b_{n-2})\\ &=36+1-36\\ &=1 \end{align} $$ and $$ \begin{align} a_na_{n-1}-2b_nb_{n-1} &=(6a_{n-1}-a_{n-2})a_{n-1}-2(6b_{n-1}-b_{n-2})b_{n-1}\\ &=(6a_{n-1}^2-a_{n-1}a_{n-2})-2(6b_{n-1}^2-b_{n-1}b_{n-2})\\ &=6(a_{n-1}^2-2b_{n-1}^2)-(a_{n-1}a_{n-2}-2b_{n-1}b_{n-2})\\ &=6-3\\ &=3 \end{align} $$

  • $\begingroup$ $b_3=5$, right? So $2b_3^2$ wouldn't be square-full. $\endgroup$ – Gerry Myerson Nov 10 '11 at 11:48
  • $\begingroup$ @Gerry: Oops. I misread the definition of square-full. I will fix. $\endgroup$ – robjohn Nov 10 '11 at 12:28
  • $\begingroup$ A little too complicated, but thanks for trying. $\endgroup$ – Patrick Da Silva Nov 10 '11 at 18:46
  • $\begingroup$ @Patrick: you make it sound as if I've lost a competition. I am merely answering your question, and although not as concise as the recursive formula from the OEIS, it is still a valid, and I think worthwhile, answer. $\endgroup$ – robjohn Nov 11 '11 at 0:21
  • $\begingroup$ Sorry, maybe I wrote my comment the wrong way. What I meant was ; thanks for considering my question, your answer is just fine, but I just don't think it's very elegant. Angela's is wayy more. Although I'd be interested in knowing how you came up with such a thing. I upvoted it, just so you know. $\endgroup$ – Patrick Da Silva Nov 11 '11 at 0:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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