10
$\begingroup$

This question related to this question from SE. I'm interested to know if there exists an integer $x>1$ that satisfies $${\sigma}^{k}(x)\equiv 0\pmod{x}$$ for all positive integers $k$.

Note. $\sigma(x)$ is the sum of divisors of $x$, and ${\sigma}^{k}(x )=\sigma(\sigma(\sigma(\sigma(\cdots x))))$ is $\sigma$ iterated $k$ times.

Edit. I edited the question to avoid the trivialities.

$\endgroup$
5
  • $\begingroup$ There are also multiperfect numbers. I suspect there is a proof that metaperfect numbers (infinitely iterated form of multiperfects) do not exist. Gerhard "Likes Using The Term 'Metaperfect'" Paseman, 2015.07.14 $\endgroup$ Jul 14, 2015 at 23:32
  • $\begingroup$ I suspect that such an $x$ does not exist, but proving it will be very hard. $\endgroup$
    – GH from MO
    Jul 14, 2015 at 23:49
  • $\begingroup$ @GHfromMO, I think should be for x to be perfect number for all k and this is very hard $\endgroup$ Jul 15, 2015 at 0:09
  • $\begingroup$ @Ricardo Andrade, thank you for your edition to the question $\endgroup$ Jul 20, 2015 at 0:38
  • $\begingroup$ @Ricardo Andrade, do you have any counter example for the above question ? $\endgroup$ Jul 20, 2015 at 1:59

2 Answers 2

1
+50
$\begingroup$

I've decided to collect some basic observations and references for the benefit of future readers.

A more challenging problem is to ask for integers $m$ and $p$ such that for all integers $k$, $p_0 = p, p_{k+1}=\sigma(p_k),$ and $p_k = 0 \bmod m$. The current problem adds the restriction that $p=m$, which implies $m$ is a multiperfect number. Since multiperfect numbers are rare, it should be hard to find a metaperfect number, a number $m$ that satisfies $\sigma^k(m) = 0 \bmod m$ for all iterations of $\sigma$.

Indeed, $\sigma(m) \lt m\omega(m)$ for most values of $m$, so for a potentially metaperfect number to exist, we can't depend on $\sigma(p_k)/m$ to be coprime to $m$ for very many $k$. More likely, $\sigma(p_k)/m$, if integral, will share a small factor with $m$ and further iterations of $\sigma$ will avoid certain large prime factors of $m$. This is what was observed, and what I hoped to prove and did not in the other answer.

It is an interesting side question to determine $\min_k g_k$ where $g_0=p_0$ and $g_{k+1} = \gcd(p_{k+1},g_k)$. In particular, do the iterates of $\sigma$ encounter a square or twice a square, regardless of the starting point? If so, then the minimum is odd and likely 1. Otherwise $p$ is a seed for $m$, and $p$ might be useful in looking for multiperfect numbers which are multiples of $m$.

Cohen and te Riele investigated a weaker question: Given $n$ is there a $k$ for which $\sigma^k(n) = 0 \mod n$? They did this in a 1996 paper and asserted through computation that the answer was yes for $n \leq 400$. Their data suggest to me both that the weaker question has an affirmative answer, and that there are no metaperfect numbers or even seeds for a number.

Regarding Gerry Myerson's example in a comment, I think one can construct arbitrarily long finite sequences $p_k$ which satisfy the congruence conditions, but to find such $p$ with $p=m$ will result in very large values even for $k$ as small as $3$. Toward this end, there is a 2009 paper of Katai that I have not found but think will be useful in this study.

I recommend as a starting point for a reference search

Cohen, Graeme L., and Herman JJ te Riele. "Iterating the sum-of-divisors function."

Experimental Mathematics 5.2 (1996): 91-100.

and (if you can get it)

Kátai, I. "On the prime power divisors of the iterates of \phi(n) and \sigma(n), Šiauliai

Math." Semin 4.12 (2009): 125-143.

Gerhard "Not Quite A Research Announcement" Paseman, 2015.07.21

$\endgroup$
2
  • $\begingroup$ Curiously, the MR entry for the Katai paper discusses only iterates of $\phi$, and never mentions $\sigma$. The paper appears to be freely available at siauliaims.su.lt/pdfai/2009/Katai-09.pdf $\endgroup$ Jul 21, 2015 at 23:53
  • $\begingroup$ Wow @Gerry, thanks for the link! I will peruse the paper more closely, but on first skimming, I don't see any remarks that say the paper's results apply to $\sigma$. I do find a 1991 paper on $\omega$ that looks interesting though. Gerhard "Deeper Into The Rabbit Hole" Paseman, 2015.07.21 $\endgroup$ Jul 22, 2015 at 0:18
2
$\begingroup$

EDIT 2015.07.15 I believe there is no such integer $x$. See below for the rest of the edit. END EDIT 2015.07.15

I had some initial thoughts which seemed promising. They do not lead to a proof, but (with notation below) may show that $m$ must be very large indeed for even $m_1$ and $m_2$ to be multiples of $m$. I suspect $m_3$ will never be a multiple of $m$ in such an unlikely situation.

I prefer to use $m$ for $x$: this is because $\sigma(m) = 0 \bmod m$ means $m$ is a multiply perfect number. To avoid trivialities I assume $m \gt 1$.

