Совершенные, дружественные и общительные числа

О совершенных и дружественных числах можно почитать например в советском математическом словаре или энциклопедии. Об общительных числах я нашел только в одной книге. На всякий случай напомню еще раз:



Совершенным называется число, равное сумме всех своих делителей кроме самого себя. Например 28 = 1 + 2 + 4 + 7 + 14. Совершенные числа имеют много интересных свойств. Если интересно, могу рассказать.



Если просуммировав делители мы получим другое число и просуммировав делители нового числа получим исходное,то такие пары чисел называются дружественными. Например 220 и 284.



Если же такая цепочка состоит из более чем двух чисел, то такие числа называются общительными.



В книге "Математические новеллы" 1974 г. сказано, что известно всего две цепочки общительных чисел. Причем они были получены без помощи ЭВМ.

Первая, 5 звеньев: 12496, 14288, 15472, 14536, 14264

Вторая, 28 (!) звеньев: Начинается с 14316.

В частности, общительные числа, состоящие из трех чисел, называются "толпы". Как сказано в книге, существуют ли толпы, неизвестно.



Написал тут прогу для поиска дружественных и общительных чисел. Ничего нового пока не нашел. Прога работает довольно медленно - поиск общительных чисел среди чисел меньших N имеет квадратичную от N сложность.



Интересно, для каждого ли размера цепочки существуют общительные числа и конечны ли такие множества.



Есть ли какие-нибудь мысли, как можно получить набор делителей с более быстрой сложностью чем O(N)? Или, если это возможно, сразу же получить сумму всех делителей числа?

 

Есть ли какие-нибудь мысли, как можно получить набор делителей с более быстрой сложностью чем O(N)?



Имеешь в виду факторизацию? А почему такое дикое описание сложности тогда?

 

volodya

Володя, не путай, факторизация это другое. Это разложение на простые множетили. А делитель это то, на что можно разделить число без остатка. Делитель может быть составным.



Например:



Факторизуем 100. 100 = 2^2 * 5^2

Делители 100: 1, 2, 5, 10, 20, 25, 50



Самый дубовый метод факторизации имеет O(sqrt(N)). А поиск всех делителей будет дольше. Вот как?

 

Блин, вот я тупой урод! )) Поиск всех делителей сводится к O(sqrt(N)) вобще элементарно

Код (Text):

1.  
2. for i=1 to sqrt(N)
3.   if(N делится на i)
4.   {
5.     Добавить_делитель(i);
6.     Добавить_делитель(N/i);
7.   }
8.  

 

На эту тему ещё одна задачка:



"Почти совершенным" или "слегка недостаточным" называется число, равное сумме всех своих делителей(кроме самого себя) плюс один(т.е. сумма(делители а кроме самого а)=а-1. Например 8: 1+2+4=7=8-1=2³-1). Пару лет назад несколько человек с нашего курса пытались доказать утверждение



а слегка недостаточно <=> a=2ⁿ



Обратное направление тривиально, а с прямым мы тогда где-то на середине завязли. Если можно было бы как-нибудь оценить сумму делителей не вычисляя её, это наверное сильно бы помогло.



P.S. Кому интересно: часть дискуссии(на немецком) находится по адресу

http://www.schuelerakademie.de/netz/mailinglist/2000/msg00613.html

если потребует логин: dsa пароль: SchuelerAkademie

 

for i=1 to sqrt(N)



Хм... В твоем же собственном примере 20,25,50 явно больше sqrt(100). Мудришь ты, Опраксий...

 

Почему? Делитель 50 получается строкой

Добавить_делитель(N/i);

при i=2



А вот 25 действительно мы пропускаем...



Гм... не пропускаем просто в начальной версии последовательности пропущено 4 в списке делителей

 

_DEN_

Можно факторизировать, а потом взять все комбинации факторов, может быть будет быстрее?

Не хватает ещё 4

 

Stiver

Ну ошибся, ошибся!!! Все, укоротили мне половой орган



volodya

Читай внимательнее



В том алгоритме надо еще добавить проверку if(sqrt(N) целое), чтобы дважды не добавлять делитель sqrt(N).



Stiver

Нет, это будет гораздо дольше. Это называется "Множество всех подмножеств". Его построение это как минимум O(2^n), тем более придется удалять дубликаты. Например 8 = 2*2*2. Построй множество всех подмножеств.

 

Хм... Странно... Моя прога правильно находит дружественные числа, правильно находит известную цепочку из пяти чисел, но не находит цепочку из 28-ми чисел... Странно, прога вроде простая. Похоже, что в книге наврали.



