На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное DigiMania RSS RSS
>  Форум на Исходниках.RU
       Программирование
         Алгоритмы
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишите свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: shadeofgray, esperanto
   Новое голосование

> Задача с уклоном на математику. Делители натурального числа.
FasterHarder
Сообщ. #1, 30.07.11, 02:45

Master
******
Профиль · PM


Всем алгоритмистам привет! Respect!
Имеется в наличии такая задача: у некого натурального числа n ровно 6 натуральных делителей. Сумма этих делителей равна 3500. Необходимо детерминировать n.
если честно, то даже примерно не представляю, какими теоремами / аксиомами / леммами можно воспользоваться...
думал, что делители должны быть простыми числами, но из чего этого следует, непонятно, поэтому отвергаю...
в принципе, можно 3500 разложить на множители простые, узнать делители, только что это даст, тоже непонятно...

подскажите как быть то?...буду признателен...

P.S. на Паскале, думаю, используя метод грубой силы, запрограммировал бы без особых проблем...хотя не факт...
___________
I originate
You must appreciate, all the others imitate

SCOOTER "GUEST LIST"

'Pon the mic I'm the teacher!
Spread my words like a preacher!
Yiiihhaaaa!!!!

SCOOTER "WEEKEND"
amk
Сообщ. #2, 30.07.11, 04:16

Guru
*******
Профиль · PM

Поощрения: 4 Dgm
Рейтинг (т): 230

Если число имеет два делителя n1 и n2, то НОК(n1,n2) тоже является делителем (если не совпадает с самим числом), и оно тоже натуральное.

Так что перебираем возможные варианты комбинаций простых делителей м определяем число делителей.
N = p1 - имеет один делитель - 1
N = p1^2 - имеет 2 делителя - 1, p1
N = p1^3 - имеет 3 делителя - 1, p1, p1^2
N = p1^4 - имеет 4 делителя - 1, p1, p1^2, p1^3
N = p1^5 - имеет 5 делителей - 1, p1, p1^2, p1^3, p1^4
N = p1^6 - имеет 6 делителей - 1, p1, p1^2, p1^3, p1^4, p1^5
N = p1*p2 - имеет три делителя - 1, p1, p2
N = p1^2*p2 - имеет 5 делителей - 1, p1, p1^2, p2, p1*p2
N = p1^3*p2 - имеет 7 делителей - 1, p1, p1^2, p1^3, p2, p1*p2, p1^2*p2
N = p1*p2*p3 - имеет 6 делителей - 1, p1, p2, p3, p1*p2, p1*p3, p2*p3
Дальше делителей становится слишком много.

Таким образом число либо является 6 степенью какого-то простого числа, либо является произведением 3 простых чисел.

В первом случае сумма равна 1 + p1 + p1^2 + p1^3 + p1^4 + p1^5 = (p1^6 - 1)/(p1 - 1)
Простой перебор показывает, что ни одно простое число не позволяет получить число 3500.

Во втором случае S = 1 + p1 + p2 + p3 + p1*p2 + p1*p3 + p2*p3
Кроме перебора на ум ничего не приходит.
Так что прикинем объем.
Пусть p3 - наибольший из сомножителей, максимального значения он может достигать, если p1 и p2 - минимальны (2 и 3)
p3 <= 581
Если сомножители близки по величине, то они окажутся в районе 30-40
Так что перебор не так уж велик
ExpandedWrap disabled
    Перебираем простые p1
      count = 0
      Перебираем простые p2 > p1
        Вычисляем по ним p3 = (S - (1 + p1 + p2 + p1*p2))/(1 + p1 + p2)
        Если p3 получился меньше или равен p2 переходим к следующему p1
        count += 1
        Если при делении получился остаток, переходим к следующей паре
        Если p3 простое, имеем вариант ответа N = p1*p2*p3
      Если count == 0, конец работы
___________
Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
Pavlovsky (Online)
Сообщ. #3, 31.07.11, 09:20

Senior Member
****
Профиль · PM

