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

[wpoms.]

Пусть натуральное число `n` имеет ровно `120` натуральных делителей (включая `1` и `n`). Для каждого делителя числа `n`, обозначим его `d`, `q` - неполное частное и `r` - остаток от деления `4*n - 3` на `d`. Пусть `Q` - сумма всех неполных частных `q` и `R` - сумма остатков `r` от деления `4*n - 3` на `d`. Найдите `Q - 4*R`, в ответе укажите все возможные значения. Пояснение: Пусть даны два натуральных чисел `a` и `b`, тогда `q` является неполным частным и `r` остатком от деления `a` на `b`, если `q` и `r` целые числа, `a = q*b + r`, `0 <= r < b`. Например, если `a = 4261`, `b = 7`, то `4261 = 7 * 608 +5`, где `q = 608` - неполное частное и `r = 5` - остаток.

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

Comments

[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)`.

[All_ex]

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`... Ну, как-то так... или я чего-то недопонял?...

[Adjirranirr]

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

[All_ex]

Несмотря на то, что немного обогатился знаниями про формулы обращения Мёбиуса , но ошибки найти не могу... про это сразу в голову ничего не приходит...

Если решать без этих формул, то получил вот что...
Пусть `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`

Вооот.... ...

[All_ex]

Правда тут подумалось, что остаток, вычисляемый по формуле `p_1^{0} * p_2^{0} * ... * p_m^{0} - 3` (а кроме, того есть ещё `p_1 < 2`...) будет отрицательным... то есть ответ надо подшаманивать (но уже лень)... Видимо не зря в условии намекали про все варианты ответа...

[Adjirranirr]

Простенький код для maple:

divp := proc (n::integer, m::integer)::integer; local s::integer; s := `mod`(n, m); s := n-s; s := s/m; return s end proc:    

R := proc (n::integer)::integer; local A::integer, t::integer, i::integer; A := n^119; A := 4*A-3; t := 0; for i from 0 to 119 do t := t+modp(A, n^i) end do; return t end proc:   

Q := proc (n::integer)::integer; local A::integer, t::integer, i::integer; A := n^119; A := 4*A-3; t := 0; for i from 0 to 119 do t := t+divp(A, n^i) end do; return t end proc:    

P(n):=Q(n)-4*R(n):    

for i from 2 to 83 do if isprime(i) then printf("%d: %d\n", i, P(i)) end if end do;

Вывод:

2: 1301
3: 1310
5: 1310
7: 1310
11: 1310
13: 1310
17: 1310
19: 1310
23: 1310
29: 1310
31: 1310
37: 1310
41: 1310
43: 1310
47: 1310
53: 1310
59: 1310
61: 1310
67: 1310
71: 1310
73: 1310
79: 1310
83: 1310

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

[All_ex]

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

[Adjirranirr]

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

x := Vector[row](5, {(1) = 3, (2) = 13, (3) = 5, (4) = 7, (5) = 11});
y := Vector[row](5, {(1) = 1, (2) = 1, (3) = 1, (4) = 2, (5) = 4});
i := Vector[row](5, {(1) = 0, (2) = 0, (3) = 0, (4) = 0, (5) = 0});
Q := 0;
R := 0;
n := x[1]^y[1]*x[2]^y[2]*x[3]^y[3]*x[4]^y[4]*x[5]^y[5];
A := 4*n-3;
for i[1] from 0 to y[1] do 
  for i[2] from 0 to y[2] do 
    for i[3] from 0 to y[3] do
      for i[4] from 0 to y[4] do 
        for i[5] from 0 to y[5] do
          Q := Q+divp(A, x[1]^i[1]*x[2]^i[2]*x[3]^i[3]*x[4]^i[4]*x[5]^i[5]);
          R := R+modp(A, x[1]^i[1]*x[2]^i[2]*x[3]^i[3]*x[4]^i[4]*x[5]^i[5]) 
        end do 
      end do 
    end do 
  end do 
end do; 
P := Q-4*R

[All_ex]

Видимо, это так... делитель 1 есть всегда... а 2 - только у чётных чисел...