Простые через индексы двоек

[kthxbye]

Буду краток. Имеем последовательность, которая даже есть в OEIS (A345176):

$$a(n)=\sum\limits_{k=1}^{n}\left\lfloor\frac{n}{k}\right\rfloor^k$$

Начинается она так:

$$1, 3, 5, 10, 12, 26, 28, 52, 73, 115, 117, 295, 297, 439, 713, 1160, 1162, 2448, 2450, 4644, 6832$$

Просто ради интереса возьмем первые разности:

$$2, 2, 5, 2, 14, 2, 24, 21, 42, 2, 178, 2, 142, 274, 447, 2, 1286, 2, 2194, 2188 $$

Присвоим первой двойке индекс $2$ и выпишем индексы всех остальных двоек. И что же мы видим, господа? Простые числа.

Есть ли объяснение сему занимательному факту?

[mihaild]

$$a(n + 1) - a(n) = 2 + \sum_{k=2}^n \left(\left\lfloor \frac{n + 1}{k}\right\rfloor^k - \left\lfloor \frac{n}{k}\right\rfloor^k\right)$$

В каком случае вторая сумма равна нулю?

[kthxbye]

mihaild в сообщении #1546506 писал(а):

$$a(n + 1) - a(n) = 2 + \sum_{k=2}^n \left(\left\lfloor \frac{n + 1}{k}\right\rfloor^k - \left\lfloor \frac{n}{k}\right\rfloor^k\right)$$

В каком случае вторая сумма равна нулю?

Благодарю за подсказку! А можно еще вопрос? Пусть

$$a(n)=\sum\limits_{k=1}^{n}\left\lfloor\frac{n}{k}\right\rfloor^{2m+1}$$

$$b(n)=a(n)-a(n-1), b(1)=1$$

Тогда получается, что $b(n)$ нечетное тогда и только тогда, когда $n=q^2$. Кроме того, $b(q^2)$ гарантированно составное. Почему?

С минимальными простыми множителями $b(q^2)$ здесь все отнюдь не очевидно. Минимальный пример, это когда $2m+1=6m'+5$ и $q=8$:

$$163, 2067771649, 8915215553, 421, 657593991585619337, 670139, 18769433, 467, 1297, 8329, 857, 3607$$

[mihaild]

kthxbye в сообщении #1546520 писал(а):

Благодарю за подсказку

А решить получилось? Для следующих вопросов нужно то же наблюдение.

[kthxbye]

mihaild в сообщении #1546534 писал(а):

kthxbye в сообщении #1546520 писал(а):

Благодарю за подсказку

А решить получилось? Для следующих вопросов нужно то же наблюдение.

Очевидно, что если $k|(n+1)$, то $\left\lfloor\frac{n+1}{k}\right\rfloor=\left\lfloor\frac{n}{k}\right\rfloor+1$.

Вторую последовательность можно упростить до

$$b(n)=\sum\limits_{d|n}^{}\left(\frac{n}{d}\right)^{2m+1}-\left(\frac{n}{d}-1\right)^{2m+1}$$

Все слагаемые нечетные, следовательно сумма будет нечетной тогда и только тогда, когда делителей нечетное количество. А нечетное количество делителей у нас тогда и только тогда, когда $n=q^2$.

А вот относительно того почему $b(q^2)$ исключительно составное никаких идей нет.

[mihaild]

kthxbye в сообщении #1546571 писал(а):

А вот относительно того почему $b(q^2)$ исключительно составное никаких идей нет

Потому что это неправда. Например при $m = 2$, $b(864^2) = 1676881683685495830377957$ - простое.

[kthxbye]

mihaild в сообщении #1546576 писал(а):

kthxbye в сообщении #1546571 писал(а):

А вот относительно того почему $b(q^2)$ исключительно составное никаких идей нет

Потому что это неправда. Например при $m = 2$, $b(864^2) = 1676881683685495830377957$ - простое.

Да, вы совершенно правы, благодарю. Даже стало интересно с какой частотой появляются контрпримеры.