Про числа, дружбу и оптимизацию


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

Присказка. Вчера под вечер в уже рекламированной здесь приблуде от sololearn попалось задание… ну как задание… «вызов» (хоть я и предпочитаю вопреки нормам переводить challenge как «испытание»). Обычно на такое я плюю, особенно если это не в игрушке. А тут что-то перемкнуло в черепушке, видать от соуса «надо-ж-учиццо» и решил поучаствовать… ну как поучаствовать, всмысле у себя сделать, а уж выпендриваться там — еще подумаю.

Задачка подкупает одновременной примитивностью и глубиной. А суть её — поиск друзей ) Не простых (хоть эта задачка интереснее), а числовых, точнее для чисел. Суть примерно такая: существуют пары чисел с таким свойством, что сумма делителей этих чисел, за вычитом их самих, равна второму числу пары. Ну и есть самовлюбленные числа, которые таким образом парны самим себе. Задача написать программу, которая находит такие пары (для натуральных чисел).

Поясню идею. Есть число 28. У него есть делители 28, 14, 7, 4, 2, 1. Первый (равный самому числу) отбрасываем, а остальные складываем. 1+2+4+7+14=28. Т.е. число — «самодруг».

220 таким образом превращается в 110+55+44+22+20+11+10+5+4+2+1= 284
284 дружит с 220, т.к. 1+2+4+71+142 = 220

Алгоритм поиска в первом приближении простейший — нужно составить массив из пар «число»-«сумма делителей» и по ней проверить парность в заданном интервале. Основной проблемой становится подсчет суммы делителей. Самое простое идет под лозунгами «тыжпрограммист» (ну или хотя бы «быдлокодер») — лупи перебором!

С перебором все просто. Берем число и до отупения его делим, на 1, 2, 3, 4… и так до самого числа. Смотрим остаток от деления, если без остатка — значит нашелся очередной делитель. С таким ломовым подходом, компьютер «сдох» на сумме\числах до 15000. Человек опупеет еще раньше, а к этому я плавно подвожу. Значит надо оптимизировать.

Самоочевидное — не делить на само число (оно в сумме не участвует), не делить на 1 (ибо результат известен). А дальше? Ну по мелочи выигрывается чисто программерски, перестроением проверок и условий (на деле — кот наплакал. Суровый, отожратый манул)

Почесав репу, и посмотрев на циферки, понимаю, что можно сократить в двое. Ведь за исключением простых чисел, которые в данной задачи вообще не интересны, т.к. сумма у них единица, которая ни с кем не дружит по определению, делители парно симметричные. На примере все тех же 220:
110 и 2
55 и 4
44 и 5
22 и 10
20 и 11

Значит, можно перебирать\делать не 220 (218) делений и сравнений остатка, а половину ~109.

Выписав на бумажку все числа и подчеркнув делители, становится заметно, что половина числа и половина делителей не одно и то же. Они смещены, кукуясь ближе к началу. Да и без выписывания видно вон выше — половина грубо 109, справа только 110 и отбрасываемые 220. С этой мысли начинается охота на границу. Пока в голову не ударяет следующая гениальная мысль (ох, как я был доволен, вечерком в метро прочитав в вики, что я допер до способа, как делают умные дядьки) — если смотрим симметрию, то делители повторяются. Вначале мы идем от меньшего к большему, в это время их зеркальное отражение идет в обратную сторону. 2-4-11-22 и 110-55-20-10. Где-то они пересекаться должны. И точка равенства  есть ни что иное как степень. По русски. Делители 16: 16,8,4,4,2,1. Середина и ограничитель для перебора это округленный до целого числа квадратный корень. Для 220 это будет 14, ну или 15, если угодно чуть-чуть подстраховаться.

Таким образом, чтобы найти все делители для 220 нужно попробовать всего 13 чисел (14 минус нетестируемая единица). Это в 17 раз быстрее изначального! И чем больше число, тем больше «экономия». Для числа «миллионника», это в тысячи раз меньше вычислений.

Но фанатикам этого мало. Остаются еще огромные поля безрезультатных проверок. Начинаешь думать дальше. И вдруг замечаешь, что у изначально нечетных чисел все делители нечетные. (если кто готов опровергнуть — жду примера\доказательства). Что является следствием самовыведенной теории, что все делители делителей имеются среди делителей

На примерах (про делители делителей).
16 — 16,8,4,2,1;
8 — 8,4,2,1
4 — 4,2,1

Про нечетность: 1, 3, 9, 27, 823, 2469, 7407, 22221 у 22221
Просто если число четное, оно по определению делится на 2 и вероятно, имеет другие делители, делящиеся на 2 (см 16). Соответственно, если есть хоть один четный делитель, то обязательно будет и двойка, которой проверяется четность.

Вывод с точки зрения оптимизации простой — если число нечетное, то шаг перебора можно делать равным двум. т.е. 1,3,5,7,9… вместо 1,2,3,4,5,6. Четных чисел половина и от них в половину меньше перебирать, т.е. ожидаемый прирост производительности (тут не совсем корректно выразился) еще где-то на четвертушку. Т.е. грубо с 40 секунд на все вычисления, затрачиваемое время упадет до 30. На практике правда, по недовкуренным причинам, эффект оказался скромнее: упало до 35с.

Такой же трюк с тройкой провернуть сложнее с точки зрения программы. Шаг получается неравномерный. 1,2,4,5,7,8… а если еще с двойкой смешивать так вообще. Однако, думается мне, что тройку, пятерку, а то и вообще простые числа, можно как-то обыграть еще.

К чему я это все пишу? Ну кроме выпендрежа и истории о том, что увлекло меня в этот момент времени… Вдруг кого заинтересует задачка и кто-нибудь предложат еще интересные идеи, как сократить число перебираемых чисел.

Вот у меня вертятся вопросы: как определить, кроме перебора, что все делители найдены? Можно ли их посчитать не перебирая? «Предсказать» место следующего делителя или достоверно отмести область чисел, которые точно не будут делителями, не проверяя их. Ведь с увеличением размера числа, растет и количество перебираемых чисел, при том, что количество делителей растет значительно медленнее. Для 1.000.000 перебираемых комбинаций 999, а делителей всего 49 из которых два известны сразу, т.е. 47 искомых. Но как узнать, без гугла и перебора, что их действительно 49? И если так подумать, то при переборе 95% проверок провалятся, как бы их сократить?

P.S. статью про определение делителей из школьной программы еще не дочитал. Но сдается мне, что они доводят до простых чисел… Это прокатывает на небольших значениях, скажем до 10000 (делители, а следовательно и простые числа в пределах 100 — по памяти выбиваются исключением значений из таблицы умножения). А на больших, с таким подходом возникает необходимость определять простое ли это число само по себе, а это опять перебор с вышеозначенными методиками.

P.S.2 Ну а про извращения и попытки параллельных вычислений я пока промолчу, т.к. вначале хочу из алгоритма выжать максимум. Пасибки и респекты маньякам дочитавшим этот цифробред. Мяу!

Обсудить у себя 7
Комментарии (3)

Да… это не для меня. Ничего не умею считать: кроме денег, конечно.)

С серьезной математикой я тоже не дружу (сожалею, но исправить это желания пока не возникло). А тут вполне себе головоломка, хоть и на любителя с программерским уклоном. Но тема следующего поста пока вакантна )

Вот кто чем голову забивает. ))

Чтобы комментировать надо зарегистрироваться или если вы уже регистрировались войти в свой аккаунт.

Войти через социальные сети: