Сумма делителей, не равных самому числу

[Ktina]

Для каждого натурального числа рассмотрим сумму всех его натуральных делителей, не равных самому числу. Например, для числа 10 эта сумма будет равна $%1+2+5=8$%, для простого числа - единице, а для числа 1 это будет пустая сумма, равная, естественно, нулю.

Легко видеть, что рассматриваемая нами сумма никогда не принимает значение 2 или 5.

(На всякий случай, доказательство)

(Если число чётное, большее 2, у него есть делители 1 и 2, отличные от самого числа, это уже даёт сумму 3, а если будет ещё хотя бы один такой делитель, то сумма будет уже как минимум 6. Если же число нечётное, большее 1, и у него хотя бы три делителя, отличных от самого числа, то сумма будет уже как минимум 9. Если же таких делителей ровно два, то их сумма будет чётной и не меньшей 4.)

Напрашивается гипотеза о том, что наша сумма может принимать любые целые неотрицательные значения, кроме 2 и 5. Ваше отношение к данной гипотезе?

[Shadow]

Ktina в сообщении #1331326 писал(а):

Ваше отношение к данной гипотезе?

Очень негативное.

[gris]

А почему бы и нет? Какое первое число недостижимо?
У меня $52$ никак не получается
Но это же не "очень" негативное, а просто слегка...
Зато $K(1870)=K(3382)=K(3526)=K(2017^2)=2018$
Кстати, если исключить простые числа, то последовательность можно минорировать возрастающей.

[wrest]

gris в сообщении #1331349 писал(а):

А почему бы и нет? Какое первое число недостижимо?

52,96,102,120,128...

Робот Тамара уже перебирает... Ждите ответа.

[gris]

Ну согласитесь, что все нечётные числа (кроме пяти) достижимы из-за гипотезы Гольдбаха, что каждое чётное число представимо в виде двух суммы простых. То есть половина чисел у нас в кармане.
Ой, а я посмотрел в OEIS. Там много теории, оказывается.
Кстати, очень полезная последовательность у ТС: если получить её более простым способом, то можно и простые числа выявлять, и совершенные.

[wrest]

Вот числа, не являющиеся Ktina-суммами и меньшие 1000:

(Оффтоп)

2, 5, 52, 88, 96, 120, 124, 146, 162, 188, 206, 210, 216, 238, 246, 248, 262, 268, 276, 288, 290, 292, 304, 306, 318, 322, 324, 326, 336, 338, 342, 348, 354, 360, 368, 372, 374, 380, 398, 402, 406, 408, 426, 430, 432, 444, 448, 458, 462, 468, 472, 474, 480, 488, 498, 500, 516, 518, 520, 530, 540, 552, 556, 558, 562, 564, 570, 576, 578, 584, 600, 608, 612, 624, 626, 628, 632, 642, 658, 660, 668, 670, 678, 692, 702, 708, 710, 714, 718, 720, 726, 728, 732, 738, 748, 750, 752, 756, 758, 762, 766, 768, 770, 782, 784, 788, 792, 802, 804, 818, 822, 828, 836, 840, 848, 852, 864, 872, 882, 892, 894, 896, 898, 902, 908, 912, 920, 926, 930, 934, 936, 938, 948, 964, 966, 968, 976, 982, 984, 992, 996, 998

Таких пропусков после анализа первых 100000 чисел, подвергнувшихся Ktina-суммированию оказалось 1208.

-- 09.08.2018, 13:10 --

Функция, которая возвращает вектор, наполненный числами, которые не попались при Ktina-суммировании чисел от 1 до n