Кстати говоря, нашел 4 цепочки из 4-х чисел, о которых в этой книге не сказано

 

Stiver

Уточни задачу. То, что ты написал - неправильно.



Делителями 2^n является 2^k, где 0 <= k <= n. Нас интересуют делители вида 2^i, где 1 <= i <= n-1.



А сумма 2^i {i=1;i<n;i++} равна 2^n - 2, а никак не 2^n.



Например:



16 = 2^4

Делители 16: 1, 2, 4, 8, 16.

Нас интересуют: 2, 4, 8.

2 + 4 + 8 = 14 = 16 - 2 = 2^4 -2

 

Дико извиняюсь за свою тупизну Все в порядке, вышеописаная цепочка из 28-ми чисел существует! Это не в книге ошибка, это я криворукий В TabControl-е добавил закладки, а вычисления всеравно до 5-го звена делал



Вопрос вот еще в чем: хотелось бы оценить, сколько делителей может быть у числа относительно самого числа? Насколько видно из алгоритма, число делителей N не может привышать 2*sqrt(N). Можно ли более точно оценить число делителей?

 

_DEN_

Количество подмножеств равно 2ⁿ только когда все элементы, в нашем случае факторы, разные. Для подавляющего большинства чисел это не так, т.е. мы имеем дело с классами элементов. Дубликатов таким образом не будет, кроме того перебор будет осуществляться аналогично твоему алгоритму только до половины общего количества факторов.

Зависит от того, насколько современные алгоритмы факторизации быстрее простого перебора до sqrt(N) и от самого числа. Для некоторых чисел будет действительно дольше, для некоторых быстрее(например n^m при большом m). Интересно сравнение в среднем.



По поводу факторизации вроде бы уже была тема.

3 одинаковых фактора -> {0,1,2,3} ->делители: {2⁰,2¹,2²,2³}

Как раз тот случай, когда проще найти все комбинации факторов чем делить в лоб(ну может не для 8, но для 1024 точно).

 

_DEN_

Прошу прощения, неточно выразился.

имеется в виду: сумма(делители а кроме самого а)=а-1. Например 8: 1+2+4=7=8-1=2³-1

 

Я в матиматике дуб, но может стОит учесть моменты поддающиеся "низкоуровневой" оптимизации - например, найти все делители являющиеся степенью 2 очень просто. деления заменить умножениями и т.п.

 

S_T_A_S_

Это не так важно. Главное, какая сложность. Лучше прога на визуальном бесике со сложностью O(N^2), чем на асме с оптимизацией с учетом особенностей архитектуры, но со сложностью O(N^3).



Вот еще интересно, существуют ли бесконечные цепочки? Или все цепочки либо сваливаются в единицу либо зацикливаются?

 

Кое-что на русском есть в книге "Живые числа": http://ega-math.narod.ru/Liv/index.htm



Но книжка уже довольно старая, поэтому оперативную информацию нужно смотреть в других источниках. Например, MathWorld:



Аликвотные последовательности: http://mathworld.wolfram.com/AliquotSequence.html



Совершенные числа: http://mathworld.wolfram.com/PerfectNumber.html



Дружественные числа: http://mathworld.wolfram.com/AmicablePair.html



Общительные числа: http://mathworld.wolfram.com/SociableNumbers.html

 

Перебор всех делителей лучше делать через разложение N. Например, если N=(p[1]^a[1])*...*(p[k]^a[k]), то все делители будут иметь вид (p[1]^b[1])*...*(p[k]^b[k]). 0<=b[k]<=a[k]. Нужно построить все вектора b. Например так b=(0,0,...,0), b[1] увеличивать на 1 пока b[1]<=a[1]. Когда b[1]>a[1], b[1]=0, увеличить b[2],... вобщем b-число в смешаной системе счисления. Одно увеличение b - один делитель.



З.Ы Число делителей вроде бы обычно должно быть меньше log2(N)^ln(ln(N))

 

RElf

Спасибо за инфу!



blood

Не, эта функция обгоняет 2*sqrt(N) где-то после 157.64. 2*sqrt(N) подходит лучше.



- - -



Интересную штуку обнаружил. У каждого числа при проверке на общительность есть три судьбы.



1. Свалиться в единицу.

2. Зациклиться, образовав совершенное, дружественное или общительное число.

3. Упереться в существующую цепочку. Например, 562 приходит к паре 220 - 284.



Интересненько...

 

Это же в точности сказано в http://mathworld.wolfram.com/AliquotSequence.html