| Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум на Исходниках.RU > Алгоритмы > Задача с уклоном на математику. Делители натурального числа. |
| Автор: FasterHarder 30.07.11, 02:45 |
| Всем алгоритмистам привет! Respect! Имеется в наличии такая задача: у некого натурального числа n ровно 6 натуральных делителей. Сумма этих делителей равна 3500. Необходимо детерминировать n. если честно, то даже примерно не представляю, какими теоремами / аксиомами / леммами можно воспользоваться... думал, что делители должны быть простыми числами, но из чего этого следует, непонятно, поэтому отвергаю... в принципе, можно 3500 разложить на множители простые, узнать делители, только что это даст, тоже непонятно... подскажите как быть то?...буду признателен... P.S. на Паскале, думаю, используя метод грубой силы, запрограммировал бы без особых проблем...хотя не факт... |
| Автор: 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 Дальше делителей становится слишком много. Таким образом число либо является 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 Так что перебор не так уж велик <{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}> Перебираем простые 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 31.07.11, 09:20 |
| http://www.eunnet.net/books/numbers/text/14.html По ссылке есть формулы количества делителей и суммы делителей для заданного числа. Используя их можно решить задачку, при этом перебор будет небольшим. Добавлено Скажем верны следующие неравенства: n^2/2<Ф(n)*S(n)<n^2. Где Ф(n) количество делителей числа n, S(n) сумма делителей числа n. Тогда n^2/2<21000<n^2 204>n>144 |
| Автор: Akina 31.07.11, 10:05 |
| Цитата FasterHarder @ Имеется в наличии такая задача: у некого натурального числа n ровно 6 натуральных делителей. Из условия неясно, входят ли в число этих 6: а) единица; б) само число. До устранения этой непонятки задачу решать бессмысленно. |
| Автор: MBo 31.07.11, 10:28 |
| Четное число делителей (не учитывая само число) может быть только у определенного класса чисел amk c тремя простыми в подсчете ошибся, и до p1^2*p2^2 не добрался а так его анализ дает практически всё, что нужно |
| Автор: Pavlovsky 31.07.11, 11:06 |
| 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 Добавлено Цитата Akina @ Из условия неясно, входят ли в число этих 6: а) единица; б) само число. До устранения этой непонятки задачу решать бессмысленно. Если автор не оговорил особенностей, то считаем как принято в математике. Единица и само число считаются делителями. |
| Автор: Pavlovsky 01.08.11, 11:36 |
| Суммы делителей (<=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 |
| Автор: Akina 01.08.11, 12:26 |
| Короче, это число 1996, его делители дают в сумме 1 + 2 + 4 + 499 + 998 + 1996 = 3500 |
| Автор: amk 01.08.11, 13:55 |
| MBo, я не столько ошибся, сколько использовал немного другое понятие делителя, когда само число как делитель не учитывается. Впрочем я это писал скорее, чтобы задать одно из возможных направлений поиска. |
| Автор: FasterHarder 06.02.12, 18:42 |
| решил вернуться к данной задаче и добить ее... Цитата amk @ Если число имеет два делителя 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, где выводятся все формулы для делителей, но мне не хочется их использовать, ибо они используют разные леммы, все теоремы нужно доказывать (абсолютно приводить все выкладки), и что САМОЕ важное, на выходе получается уравнение: имхо, ни сколь не проще (моего) ... мне очень нужно понять, как ОПТИМАЛЬНО решить данное уравнение (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 может быть решение (я об этом писал раньше)... так нужно решать подобное уравнение??...то есть перебирать ВСЕ ВОЗМОЖНЫЕ ДЕЛИТЕЛИ полагаясь на удачу!... |
| Автор: FasterHarder 06.02.12, 21:11 |
| все, я понял!... p1^2 + p1 + 1 = p1 (p1 + 1) + 1 - ЭТО НЕЧЕТНОЕ ЧИСЛО!...это ключ к решению... следовательно, нужно перебрать ТОЛЬКО нечетные делители, а их всего...всего: 5, 25, 7, 125, 35, 875, 175 (правда их нужно суметь вывести).. ну и подойдет число, равное 7... всем пасибо! вопросов не имею... Добавлено кстати, все делители, оканчивающиеся на 5 не подойдут, т к дискриминант не извлекается в натур. число... p1^2 + p1 + 1 - xx5 = p1^2 + p1 - xx4 = 0 D = 1^2 - 4 * (-xx4) = 1 + xxx6 = xxx7 а не существует натурального числа, которое можно получить извлечением ариф. корня из другого натурального числа, оканчивающегося на 7... тогда перебор сокращается до ОДНОГО числа, это 7...а вот это сверхкруто!...Четкая детерминация ответа, без переборов и избыточности...вот она, КРАСОТА математики!... |