Ktina128962(n)=my(v=[],v2=[],v3=[]);v=vector(n,i,sumdiv(i,x,x)-);v=vecsort(v,,8);v2=vector(#v,i,i);v3=setminus(v2,v);return(v3)

Запуск:

? Ktina128962(10)
%1 = [2, 5]
? Ktina128962(20)
%2 = [2, 5, 11, 12, 13]
? Ktina128962(100)
%3 = [2, 5, 12, 18, 24, 29, 30, 37, 38, 39, 45, 47, 48, 51, 52, 53, 56]

Хочу заметить, что при переходе от перебора 1-20 к перебору 1-100, суммы 11 и 13 нашлись!
А при запуске перебора до 10000, находятся и суммы между 5 и 51.

Э, нет!.. все не так-то и просто. Например Ktina-сумма 318, не найденная при переборе до 100 000, нашлась при переборе до 1 000 000.
Таким образом, перебор до $n$ выявляет пропуски до какого-то граничного числа, например до $\sqrt{n}$.

[rockclimber]

wrest в сообщении #1331358 писал(а):

Хочу заметить, что при переходе от перебора 1-20 к перебору 1-100, суммы 11 и 13 нашлись!
А при запуске перебора до 10000, находятся и суммы между 5 и 51.

Как работает ваша функция? Берет числа подряд и считает суммы делителей? Имхо, не самый лучший путь, потому что есть проблема вида "нужное число уже нашлось или еще нет?"
Я бы искал иначе: для каждого натурального числа надо найти, суммой делителей какого числа оно может являться? Любое натуральное число есть произведение нескольких простых. Сумма делителей числа - это сумма единицы, всех простых делителей и всех их возможных комбинаций. При тестировании числа на "ктинообразность" надо взять все простые, меньшие корня из числа, и попробовать все их комбинации. Возможно, на маленьких числах это будет требовать намного больше вычислений, но на больших должно дать преимущество.

[wrest]

rockclimber в сообщении #1331368 писал(а):

Как работает ваша функция? Берет числа подряд и считает суммы делителей?

Ну да, по-колхозному.

rockclimber в сообщении #1331368 писал(а):

При тестировании числа на "ктинообразность" надо взять все простые, меньшие корня из числа, и попробовать все их комбинации.

Ну давайте попробуем. Берем 52. Корень из него - чуть больше 7, т.е. 7 входит. Итого "единица и все простые меньшие корня": 1,2,3,5,7
Что дальше?

[rockclimber]

wrest в сообщении #1331370 писал(а):

Итого "единица и все простые меньшие корня": 1,2,3,5,7
Что дальше?

$1 + 2^1$ - сумма всех множителей числа $4$
$1 + 2^1 + 2^2$ - сумма всех множителей числа $8$
...
И так пока сумма не будет больше $52$

$1 + 3^1$ - сумма всех множителей числа $9$
$1 + 3^1 + 3^2$ - сумма всех множителей числа $27$
...
И так пока сумма не будет больше $52$

$1 + 5^1$ - сумма всех множителей числа $25$
$1 + 5^1 + 5^2$ - сумма всех множителей числа $125$
...
И так пока сумма не будет больше $52$

$1 + 7^1$ - сумма всех множителей числа $49$
$1 + 7^1 + 7^2$ - сумма всех множителей числа $343$
...
И так пока сумма не будет больше $52$ (уже больше в данном случае)

$1 + 2^1 + 3^1 $- сумма всех множителей числа $6$
$1 + 2^1 + 2^2 + 3^1 + 2^1 \cdot 3^1$ - сумма всех множителей числа $12$
$1 + 2^1 + 2^2+ 2^3 + 3^1 + 2^1 \cdot 3^1 + 2^2 \cdot 3^1$ - сумма всех множителей числа $24$
...
И так пока сумма не будет больше $52$

И так далее, и так далее. В какой-то момент сумма совпадет с заданным числом. А если перебрали все варианты, но сумма не совпала - это Ktina-число.

[Sender]

Можно свернуть эти суммы:

$$\frac{p_1^{\alpha_1+1}-1}{p_1-1}\cdot \frac{p_2^{\alpha_2+1}-1}{p_2-1}\cdot \dots \cdot \frac{p_n^{\alpha_n+1}-1}{p_n-1}-p_1^{\alpha_1} \cdot p_2^{\alpha_2}\cdot p_n^{\alpha_n}.$$

[wrest]

rockclimber
Да, много пребирать вариантов.

Ну вот, собсна, "Untouchable numbers": https://oeis.org/A005114

[rockclimber]

wrest в сообщении #1331396 писал(а):

rockclimber
Да, много пребирать вариантов.

Вы хотели сказать "много кода писать руками"? Чтобы найти Ktina-числа от 1 до 51, вы перебрали все натуральные числа от 1 до 10000 и для каждого нашли все их множители, но их множители вы искали по тому же самому алгоритму перебора, просто вшитому в стандартную функцию вашего языка. А по моему алгоритму вам надо перебрать все множители 51 натурального числа (а не 10 000), просто числа эти не по порядку идут.

-- 09.08.2018, 15:53 --

rockclimber в сообщении #1331399 писал(а):

вам надо перебрать все множители 51 натурального числа

Отставить, это я не подумавши сказал. Сильно больше, но сколько точно, навскидку не скажу. Но, имхо, все равно меньше 10000.

[Dmitriy40]

Насколько я понимаю, величина sumdiv(x)-x не может быть меньше $\sqrt{x}$ за исключением простых чисел. Так что для доказательства недостижимости 52 достаточно перебрать числа лишь до $52^2=2704$.

[rockclimber]

Что-то мой алгоритм перестает мне нравиться.
Его явно можно существенно усилить, но нет времени над этим думать. Основных направлений два:
1) для любого проверяемого числа можно установить предельную степень для каждого из простых в зависимости от того, какие еще простые входят в набор - тогда не придется перебирать слишком много вариантов.
2) создать алгоритм типа "решето". В процессе проверки диапазона чисел у нас будет сгенерировано сколько-то других чисел, отличных от проверяемых. Все эти сгенерированные числа можно запомнить и исключить из дальнейших проверок. И, что самое главное, наборы комбинаций простых чисел тоже. Но тут алгоритм начинает резко потреблять память.

[wrest]

Dmitriy40 в сообщении #1331400 писал(а):

Насколько я понимаю, величина sumdiv(x)-x не может быть меньше $\sqrt{x}$ за исключением простых чисел.

Да, у квадратов простых чисел минимальные суммы делителей, ессно.
Ну да, вот что написали в OEIS

isA078923(n)=if(n==0 || n==1, return(1)); for(m=1, (n-1)^2, if( sigma(m)-m == n, return(1))); 0

Перебирают даже не до $x^2$ а до $(x-1)^2$ -- совершенно правильно потому что единица-то всегда входит в сумму, так что надо её вычесть.
Но вот только они перебирают от единицы, а это ж как-то неправильно.
Мы недавно обсуждали суперизбыточные числа, ну вот сумма делитлей большая чем упятренное число, емнип не встречается в обозримой перпективе. А у нас туда еще не входит само число, значит берем учетверенное (это тоже с запасом, кажись). Так что перебирать надо не от единицы, а от четверти числа, и для 52 соответственно от 14-ти.

-- 09.08.2018, 15:37 --

rockclimber в сообщении #1331405 писал(а):

создать алгоритм типа "решето". В процессе проверки диапазона чисел у нас будет сгенерировано сколько-то других чисел, отличных от проверяемых.

Верной дорогой идёте, товарищ! Я вот пошел туда же прям сразу ;)
Решето тут лучше всего, просто надо помнить, что если просеял первые $10^6$ натурльных чисел, то надежно отсеялись только неприкасаемые числа до $10^3$