Разложение числа на множители.

← →
Думкин © (2010-05-06 10:45) [40]

> Игорь Шевченко © (06.05.10 10:29) [39]

Ломает со сложением? Это чего такое сломать то можно? Он же разложением то так и не занимается. Тут только мозг собеседнику сломать и вынести можно. Не более.

← →
Игорь Шевченко © (2010-05-06 10:47) [41]

Думкин © (06.05.10 10:45) [40]

> Ломает со сложением? Это чего такое сломать то можно? Он
> же разложением то так и не занимается.

как умеет :))

← →
Rouse_ © (2010-05-06 11:03) [42]

Ломать RSA разложением паблик ключа на множители при длине ключа от 768 достаточно бесперспективная задача и более того практическое применение при успешном разложении достаточно смутно видится. Если задача состоит в декрипте блока данных, то обычно это дают делать приложению, после чего дампят открытые данные :)

← →
имя (2010-05-06 11:23) [43]

Удалено модератором

← →
'<> (2010-05-06 11:37) [44]

> Вот 28, например. Мне всю доргу казалось, что его разложение
> выглядит так:
>
> 28 = 7*2^2
>
> Но оказывается, возможны варианты в виде:
>
> 28 = 3^3+1=5^2+3 и тп. Тту безусловно кнут поможет, но в
> виде оберток для курения конопли.

=) Пойми же, мне надо максимально использовать степень!
(28 = 7*2^2) - тут используется только степень ^2, ведь можно как раз использовать такое выражение (3^3+1) и получим тот же результат, но это будет удовлетворять моим нуждам.

Я ничего не ломаю, это эксперимент. По сабжу необходимо, то что я зацитатил (использовать степень отличную от ^2, а максимально эффективную), обертки тут не причем, разве так сложно вообразить степень больше ^2 при разложении.

← →
Anatoly Podgoretsky © (2010-05-06 11:45) [45]

> Игорь Шевченко (06.05.2010 10:29:39) [39]

Научная основа - это навешать лапши на уши?

← →
Думкин © (2010-05-06 11:47) [46]

> Пойми же, мне надо максимально использовать степень!

Ну, значит сабж не соответствует запросу. И пока это похоже на заклинание

"Люк, используй СИЛУ СТЕПЕНИ!!, максимально эффективную"

Люк, наверное, просечет в чем эта максимальная эффективность силы, но мне с моим ограниченным образованием подобное не под силу. Так надо то чего в итоге все-таки, Йода?

← →
' (2010-05-06 11:56) [47]

Может это реализуемо через НОД НОК? Может подбор как-то через это можно наладить?

← →
Думкин © (2010-05-06 12:01) [48]

> "<> (06.05.10 11:56) [47]

Подбор чего? Задача то так и не сформулирована.

← →
' (2010-05-06 12:07) [49]

Задача в том. Допустим, есть число:

28 = 7*2^2 (это находится как Корень из 28 в степени 2)

Но можно разложить так:

28 = 3^3+1 (тут уже засчет степени мы приблизились к исходному числу)

Так сказать степень и число под степенью чтоб было максимально близкое в результате к исходному числу.
Может найти можно как-то через НОД НОК?

Это основная задача. Пожалуйста помогите. Что-то типа колмогоровского числа.

← →
Думкин © (2010-05-06 12:12) [50]

> Так сказать степень и число под степенью чтоб было максимально
> близкое в результате к исходному числу

a = a^1+0 Гы. :)

← →
Омлет © (2010-05-06 12:22) [51]

Логарифмирование перебором.

← →
oldman © (2010-05-06 12:32) [52]

> "<> (06.05.10 12:07) [49]

Начиная с 1 и до бесконечности извлекаешь корень степени n из искомого числа до того момента, пока результат не станет меньше двойки.
Ты нашел максимальную степень, поздравляю.
Потратив уйму времени.
Даже для четырехзначного 1024 надо дойти до n=10
А у тебя 30...40 значное число
Успехов в переборе!!! :)))

> Думкин © (06.05.10 12:12) [50]
> > Так сказать степень и число под степенью чтоб было максимально
> > близкое в результате к исходному числу
> a = a^1+0 Гы. :)

Неа.
a = 1^(бесконечность)+a
Два раза Гы :)

← →
Дмитрий С © (2010-05-06 12:45) [53]

