3
$\begingroup$

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)$.

  1. What is the least $n \in \mathbb{N}$ such that $\displaystyle \lim_{k \rightarrow \infty} D(n)_k = +\infty$?
  2. 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:

  1. $n$ is prime and so $\delta(n) = 0 < n$;
  2. $n=2p$ for some prime $p$, and then $\delta(2p) = 2(2-1)(p-1) = 2(p-1) < 2p$;
  3. $n=p^2$ for some prime $p$, and then $\delta(p^2) = (p-1)^2 < p^2$;
  4. $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.


The set of delta(15) as a union of two lattices corresponding to the divisors 3 and 5. For distinct primes p,q, we have delta(pq) = 2(p-1)(q-1).

The set of delta(45) with the lattice corresponding to the divisor 15 highlighted in orange.


$\endgroup$
2
  • $\begingroup$ Have you checked whether $\delta(n)$ is in the Online Encyclopedia of Integer Sequences? $\endgroup$ Apr 20, 2020 at 2:00
  • $\begingroup$ @GerryMyerson Indeed I have, but unfortunately I did so at an earlier stage. In the original context from which I distilled this question, I worked with $n^2 - \delta(n)$. Since I could not find that in the OEIS, I assumed that $\delta(n)$ would not be there either. But now I see that $\delta(n)$ is OEIS A268631 (edit: added ref to question). Thanks! $\endgroup$
    – Z. A. K.
    Apr 20, 2020 at 2:48

0

Your Answer

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

Browse other questions tagged or ask your own question.