10
$\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$
9
  • $\begingroup$ Maybe this is helpful $\endgroup$
    – Bman72
    May 19, 2015 at 17:10
  • $\begingroup$ No this was not helpful @Ale. Seen it $\endgroup$ May 19, 2015 at 17:13
  • $\begingroup$ $\sigma(81)=11^2$. $\endgroup$
    – mathlove
    May 19, 2015 at 17:15
  • 4
    $\begingroup$ oeis.org/A006532 indicates it's only conjectural that there are infinitely many such numbers. It also gives some references. $\endgroup$ May 19, 2015 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, 2015 at 18:54

2 Answers 2

3
$\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$
8
  • $\begingroup$ Will, does your algorithm guarantee infinitely many examples? Because the OEIS seems to be unsure (see my comment to the OP). $\endgroup$ May 19, 2015 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, 2015 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, 2015 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$ May 19, 2015 at 19:01
  • 1
    $\begingroup$ I think it would suffice to consider 3x3 matrices. I was working on a similar problem earlier, then stumbled upon your comment from $2015$. (My apologies for disturbing you.) At any rate, I will try to type up what I have and then send you a copy. =) $\endgroup$ May 14, 2023 at 21:52
0
$\begingroup$

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

$\endgroup$
1
  • $\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$ May 23, 2015 at 17:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .