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

RElf

Веришь - нет, не читал! Я только SociableNumbers.html успел прочитать...



Вот интересно, почему самые большие известные общительные числа не привышают триллиона? Их что, на нормальных тачках не гоняли, на которых гоняют число пи и числа Мерсена?



Всетаки удивительно... Самая большая, оторвавшаяся от всех вдалеке цепочка из 28 чисел была найдена без помощи компа. Это не иначе как проделки Нео...

 

RElf



Спасибо за ссылки, там приводится то же утверждение:



A number is least deficient iff it is a powers of 2



и опять же без доказательства("least deficient"=="слегка недостаточное") Или это я плохо искал?



blood

Так о том и речь..

А можно поподробнее, очень интересно откуда такая формула. Убил на неё последние два часа, так и не понял.



P.S. Зато получил красивое тождество

(log_ab)^(log_c(log_de))=(log_de)^(log_c(log_ab))

Подкину его младшему поколению для тренировки

 

_DEN_



Ла я не о "2 раза ку" или "3 раза ку" А том, что можно просто не вычислять то, что и так уже видно из бинарного представления числа. например, для 8 все множители можно найти за "одно действие"

 

log2(N)^ln(ln(N)) я наколенке прикинул Видимо перестарался... Получается она так: N=(p[1]^a[1])*...*p[k]^a[k]), логарифмируем, log2(N)=summ(i=1..k,a*log2(p)). log2(p)>=1 т.к p>=2, заменяем log2(p)):=1, получаем summ(i=1..k,a)<log2(N). Число делителей равно (a[1]+1)*...*(a[k]+1). Максимум произведения при выше приведеных ограничениях(х.з. вроде должен быт равен (1+log2(N)/k)^k. матожидание k гдето ln(ln(N)) (см. кнута например). В прошлый раз я немного ошибся, вдобавок перестарался упрощая форулу... Ответ (барабанная дробь) (1+ log2(N)/ln(ln(N)) )^ln(ln(N))

З.Ы. Меньше sqrt(N) кстати

 

MathWorld ссылается на OEIS, которая утверждает что степени 2-ки - это в точности



Least deficient numbers (i.e. n such that sigma(n)=A000203(n)=2n-1). - Lekraj Beedassy (boodhiman(AT)yahoo.com), Jun 03 2004



Так что, имеет смысл спросить этого чувака насчет доказательства.



Кстати, "least deficient" = "наименее недостаточное"

 

Cумму всех делителей для всех чисел из диапазона a..b можно посчитать аналогично решету Эратосфена за, примерно, sqrt(b)+(b-a)*ln(b)

 

but the readability of this source == 0 - as all sources from ioccc

 

blood

Да, действительно, в этот раз лучше



S_T_A_S_

Я понимаю, но в этом случае выигрыш в скорости не зависит от числа данных.



blood

Поясни...



- - -



На сколько мне подсказывает интуиция, бесконечных цепочек не бывает (я опять о поиске общительных). Для этого числам цепочки пришлось бы постоянно возрастать, а мне кажется что не существует такого "пути" который не встретит одну из трех своих судеб.

 

_DEN_

Берется массив R[a..b].

для i от 1 до [sqrt(b)]

к каждому i-ому элементу массива R добавляется i, а

также (индекс_текущего_элемента/i). Причем выбирать

элементы нужно так как будто массив не R[a..b], а R[1..b]

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

множителя больше одного раза!(я добавлял (индекс_текущего_элемента/i)

только в случае, когда индекс_текущего_элемента>i*[sqrt(b)])



В аттаче прога на паскале(вроде не глючит но писалась за минуты)

_2101676461__PERFNUM.PAS

 

blood

Наверное можно сделать главный цикл от 1, изменить if s<=i на if s<i и убрать первый цикл целиком.



Поправка: нет, тогда скорость немного уменьшится.

 

Stiver



Похоже, утверждение

A number is least deficient iff it is a powers of 2

является открытой проблемой. Она так и позиционируется в другой статье на MathWorld и там есть ссылка на авторитетную книгу R.Guy "Unsolved Problems in Number Theory".



В описании A000079 она ошибочно указана как доказанный факт, а MathWorld в статье "Least Deficient Number" просто повторил эту ошибку.

 

RElf

Как мне кажется в A000079 утверждается только, что степени двойки являются "least deficient numbers", обратного я там не видел. Так что ответственность за ошибку лежит скорее всего целиком на MathWorld.



Вот здесь( http://mathforum.org/epigone/sci.math.research/bulvirfloo) есть доказательство, что слегка недостаточное число должно быть четным. Вместе с нашими усилиями следует: a слегка недостаточное => a=2^ks² где k>0 и s нечетное. Осталось доказать s=1.

 

Stiver

A000079 исходно определяется как последовательность степеней 2-ки, а потом идет альтернативное определение как "least deficient numbers". Это равносильно утверждению, что каждое слегка недостаточное число является степенью 2-ки и наоборот. А MathWorld собственно просто скопировал это утверждение.

 

RElf

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