00:20 

Деление с остатком

wpoms.
Step by step ...
Пусть натуральное число `n` имеет ровно `120` натуральных делителей (включая `1` и `n`). Для каждого делителя числа `n`, обозначим его `d`, `q` - неполное частное и `r` - остаток от деления `4*n - 3` на `d`. Пусть `Q` - сумма всех неполных частных `q` и `R` - сумма остатков `r` от деления `4*n - 3` на `d`. Найдите `Q - 4*R`, в ответе укажите все возможные значения.
Пояснение:


@темы: Теория чисел

Комментарии
2013-03-04 в 10:12 

Adjirranirr
Только дурак нуждается в порядке — гений господствует над хаосом.
`n`, очевидно, больше, скажем, чем 100. Значит,
`(4n - 3)\text{div} n = (3n + (n - 3)) \text{div} n = 3`
`(4n - 3)\text{mod} n = n - 3`.
Обозначим
`{ (Q(n) = \sum_{d | n} (4n - 3) \text{div} d), (R(n) = \sum_{d | n} (4n - 3) \text{mod} d) :}`
Тогда, по формуле обращения Мёбиуса,
`{((4n - 3) \text{div} n = \sum_{d | n} \mu(d) Q(n/d)), ((4n - 3) \text{mod} n = \sum_{d | n} \mu(d) R(n/d)) :}=>{(\sum_{d | n} \mu(d) Q(n/d), =, 3), (\sum_{d | n} \mu(d) R(n/d),=,n-3) :}`
Применяя обращение еще раз, получим
`{ (Q(n), =, \sum_{d | n}3,=,120*3), (R(n), =, \sum_{d | n}d-3,=,-360 + \sum_{d|n} d) :}`

Пусть теперь `n = p_1^{k_1} * p_2^{k_2} * ... * p_m^{k_m}`. Тогда `n` имеет ровно 120 делителей тогда и только тогда, когда `(k_1 + 1) * (k_2 + 1) * ... * (k_m + 1) = 120`. Очевидно, при этом простые `p_i` могут быть выбраны произвольно. Пусть `\sigma(n)` — сумма натуральных делителей числа `n`, тогда `R(n) = \sigma(n) - 360`, и `Q(n) - 4R(n) = 1800 - 4\sigma(n)`.

2013-03-04 в 19:12 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Adjirranirr, Задания заявляются как школьные олимпиады... уж не знаю, известны ли школьникам формулы обращения Мёбиуса... читать дальше
Не обращая на это внимания, скажу, что у меня частный случай с Вашим ответом не сходится...
Рассмотрим число `n = 2^{119}`... Его делители имеют вид `d = 2^k, \ k in {0; 1; ... ; 119}`...
Тогда `N = 4*n - 3 = 2^{121} - 3`... следовательно, `N \text{div} 2^k = 2^{121 - k} - 1, \ \ N \text{mod} 2^k = 2^k - 3`...
При этом `Q = sum_{k = 0}^{119} 2^{121 - k} - 1 = 2^{122} - 2^2 - 120, \ \ R = sum_{k = 0}^{119} 2^k - 3 = 2^{120} -1 - 3*120 \ \ => \ \ Q - 3*R = 2^{122} - 2^2 - 120 - 4*(2^{120} - 1 - 3*120) = 11*120 = 1320 > 0`
А согласно Вашему ответу `sigma(2^{119}) = sum_{k = 1}^{119} 2^k = 2^{120} - 1` и тогда `1800 - 4*sigma(n) < 0`... Ну, как-то так... или я чего-то недопонял?... :upset:

2013-03-04 в 20:01 

Adjirranirr
Только дурак нуждается в порядке — гений господствует над хаосом.
Да я вот тоже чего-то недопонял =) Но в своем решении найти ошибку не могу.

2013-03-04 в 21:36 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Несмотря на то, что немного обогатился знаниями про формулы обращения Мёбиуса :shuffle2:, но ошибки найти не могу... про это сразу в голову ничего не приходит...

Если решать без этих формул, то получил вот что...
Пусть `n = p_1^{k_1} * p_2^{k_2} * ... * p_m^{k_m}`, где `p_1, ..., p_m` - простые числа
Тогда делители имеют вид `d = p_1^{k_1 - s_1} * p_2^{k_2 - s_2} * ... * p_m^{k_m - s_m}`...

Поскольку `4*n - 3 = 4*p_1^{k_1} * p_2^{k_2} * ... * p_m^{k_m} - 3 = (4*p_1^{s_1} * p_2^{s_2} * ... * p_m^{s_m} - 1)*[p_1^{k_1 - s_1} * p_2^{k_2 - s_2} * ... * p_m^{k_m - s_m}] + (p_1^{k_1 - s_1} * p_2^{k_2 - s_2} * ... * p_m^{k_m - s_m} - 3)`, то получаем, что

`Q(n) = sum_{s_1, ..., s_m} (4*p_1^{s_1} * p_2^{s_2} * ... * p_m^{s_m} - 1), \ \ R(n) = sum_{s_1, ..., s_m} (p_1^{k_1 - s_1} * p_2^{k_2 - s_2} * ... * p_m^{k_m - s_m} - 3),`

Очевидно, что `sum_{s_1, ..., s_m} (p_1^{s_1} * p_2^{s_2} * ... * p_m^{s_m}) = sum_{s_1, ..., s_m} (p_1^{k_1 - s_1} * p_2^{k_2 - s_2} * ... * p_m^{k_m - s_m})`...

Таким образом, `Q(n) - 4*R(n) = sum_{s_1, ..., s_m} (4*p_1^{s_1} * p_2^{s_2} * ... * p_m^{s_m} - 1) -4*sum_{s_1, ..., s_m} (p_1^{k_1 - s_1} * p_2^{k_2 - s_2} * ... * p_m^{k_m - s_m} - 3) = 11*sum_{s_1, ..., s_m} 1`, то есть ответ не зависит от выбора чисел `p_1, ..., p_m`

Поскольку `s_i in {0; 1; ... ; k_i}`, то `sum_{s_1, ..., s_m} 1 = (k_1 + 1) * (k_2 + 1) * ... * (k_m + 1)`, что является общим числом делителей... ИТОГО, `Q(n) - 4*R(n) = 11*120 = 1320`

Вооот.... :hot: ...

2013-03-04 в 21:45 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Правда тут подумалось, что остаток, вычисляемый по формуле `p_1^{0} * p_2^{0} * ... * p_m^{0} - 3` читать дальше будет отрицательным... то есть ответ надо подшаманивать читать дальше... Видимо не зря в условии намекали про все варианты ответа...

2013-03-04 в 22:44 

Adjirranirr
Только дурак нуждается в порядке — гений господствует над хаосом.
Простенький код для maple:

Вывод:


Наводит на мысли =) Ну, по крайней мере, 1320, похоже, нет.

2013-03-04 в 22:51 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Ну, по крайней мере, 1320, похоже, нет. - Ну, видимо, это как раз поправка на вид целой части и остатка при делении на 1 и 2...

2013-03-04 в 23:18 

Adjirranirr
Только дурак нуждается в порядке — гений господствует над хаосом.
Экспериментально проверил можно наблюдать, что если `n` четно, то `Q - 4*R = 1301`, и `Q - 4*R = 1310` в противном случае =)

2013-03-04 в 23:25 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Видимо, это так... делитель 1 есть всегда... а 2 - только у чётных чисел...

     

Не решается алгебра/высшая математика?.. ПОМОЖЕМ!

главная