Рейтинг (т): 61

http://www.eunnet.net/books/numbers/text/14.html
По ссылке есть формулы количества делителей и суммы делителей для заданного числа.
Используя их можно решить задачку, при этом перебор будет небольшим.

Добавлено 31.07.11, 09:29
Скажем верны следующие неравенства: n^2/2<Ф(n)*S(n)<n^2. Где Ф(n) количество делителей числа n, S(n) сумма делителей числа n.
Тогда
n^2/2<21000<n^2
204>n>144
___________
Мне не нужен код. Мне нужны безумные идеи. Незамыленный взгляд стороннего наблюдателя. Ссылки по обсуждаемой проблеме.
Guru Akina
Сообщ. #4, 31.07.11, 10:05
Guru
*******
Профиль · PM

Поощрения: 35 Dgm
Рейтинг (т): 410

Цитата (FasterHarder @ 30.07.11, 02:45)
Имеется в наличии такая задача: у некого натурального числа n ровно 6 натуральных делителей.

Из условия неясно, входят ли в число этих 6:
а) единица;
б) само число.
До устранения этой непонятки задачу решать бессмысленно.
___________
Есть претензии ко мне как к модератору? читайте Правила, разделы 5 и 6, и действуйте соответственно.
Есть претензии ко мне как к участнику? да ради бога.
Не нравятся мои ответы? не читайте их.
В общем, берегите себя. Нервные клетки не восстанавливаются.
MBo
Сообщ. #5, 31.07.11, 10:28
Profi
*****
Профиль · PM

Поощрения: 3 Dgm
Рейтинг (т): 241

Четное число делителей (не учитывая само число) может быть только у определенного класса чисел
amk c тремя простыми в подсчете ошибся, и до p1^2*p2^2 не добрался а так его анализ дает практически всё, что нужно
Pavlovsky (Online)
Сообщ. #6, 31.07.11, 11:06

Senior Member
****
Профиль · PM

Рейтинг (т): 61

6 делителей имеют числа вида:
1) p^5 (1,p,p^2,p^3,p^4,p^5)
2) p1*p2^2 (1,p1,p1*p2,p1*p2^2,p2,p2^2)

сумма делителей равна для
1) (p^6-1)/(p-1)=3500
2) [(p1^2-1)/(p1-1)]*[(p2^3-1)/(p2-1)]=3500

Добавлено 31.07.11, 11:09
Цитата (Akina @ 31.07.11, 10:05)
Из условия неясно, входят ли в число этих 6:
а) единица;
б) само число.
До устранения этой непонятки задачу решать бессмысленно.


Если автор не оговорил особенностей, то считаем как принято в математике. Единица и само число считаются делителями.
___________
Мне не нужен код. Мне нужны безумные идеи. Незамыленный взгляд стороннего наблюдателя. Ссылки по обсуждаемой проблеме.
Pavlovsky (Online)
Сообщ. #7, 01.08.11, 11:36

Senior Member
****
Профиль · PM

Рейтинг (т): 61

Суммы делителей (<=3500) которые можно получить из чисел имеющих 6 делителей.
Цитата
39 52 78 93 104 124 156 171 182 186 228 234 248 260 312 342 372 390 399 416 434 456 494 532 546 549 558 572 620 624 650 684
702 732 744 780 798 798 806 921 930 992 1026 1064 1098 1140 1143 1178 1228 1302 1364 1368 1464 1488 1524 1550 1596 1659 1674 1710 1824 1842
1860 1862 1922 2166 2196 2212 2286 2394 2394 2456 2508 2562 2613 2660 2736 2850 2979 3048 3078 3294 3318 3420 3484


Сообщение отредактировано: Pavlovsky - 01.08.11, 11:36
___________
Мне не нужен код. Мне нужны безумные идеи. Незамыленный взгляд стороннего наблюдателя. Ссылки по обсуждаемой проблеме.
Guru Akina
Сообщ. #8, 01.08.11, 12:26
Guru
*******
Профиль · PM