Note that $\sigma(m)/m$ is bounded above by the product over all primes $q$ dividing $m$ of $q/(q-1)$, which is $O(\log p)$ with $p$ the largest prime divisor of $m$, and strictly less than $p$ when $p \gt 3$. (Indeed, it is less than $\omega(m)$, the number of distinct prime divisors of $m$, when $\omega(m) \gt 4$.) While $\sigma(m)$ itself does not have to be multiperfect, I suspect there are finitely many numbers with $\sigma(\sigma(m))$ a multiple of $m$. In particular, let $g_0=m_0=m$, $m_{n+1}=\sigma(m_n)$, and $g_{n+1}=\gcd(g_n,m_{n+1})$. I suspect $g_3 \lt m$. I base this suspicion on the observation that the power of $2$ exactly dividing $m_n$ appears to change between $m_n, m_{n+1}$, and $m_{n+2}$.

Let me write $w$ for $\omega(m)$ and let us note that for a multiperfect $m$, $m_1$ will differ from $m$ by having less than $O(\log(w))$ additional prime factors, some in common with the prime factors of $m$. So the prime factorization of $m_1$ looks very much like the prime factorization of $m$.

I would like to argue that the prime factorization of $m_2$ should be quite different from that of $m_1$, because any additional powers of $q$ for $q$ a small prime dividing $n$ will affect $\sigma(q^n)$ and thus remove some prime factors. However, it is possible that there are (insanely large) odd multiperfect numbers which would be factors of $m$ and not be affected by this. Indeed, this question may be equivalent to the question of the existence of large odd multiperfect numbers.

EDIT (Part II) 2015.07.15 Let us look at $S(m)= \sigma(m)/m$. Letting the following products run over the distinct primes $q$ dividing $m$, we have $\prod (q+1)/q \leq S(m) \lt \prod q/(q-1)$. (And the lower bound is at least half the upper bound, so we have $S(m) \simeq \prod q/(q-1)$.) As observed above, $S(m) \lt \omega(m)$ when $4 < \omega(m)$ and $S(m) \lt 2\omega(m)$ the rest of the time. So $S(m)$ is pretty small compared to $m$ and often small compared to $\log p$ where $p$ is the greatest prime factor of $m$.

Let $r_n = m_{n+1}/m_n = S(m_n)$. The assumption in the problem implies $r_n \gt r_0$, for if $m$ properly divides $k$ then $S(m) \lt S(k)$. Then $m_n \gt mr_0^n$ for all $n$, since $m_n$ is an increasing sequence. I believe we can't have both conditions hold indefinitely. However, I now switch ground on my assertion above that $g_3 < m$ always happens: I think it can, I just don't think we will see an example with fewer than a 1000 decimal digits (which isn't insanely large).

Gerry Myerson's example from the comment is thought provoking: When $S(m)$ is coprime to $m$, we clearly have $m \mid m_2$ as well as $m \mid m_1$, and by multiplicativity of $S$ we also have $S(S(m)m)=S(S(m))S(m)$. What if $S(m)$ is not coprime to $m$? We still have $S(S(m)m) \lt S(m)S(S(m))$.

This last is the crux. $S()$ grows slower than $\log()$, so we need to show this contradicts the growth rate implied by all $m_n$ being multiples of $m$. It is this that inspires my confidence above, and also has me reverse my stance on this being equivalent to odd multiperfect numbers. I hope to finish this argument in a future edit. END EDIT(Part II) 2015.07.15

Gerhard "Doesn't Have A Good Closer" Paseman, 2015.07.14

$\endgroup$
27
  • 5
    $\begingroup$ The number $n=13188979363639752997731839211623940096$ satisfies $\sigma(n)=5n$ and, since $\gcd(5,n)=1$, $$\sigma^2(n)=\sigma(5n)=6\sigma(n)=30n$$ so at least there's one example where $m_1$ and $m_2$ are multiples of $m$. Whether $n$ qualifies as "very large indeed" is a matter of taste. $\endgroup$ Jul 15, 2015 at 3:04
  • $\begingroup$ That is smaller than I would have expected. Gerhard "How About One More Iterate?" Paseman, 2015.07.15 $\endgroup$ Jul 15, 2015 at 7:27
  • $\begingroup$ I am now confident the answer to the question is no; the basic reason is that the function $r(m)=\sigma(m)/m$ "can't grow fast enough" to support the existence of such a number. I will attempt an argument. Gerhard "Sleeping On It Is Good" Paseman, 2015.07.15 $\endgroup$ Jul 15, 2015 at 20:53
  • $\begingroup$ @GerryMyerson, if you seek to the asymptotics integer , i think 114 mod 6 is good example and fails only for k=9,12,18 $\endgroup$ Jul 15, 2015 at 21:54
  • 1
    $\begingroup$ It is known that sigma(n)/n can't grow too fast: en.wikipedia.org/wiki/Divisor_function#Approximate_growth_rate Robin also proved, unconditionally, that the inequality $\ \sigma(n) < e^\gamma n \log \log n + \frac{0.6483\ n}{\log \log n} $ holds for all n ≥ 3. $\endgroup$
    – joro
    Jul 20, 2015 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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