Question
For $n \in \mathbb{N}$ let $\delta(n)$ denote the cardinality of the set $$\left\{(a,b) \in \mathbb{N}^2 \::\: 1 < a < n,\ 1 < b < n,\ n|ab\!\: \right\}.$$ Let $D(n)$ denote the sequence obtained by iterating the map $x \mapsto \delta(x)$ on $n$, so that e.g. $D(6) = [6,4,1,0,0,0,\dots]$ and $D(12) = [12,17,0,0,0,\dots]$. The following questions concern the asymptotic behavior of the sequences $D(n)$.
- What is the least $n \in \mathbb{N}$ such that $\displaystyle \lim_{k \rightarrow \infty} D(n)_k = +\infty$?
- Can we find $n > 0$ such that $D(n)$ is periodic?
Notice that the density of pairs $(a,b) \in \mathbb{N}^2$ such that $n$ divides $ab$ but $n$ fails to divide $a$ and $b$ measures how far away $n$ is from being prime. This density is just $\frac{\delta(n)}{n^2}$. The sequence $\delta$ is A268631.
Observations
The maps $(a,b) \mapsto (a,n-b)$ and $(a,b) \mapsto (b,a)$ preserve membership in the set involved in the definition of $\delta(n)$, and fix only $(\frac{n}{2},\frac{n}{2})$. Thus, the quantity $\delta(n)$ is congruent to $1$ modulo $4$ precisely if $4$ divides $n$. Otherwise, $\delta(n)$ is congruent to $0$ modulo $4$. This provides a partial answer to Question 2: $D(n)$ cannot have odd period for $n > 0$, and in particular $n=0$ is the only solution to $\delta(n) = n$.
By writing the set $\left\{(a,b) \in \mathbb{N}^2 \::\: 1 < a < n,\ 1 < b < n,\ n|ab \right\}$ as a union of periodic lattices corresponding to the divisors of $n$ (as in the figures below) I was able to determine, using elementary arguments, that $\delta(n) < n$ holds only in the following cases:
- $n$ is prime and so $\delta(n) = 0 < n$;
- $n=2p$ for some prime $p$, and then $\delta(2p) = 2(2-1)(p-1) = 2(p-1) < 2p$;
- $n=p^2$ for some prime $p$, and then $\delta(p^2) = (p-1)^2 < p^2$;
- $n=8$.
I feel that a negative answer to Question 2 should follow straightforwardly from here (but I'm not quite sure how to get it). It also suggests to me (perhaps naively) that $D(n)$ should diverge for many integers: since $2p$ is always congruent to $2$ modulo $4$, numbers of the form $2p$ cannot occur in any $D(n)$ with $n \neq 2p$, which leaves only the prime and prime square cases. But as the primes thin out, it seems likely that a sequence will never hit any of these. Does e.g. $D(45)$ grow without bound? It reaches 407425 in eight iterations.