Поощрения: 35 Dgm
Рейтинг (т): 410

Короче, это число 1996, его делители дают в сумме 1 + 2 + 4 + 499 + 998 + 1996 = 3500
___________
Есть претензии ко мне как к модератору? читайте Правила, разделы 5 и 6, и действуйте соответственно.
Есть претензии ко мне как к участнику? да ради бога.
Не нравятся мои ответы? не читайте их.
В общем, берегите себя. Нервные клетки не восстанавливаются.
amk
Сообщ. #9, 01.08.11, 13:55

Guru
*******
Профиль · PM

Поощрения: 4 Dgm
Рейтинг (т): 230

MBo, я не столько ошибся, сколько использовал немного другое понятие делителя, когда само число как делитель не учитывается. Впрочем я это писал скорее, чтобы задать одно из возможных направлений поиска.
___________
Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
FasterHarder
Сообщ. #10, 06.02.12, 18:42

Master
******
Профиль · PM


решил вернуться к данной задаче и добить ее...
Цитата (amk @ 30.07.11, 04:16)
Если число имеет два делителя n1 и n2, то НОК(n1,n2) тоже является делителем (если не совпадает с самим числом), и оно тоже натуральное.

Так что перебираем возможные варианты комбинаций простых делителей м определяем число делителей.
N = p1 - имеет один делитель - 1
N = p1^2 - имеет 2 делителя - 1, p1
N = p1^3 - имеет 3 делителя - 1, p1, p1^2
N = p1^4 - имеет 4 делителя - 1, p1, p1^2, p1^3
N = p1^5 - имеет 5 делителей - 1, p1, p1^2, p1^3, p1^4
N = p1^6 - имеет 6 делителей - 1, p1, p1^2, p1^3, p1^4, p1^5
N = p1*p2 - имеет три делителя - 1, p1, p2
N = p1^2*p2 - имеет 5 делителей - 1, p1, p1^2, p2, p1*p2
N = p1^3*p2 - имеет 7 делителей - 1, p1, p1^2, p1^3, p2, p1*p2, p1^2*p2
N = p1*p2*p3 - имеет 6 делителей - 1, p1, p2, p3, p1*p2, p1*p3, p2*p3
Дальше делителей становится слишком много.

здесь все круто и здесь я ВСЕ сейчас понял...Единственное, как было замечено ниже, не учтено, что само число также является делителем...просто я не написал об этом сразу (моя ошибка!)...
в этом случае подходит комбинация делителей:
p1^2 * p2 * [1]
Делители: 1, p1, p2, p1^2, p1 * p2, p1^2 * p2...
именно эти же делители ниже привел Pavlovsky, но я их тоже получил, опираясь на пост №2...
В итоге имеем уравнение:
1 + p1 + p2 + p1^2 + p1 * p2 + p1^2 * p2 = 3500
группируем:
(p1^2 + p1^2 * p2) + (p1 + p1 * p2) + (p2 + 1) = 3500
вынесение общих множителей:
p1^2(1 + p2) + p1(1 + p2) + (1 + p2) = 3500
вынесение ОБЩЕГО МНОЖИТЕЛЯ за скобки:
(1 + p2) * (p1^2 + p1 + 1) = 3500 (мое)
*сразу скажу, что я ходил по ссылке, приведенной Pavlovsky, где выводятся все формулы для делителей, но мне не хочется их использовать, ибо они используют разные леммы, все теоремы нужно доказывать (абсолютно приводить все выкладки), и что САМОЕ важное, на выходе получается уравнение:
Цитата (Pavlovsky @ 31.07.11, 11:06)
[(p1^2-1)/(p1-1)]*[(p2^3-1)/(p2-1)]=3500

