35 членов последовательности, любопытное наблюдение

[Ktina]

Рассмотрим последовательность 0, 0, 0, 1, 0, 2, 0, 2, 1, 2, 0, 6, 0, 2, 2, 3, 0, 6, 0, 6, 2, 2, 0, 10, 1, 2, 2, 6, 0, 12, 0, 4, 2, 2, 2, 12, ...
(формула энного члена - количество простых делителей, умноженное на количество составных делителей).

А вам не показалось удивительным, что первые 35 её членов совпадают с первыми 35 членами вот этой последовательности, а 36-ой член не совпадает?

[maxal]

Ktina
Обозначим через $\omega(n)$ количество различных простых делителей (т.е. без учёта кратности), а через $\tau(n)$ количество всех натуральных делителей числа $n$.
Тогда $n$-й члена вашей последовательности дается выражением $a(n)=\omega(n)\cdot (\tau(n)-1-\omega(n))$.

С другой стороны, $n$-ый член A070288 можно задать выражением

$$b(n)=\sum_{p\mid n} \sum_{q\mid \frac{n}{p}} \tau\left(\frac{n}{pq}\right),$$

где суммы берутся по простым $p,q$.

Пусть $n$ имеет вид $n=p^km$ ($k\geq 1$), где $m$ - cвободно от квадратов и не делится на простое $p$. Обозначим $s=\omega(m)\geq 0$. Прямым вычислением получаем:

$$a(n)=(s+1)\cdot ((k+1)2^s-s-2)$$

и

$$b(n)=(ks+k-1)2^s+s(s-1)(k+1)2^{s-2}.$$

Эти выражения совпадают при $s=0,1$ и любом $k$. А также при $s=2$ и $k=1$.

Итак, если $a(n)\ne b(n)$, то $n$ либо делится на произведение 4-х простых чисел, как минимум три из которых различны, либо на квадрат составного числа. Минимальное такое число - это как раз $36=(2\cdot 3)^2$.

Вывод: удивительно, но лишь чуть-чуть. Закон малых чисел в действии.

[Ktina]

maxal
Большое спасибо!