Докажите, что четвёрка не встретится в последовательности

[Ktina]

Докажите, что в последовательности 0 2 3 2 5 1 7 10 6 3 11 17 13 5 7 26 17 28 19 27 ... никогда не встретится число 4.

Эта последовательность является последовательностью модулей разности между суммой простых делителей и суммой составных делителей натуральных чисел (пустая сумма считается за 0).

[waxtep]

Можно так (наверное, есть способ проще): пусть для натурального $n$, $P_n$ - сумма его простых делителей, а $C_n$ - составных, и $D_n=|C_n-P_n|$.
а) простым искомое число быть не может;
б) заметим, что если $n$ - составное, то $C_n\ge4, C_n>P_n$;
в) рассмотрим число $m=p\cdot n$, где $p$ - простое, для трех исчерпывающих все возможности случаев:
i. $p\not{\mid} n: P_m=P_n+p,C_m=(p+1)C_n+pP_n,D_m=|(C_n-P_n)+p(C_n+P_n-1)|$. Если $n$ - составное, обе скобки под модулем положительны и их сумма не меньше $11$, это нам не годится. Если же $n$ - простое (не равное $p$), то $|np-n-p|=4$ не проходит по соображениям четности.
ii. $n$ - составное и $p\mid n: P_m=P_n, C_m=C_n+p^x(1+y)>C_n+4$, поскольку $p,x\ge2,y\ge0$ (и хотя бы одно из неравенств для $x,y$ - строгое), и $C_m-P_m>4$, не годится.
iii. $p=n, |p^2-p|=4$ - не бывает.

[waxtep]

...вообще, конечно, значения $D_n$ так позорно малы до десятки, а дальше-то они огого!

[Ktina]

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

[wrest]

Назовем последовательность описанную в первом посте этой темы как Ktina128856 (по номеру темы на форуме).
Последовательность чисел, меньших 100, которые не встретятся в последовательности Ktina128856 до миллионного члена включительно, назовем Ktina128856-bis, она дана ниже:
Ktina128856-bis=[4, 8, 12, 14, 16, 18, 22, 24, 25, 30, 32, 34, 36, 38, 40, 44, 46, 48, 50, 52, 54, 56, 60, 62, 64, 66, 68, 70, 72, 74, 76, 82, 84, 85, 86, 88, 90, 92, 93, 94, 96, 98]
По характеру последовательности Ktina128856 видно что эти числа не встретятся в последовательности Ktina128856 никогда, т.к. последовательность Ktina128856 хоть немного и колеблется, но все время возрастает.

[wrest]

waxtep
А можно ли ваше доказательство как-то применить для доказательства того, что не встретится не только 4, но также и 8,12,16 ?

[waxtep]

Без дополнительных идей вряд ли, я все таки существенно опираюсь на то, что четверка - маленькая. Может быть, удачной идеей будет расписать, что будет с $D_n$, если показатель одного из простых множителей $n$ увеличить на единичку, и таким образом получить все числа, которые в последовательности встретятся. Надо покумекать.

[wrest]

Для истории, если понадобится вычислять эту последовательность...