имхо, ни сколь не проще (моего) ...
мне очень нужно понять, как ОПТИМАЛЬНО решить данное уравнение (1 + p2) * (p1^2 + p1 + 1) = 3500 в натуральных неизвестных...
чтобы много не расписывать сразу скажу, что знаю:
выражение (p1^2 + p1 + 1) равно одному из делителей числа 3500 в ЕДИНСТВЕННОМ случае!...(как это доказать - вообще без понятия, скорее всего и не потребуется в решении)..
Разложим 3500 на простые множители (основная теорема арифметики): 2 * 2 * 5 * 5 * 5 * 7
Очевидно, что (1 + p2) = одному из делителей 3500 и (p1^2 + p1 + 1) = одному из делителей 3500...
Вопрос: сколько всего РАЗЛИЧНЫХ делителей у числа 3500?
Ответ: не уверен, но возможно, нужно использовать "перестановку с повторяющимися элементами".
m1 = 2 (двойка встречается 2 раза)
m2 = 3 (пятерка встречается 3 раза)
m3 = 1 (семерка встречается 1 раз)...не уверен, что нужно учитывать в формуле, если 1 раз встречается...
m = m1 + m2 + m3 = 2 + 3 + 1 = 6
Число перестановок равно: (m! / (m1! * m2! * m3!) = 6! / (2! * 3! * 1!) = (1 * 2 * 3 * 4 * 5 * 6) / (1 * 2 * 2 * 3) = 2 * 5 * 6 = 60 [вариантов], но мне кажется, что здесь будет меньше, чем 60...

в итоге, берем 1 вариант (например, делитель = 2) и пытаемся решить в целых уравнение:
(p1^2 + p1 + 1) = 2
целых корней нет
берем 2 вариант (например, делитель 2 * 2 = 4) и пытаемся решить в целых уравнение:
(p1^2 + p1 + 1) = 4
целых корней нет
и так далее, пока НЕ НАТКНЕМСЯ на делитель равный 7 и потом, О ЧУДО, РЕШЕНИЕ есть и p1 = 2!...кстати только для 7 может быть решение (я об этом писал раньше)...

так нужно решать подобное уравнение??...то есть перебирать ВСЕ ВОЗМОЖНЫЕ ДЕЛИТЕЛИ полагаясь на удачу!...
___________
I originate
You must appreciate, all the others imitate

SCOOTER "GUEST LIST"

'Pon the mic I'm the teacher!
Spread my words like a preacher!
Yiiihhaaaa!!!!

SCOOTER "WEEKEND"
FasterHarder
Сообщ. #11, 06.02.12, 21:11

Master
******
Профиль · PM


все, я понял!...
p1^2 + p1 + 1 = p1 (p1 + 1) + 1 - ЭТО НЕЧЕТНОЕ ЧИСЛО!...это ключ к решению...
следовательно, нужно перебрать ТОЛЬКО нечетные делители, а их всего...всего: 5, 25, 7, 125, 35, 875, 175 (правда их нужно суметь вывести)..
ну и подойдет число, равное 7...

всем пасибо! вопросов не имею...

Добавлено 06.02.12, 21:20
кстати, все делители, оканчивающиеся на 5 не подойдут, т к дискриминант не извлекается в натур. число...
p1^2 + p1 + 1 - xx5 = p1^2 + p1 - xx4 = 0
D = 1^2 - 4 * (-xx4) = 1 + xxx6 = xxx7
а не существует натурального числа, которое можно получить извлечением ариф. корня из другого натурального числа, оканчивающегося на 7...

тогда перебор сокращается до ОДНОГО числа, это 7...а вот это сверхкруто!...Четкая детерминация ответа, без переборов и избыточности...вот она, КРАСОТА математики!...

Сообщение отредактировано: FasterHarder - 06.02.12, 21:22
___________
I originate
You must appreciate, all the others imitate

SCOOTER "GUEST LIST"

'Pon the mic I'm the teacher!
Spread my words like a preacher!
Yiiihhaaaa!!!!

SCOOTER "WEEKEND"
0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
0 пользователей:

> Форум на Исходниках.RU · Алгоритмы

Новое голосование


[ Script Execution time: 0,1606 ]   [ 15 queries used ]   [ Generated: 16.04.14, 10:29 GMT ]  

Rambler's Top100