> Начиная с 1 и до бесконечности извлекаешь корень степени
> n из искомого числа до того момента, пока результат не станет
> меньше двойки.
> Ты нашел максимальную степень, поздравляю.
> Потратив уйму времени.
> Даже для четырехзначного 1024 надо дойти до n=10
> А у тебя 30...40 значное число

Можно применить половинное деление (или как оно называется). Наподобие поиска числа в отсортированном массиве.

Автору,
Самый простой способ:
1. Делаешь тупым перебором, отлаживая на маленьких числах.
2. Оптимизируешь то, что у тебя получилось.

А пока складывается ощущение, что ты сам не понял чего хочешь.

← →
Alx2 © (2010-05-06 14:03) [54]

N=sum(a[k]^b[k])+sum(c[k]*d[k])
max( min(a[k],b[k],c[k],d[k], for all k)) -> min?

← →
Alx2 © (2010-05-06 14:04) [55]

Вдогонку к Alx2 © (06.05.10 14:03) [54]
Имелось в виду при фиксированном кол-ве слагаемых

← →
Думкин © (2010-05-06 16:18) [56]

> Alx2 © (06.05.10 14:03) [54]

Я так думаю, что там типо хитрым вывинтом рассыпав бисер хочется собрать Бородино.

Берем число 99^99+98*97 получаем кучу цифр и радуемся, что выразить его смогли используя лишь 4 байта. Думаем, что таким финтом сможем поступит с любым числом которое имеет такое же хитрое и большое написание в десятричной системе.

Допустим смотрим на числа в виде a^b+c*d и {a,b,c,d}<=100

В итоге получаем максимальное в виде 100^100+100*100, что впечатляет, а чисел помечаем лишь 100^4, притом получаем дырки непомеченных в среднем уровня 10^98. Вот последнего, видимо, пока и не понятно автору.

ТО есть при заданном мной, я беру число (99^100+100^100+1)/2 и ищу ео выражение в указаном виде. Ну и все. Можно поднять величину числа a, а потом и других. В итоге приходим, что банальная запись в виде двоичного куда экономнее. Потому чего хочет автор - только Йода знает.

← →
И. Павел © (2010-05-06 16:28) [57]

> задание по сокращению базы данных

Интересно, а вообще есть какой-нибудь способ сжать число, представленное в обычном двоичном виде, а не в виде текста? Если появление всех чисел равновероятны, то и появление всех цифр в определенной позиции определенного числа тоже равновероятны. ИМХО такое просто нельзя сжать, т.к. избыточности нет.

← →
Игорь Шевченко © (2010-05-06 16:30) [58]

> Интересно, а вообще есть какой-нибудь способ сжать число,
> представленное в обычном двоичном виде

zip вот сжимает

← →
И. Павел © (2010-05-06 16:33) [59]

> zip вот сжимает

Ну там, наверное, несколько чисел. И архиватор находит какую-нибудь закономерность - кто-то встречается в 49% случаях, а что-то в 51%. Или нет? Если нет, то интересно было бы знать - как это делается?

← →
Думкин © (2010-05-06 18:08) [60]

Удалено модератором

← →
TUser © (2010-05-06 18:10) [61]

Удалено модератором

← →
Конформист (2010-05-06 21:19) [63]

> "<> (05.05.10 13:57)

Тоже "4исла" смотрел? Лимон, как Перельман хочешь?

← →
' (2010-05-06 23:00) [65]

................................................................................ ..........
................................................................................ ..........
..............................Тема закрыта.
................................................................................ ..........
................................................................................ ..........

Все перетекло совсем в другое русло.

Тему закроют тогда, когда захотят другие. Русло то самое. Но задачу так и не услышали. Жаль. А ведь верная постановка - уже полдела. До науки тут как известным методом до Луны, да.

>Думкин © (06.05.10 16:18) [56]

При таком подходе - да, конечно :)

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

> Alx2 © (07.05.10 09:07) [68]

Да про сжатие чисел - мол к шарлатанам надо обращаться (про биективные отображения не счел нужным и видимо зря). :) А потом просто нотацию прочитал про весенне-юношеское обострение. :)

А интерес ради интереса понятен, но я хотел таки автора подтолкнуть к формулированию своей задачи и осознанию ее. Но этого не произошло. Он просто обиделся.

Кстати, здесь еще лишь один шаг, и будет задачка поиска сложности по-Колмогорову (у него это минимальная по длине программа (на Паскале ;-) ), генерирующая заданное число).

Разложение числа на множители. Найти похожие ветки