1
$\begingroup$

There is a family of recursive sequences that I came up with: $$a_n=\text{sum of factors less than $a_{n-1}$ of } a_{n-1}, a_0\in\mathbb{N}$$ First question: Has it been studied before?

Here are some observations I've made about it:

Starting from successive positive integers, and defining the sum of factors of $0$ less than $0$ as $0$, the first few sequences are: $$1,0,0\dots$$ $$2,1,0,0\dots$$ $$3,1,0,0\dots$$ $$4,2,1,0,0\dots$$ $$5,1,0,0\dots$$ $$6,6,6\dots$$ etc. Setting $a_0$ equal to a perfect number $n$ produces the sequence $n,n,n\dots$ Starting from $a_0=n_1$, where $n_1\text{ and }n_2$ are a pair of amicable numbers, produces the sequence $n_1, n_2, n_1, n_2\dots$

If $a_0$ is a prime number, $a_1=1$.

There are several conjectures I've made about this family of sequences, but haven't been able to prove or disprove:

  1. No sequence diverges to infinity.
  2. For any positive integer $>2$ defined as $a_n$, there is at least one possible $a_{n-1}$ that fits the rule of the sequence. Edit: Never mind
  3. For every $j\in\mathbb{N}$, there is at least one $a_0$ fso that $a_j=a_0$ but for all $a_k$ where $1\leq k<j$, $a_k\neq a_0$.
  4. (this might be easier than the other conjectures) No $k\in\mathbb{N}=a_n$ (greater than one) generates an infinite number of positive integers that can be set equal to $a_{n-1}$ and have these two terms follow the rule of the sequence.

Second question: Does anyone know how to prove any of these conjectures?

P.S. I do not necessarily want a proof to all four of these conjectures, although that would be good. It's just that these seem so difficult to prove that I feel like a proof of any one, two, or three of these conjecturs also has a place here.

$\endgroup$
  • 2
    $\begingroup$ The divisor function counts what you want plus the $a_{n-1}$ term. There are published bounds for it so your claim number 1 might not be hard to prove. $\endgroup$ – Sandeep Silwal Jun 9 '14 at 19:23
  • 1
    $\begingroup$ For conjecture #4, isn't it sufficient to observe that $a_{n-1}$ is either a prime (in which case $a_n=1$) or has at least one proper divisor not smaller $\sqrt{a_{n-1}}$ (so $a_n\geq \sqrt{a_{n-1}}$ or, equivalently, $a_n^2\geq a_{n-1}$) $\endgroup$ – Peter Košinár Jun 14 '14 at 22:42
  • $\begingroup$ This might be an useful reference too. $\endgroup$ – Peter Košinár Jun 15 '14 at 7:38
  • $\begingroup$ @PeterKošinár, I believe your logic is correct. Would you please write that up as an answer? $\endgroup$ – Aidan F. Pierce Jun 15 '14 at 13:31
2
+50
$\begingroup$

The sequence in question is known as aliquot sequence. Based on the references I was able to find, question #1 and #3 are open problems at the moment; we don't even know whether :

Question #4 turns out to be an easy one. If $a_{n-1}$ was a prime, we'd have $a_n=1$. Otherwise, $a_{n-1}$ must have at least one divisor greater or equal to $\sqrt{a_{n-1}}$, so $a_n\geq \sqrt{a_{n-1}}$. Thus, $a_{n-1}\leq a_n^2$ which means that any particular value $a_n>1$ can have at most $a_n^2$ immediate predecessors (the actual number of possible predecessors tends to be considerably smaller).

This upper bound can be used to check if a particular number is untouchable (which means it can only ever appear at the beginning of the sequence) and find out that $5$ is the smallest counter-example to question #2.

$\endgroup$

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.