8
$\begingroup$

For $n=3$, $\sigma(n)=4$, a perfect square. Calculating further was not yielding positive results.

I was wondering is there a way to find all such an $n$, like some algorithm?

We know that if $n=p_1^{k_1}p_2^{k_2}\dots p_r^{k_r}$ then $\sigma(n)=\frac {p_1^{k_1+1}-1}{p_1-1} \frac{p_2^{k_2+1}-1}{p_2-1}\dots \frac {p_r^{k_r+1}-1}{p_r-1}$. So we have to find $n$ such that $\sigma(n)=\frac {p_1^{k_1+1}-1}{p_1-1} \frac{p_2^{k_2+1}-1}{p_2-1}\dots \frac {p_r^{k_r+1}-1}{p_r-1}=t^2$ for some integer $t$. If each $\frac{p_i^{k_i+1}-1}{p_i-1}$ is a square we will get some such numbers (not all though), but let us consider $\frac{p_i^{k_i+1}-1}{p_i-1}=m^2$.

Working a example, If I take $p_i=17 $ , (or any prime such that $p_i-1$ is a perfect square), then if I can find a $k_i$ such that ${p_i^{k_i+1}-1}=16.m^2$ I will get an $n$, so now when can this happen, is something I have to try out.

But out of curiosity I am asking has this been worked out before. Problem looks broad to me, Is there a solution to this problem?

$\endgroup$
  • $\begingroup$ Maybe this is helpful $\endgroup$ – Bman72 May 19 '15 at 17:10
  • $\begingroup$ No this was not helpful @Ale. Seen it $\endgroup$ – Bhaskar Vashishth May 19 '15 at 17:13
  • $\begingroup$ $\sigma(81)=11^2$. $\endgroup$ – mathlove May 19 '15 at 17:15
  • 3
    $\begingroup$ oeis.org/A006532 indicates it's only conjectural that there are infinitely many such numbers. It also gives some references. $\endgroup$ – Barry Cipra May 19 '15 at 17:28
  • 1
    $\begingroup$ The first 10,000 are listed at oeis.org/A006532/b006532.txt After about entry 20 these become more frequent than squares, that is entry number $n$ becomes smaller than $n^2,$ and it continues that way. This makes me think it's a good bet that there are infinitely many. $\endgroup$ – Will Jagy May 19 '15 at 18:54
2
$\begingroup$

I came up with an algorithm, decades ago. Kap was interested in solving $\sigma(x^3) = y^2,$ where the next simplifying hypothesis was that $x$ would be squarefree. He referred to these problems with the name Ozanam, from somewhere in Dickson's History.

The reason something can be done is that it is possible to regard odd/even exponents as numbers $0,1$ and perform row reductions using Gauss methods in the field with two elements.

So, take the primes up to $100,$ say. Each prime gets a column in a certain matrix. For each prime, factor (in my case ) $\sigma(p^3),$ and assign a row for every prime that comes up in at least one of these factorizations.

The column for prime $p$ gets mostly $0$ entries, but gets a $1$ at every prime factor of $\sigma(p^3)$ that occurs to an odd power.

An answer to the original problem is a vector in the nullspace of this matrix, that is a vector consisting of either $0$ or $1$ that is sent to all $0$ over the field with two elements. This is, simply, a choice of the prime factors of a (squarefree) solution.

None of this was easy, but the program was lightning fast.

One could customize this for $\sigma(x)$ = y^2 by dropping the $x^3$ aspect, instead, for a few primes of interest, replace the column for $p$ by the column for the preferred $p^a.$ I did some of that at the time. It is less elegant, there are some nice features to keeping homogeneity of exponents.

$\endgroup$
  • $\begingroup$ Will, does your algorithm guarantee infinitely many examples? Because the OEIS seems to be unsure (see my comment to the OP). $\endgroup$ – Barry Cipra May 19 '15 at 18:00
  • $\begingroup$ @BarryCipra, I don't remember considering that very carefully, I just got the impression that there would be infinitely many, even among squarefree, partly because one may take the product of two of them and divide out any square factors. Hmmm. I suspect if we had a proof of infinite cardinality Kap would have written that up and distributed to interested parties, the way he did, so I think we had no proof. $\endgroup$ – Will Jagy May 19 '15 at 18:24
  • $\begingroup$ @BarryCipra, for what it's worth, the table oeis.org/A006532/b006532.txt has these examples as being more frequent than squares when considered in dictionary order. That takes no account of structure, of course. $\endgroup$ – Will Jagy May 19 '15 at 18:40
  • 1
    $\begingroup$ If you have easy access to Dickson's History of the Theory of Numbers vol. I, take a look at page 54. It says Fermat proposed the problem "Find a cube which when increased by the sum of its aliquot parts becomes a square; for example $7^3+(1+7+7^2)=20^2$." This is precisely the problem $\sigma(x^3)=y^2$. Ozanam is mentioned on page 56. Also on page 56: "E. Lucas stated that there is an infinitude of solutions of Fermat's problem." Note the word "stated," not "proved." $\endgroup$ – Barry Cipra May 19 '15 at 19:01
  • $\begingroup$ @BarryCipra, thank you, I have the three volumes. On page 55, the methods of Wallis are close to what Kap and I did. Ozanam on page 56 does not seem quite right. Maybe I am remembering Kap writing about some variant under the name Ozanam, possibly $\sigma(x^2) = y^3,$ which never went anywhere. Matrices over the field with two elements behaved well; over the field with three elements it all bogged down. Alright, Lucas on page 56 means Fermat (i) on page 54; if restricted to squarefree numbers is what Kap and I did. $\endgroup$ – Will Jagy May 19 '15 at 19:11
0
$\begingroup$

Here is where I approached a more general problem from an algorithm standpoint. However, the discussion involved should answer your question.

$\endgroup$
  • $\begingroup$ In this answer you have talked about number of divisors, but what I posted was about sum of divisor. It does not answer it, sorry $\endgroup$ – Bhaskar Vashishth May 23 '15 at 17:54

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.