Ktina128856(n)=my(dv=divisors(n),s1=0,s2=0);for(i=2,#dv,if(ispseudoprime(dv[i]),s1+=dv[i],s2+=dv[i]));abs(s1-s2)

[waxtep]

Честно говоря, похоже, ничего красивого тут не получится. Можно же в лоб взять формулу для суммы $S_n$ всех делителей числа $n=\prod\limits_{i}p_i^{a_i}, S_n=\prod\limits_{i}\frac{p_i^{a_i+1}-1}{p_i-1}$ и получить курьезное выражение для разности сумм его составных и простых делителей, $D_n=\prod\limits_{i}\frac{p_i^{a_i+1}-1}{p_i-1}-2\sum\limits_{i}p_i-1$. Представимо ли, скажем, число $76$ в таком виде при каких-то $p_i,a_i$? Да Диэдр его знает!..

[wrest]

waxtep в сообщении #1330486 писал(а):

Представимо ли, скажем, число $76$ в таком виде при каких-то $p_i,a_i$? Да Диэдр его знает!..

Тут дело такое. Если вы смотрели на график то видели, что число 76 может быть только в определеннном месте последовательности. Сначала последовательность меньше, потом какое-то время колеблется, а потом строго больше. Соответственно, определив внешние границы допустимости нахождения 76, и перебрав последовательность внутри этих границ, можно и доказать встретится или нет.
Например попробовать доказать, что для $n>20$: $1/4<\dfrac{D_n}{n}<4$

[wrest]

По крайней мере для $n$ от 100 до 10 миллионов, $\dfrac{1}{2}<\dfrac{D_n}{n}$ т.е. $D_n>0,5n$
Похоже что $0,5n$ это к чему стремятся локальные минимумы $D_n$.

[waxtep]

да, для $n=2p, D_n=p-2$, и меньших значений $\dfrac{D_n}n$ не будет

[wrest]

Короче, всё просто: минимумы у чисел вида $n=2\cdot p$ где $p$ простое

[wrest]

Максимумы $D_n/n$ тоже идут по какой-то схеме, но пока непойму по какой. Вот эти $n$:

(Оффтоп)

$3=3^1$
$4=2^2$
$5=5^1$
$7=7^1$
$8=2^3$
$12=2^2\cdot 3^1$
$16=2^4$
$24=2^3\cdot 3^1$
$36=2^2\cdot 3^2$
$48=2^4\cdot 3^1$
$60=2^2\cdot 3^1\cdot 5^1$
$72=2^3\cdot 3^2$
$120=2^3\cdot 3^1\cdot 5^1$
$180=2^2\cdot 3^2\cdot 5^1$
$240=2^4\cdot 3^1\cdot 5^1$
$360=2^3\cdot 3^2\cdot 5^1$
$720=2^4\cdot 3^2\cdot 5^1$
$840=2^3\cdot 3^1\cdot 5^1\cdot 7^1$
$1260=2^2\cdot 3^2\cdot 5^1\cdot 7^1$
$1680=2^4\cdot 3^1\cdot 5^1\cdot 7^1$
$2520=2^3\cdot 3^2\cdot 5^1\cdot 7^1$
$5040=2^4\cdot 3^2\cdot 5^1\cdot 7^1$
$10080=2^5\cdot 3^2\cdot 5^1\cdot 7^1$
$15120=2^4\cdot 3^3\cdot 5^1\cdot 7^1$
$25200=2^4\cdot 3^2\cdot 5^2\cdot 7^1$
$27720=2^3\cdot 3^2\cdot 5^1\cdot 7^1\cdot 11^1$
$55440=2^4\cdot 3^2\cdot 5^1\cdot 7^1\cdot 11^1$
$110880=2^5\cdot 3^2\cdot 5^1\cdot 7^1\cdot 11^1$
$166320=2^4\cdot 3^3\cdot 5^1\cdot 7^1\cdot 11^1$
$277200=2^4\cdot 3^2\cdot 5^2\cdot 7^1\cdot 11^1$
$332640=2^5\cdot 3^3\cdot 5^1\cdot 7^1\cdot 11^1$
$554400=2^5\cdot 3^2\cdot 5^2\cdot 7^1\cdot 11^1$
$665280=2^6\cdot 3^3\cdot 5^1\cdot 7^1\cdot 11^1$
$720720=2^4\cdot 3^2\cdot 5^1\cdot 7^1\cdot 11^1\cdot 13^1$
$1441440=2^5\cdot 3^2\cdot 5^1\cdot 7^1\cdot 11^1\cdot 13^1$
$2162160=2^4\cdot 3^3\cdot 5^1\cdot 7^1\cdot 11^1\cdot 13^1$
$3603600=2^4\cdot 3^2\cdot 5^2\cdot 7^1\cdot 11^1\cdot 13^1$
$4324320=2^5\cdot 3^3\cdot 5^1\cdot 7^1\cdot 11^1\cdot 13^1$
$7207200=2^5\cdot 3^2\cdot 5^2\cdot 7^1\cdot 11^1\cdot 13^1$
$8648640=2^6\cdot 3^3\cdot 5^1\cdot 7^1\cdot 11^1\cdot 13^1$
$10810800=2^4\cdot 3^3\cdot 5^2\cdot 7^1\cdot 11^1\cdot 13^1$
$21621600=2^5\cdot 3^3\cdot 5^2\cdot 7^1\cdot 11^1\cdot 13^1$
$36756720=2^4\cdot 3^3\cdot 5^1\cdot 7^1\cdot 11^1\cdot 13^1\cdot 17^1$
$61261200=2^4\cdot 3^2\cdot 5^2\cdot 7^1\cdot 11^1\cdot 13^1\cdot 17^1$
$73513440=2^5\cdot 3^3\cdot 5^1\cdot 7^1\cdot 11^1\cdot 13^1\cdot 17^1$

[waxtep]

Это, похоже, ближе к большой науке, и имеет смысл смотреть в сторону избыточных чисел. Для достаточно больших чисел можно пренебречь разницей между суммой всех делителей и $D_n$, и просто смотреть на поведение индекса избыточности, A134716

-- 04.08.2018, 19:01 --

Или даже лучше сюда A004394