Чубариков

stm29576666

Народ!
Срочно.Кто может решить:
1. (Сумма по n<=xфи(n)*фи(n)*фи(n) / n)=? при x->бесконечности
фи-это число чисел до n взаимно простых с n
2.(Сумма по n<=xтау(n при x->бесконечности
тау-это число делителей n
Пиво ставлю (к 739Б)

XTC-XTC

решение второй ты можешь найти в сети.
кажется, я видел... но где - не помню.. либо в книге электронной, либо на скане листочков.

stm29576666

А что за книга электронная?

976evil

Над первой надо немного подумать, сходу сложно сказать ответ.
Вторая - халява. Смотри тут: http://lorien.local/pub/docs/botva/TCH/chubarikov.ps
Если будет время сегодня, напишу туда же решения других задач, упоминавшихся тут в форуме.

phe13

Народ, может у кого-нить уже были задачки:
1. Tau(n)<=Tau( 2^n-1)
2. sum по n<x (Tau^3(n)/n) при x->беск-ти
Подскадите, плиз, как решать или где можно посмотреть теорию..

margo11

Ну первая простая. Пусть d | n тогда n = d*k, значит, 2^n - 1 = 2^{d*k} - 1 = (2^d)^k - 1 = (2^d - 1)*(1 + 2^d + 2^{2d} + ... + 2^{(k-1)d}). Видим, что каждому делителю n соответствует делитель 2^n - 1, значит у второго числа делителей не меньше.

phe13

Сенкс, а можешь еще что-нить про вторую сказать?

Sanych

Впрочем, там написано срочно. Значит это наверно уже зря.
Ну да ничего страшного. Положу в архив.
Первая задача вроде сводится здесь к
n^3/3 \prod_p (1-3/p^2+3/p^3-1/p^4
то есть асимптотически cn^3, где эту самую c совершенно непонятно, как считать. Так что имхо в таком виде и оставить.
То есть надо показать, что с точностью до o(n^3) наше выражение равно произведению. Для этого мы произведение заменяем на сумму по той части слагаемых, которые получаются при представлении \phi(n)^3/n. А с другой стороны, группируем n по тому, на какие простые они делятся и заменяем \sum_{n делится на w}n^2 ~ n^3/(3w)
Делается это с помощью чего-то вроде формулы включений-исключений аналогично рассуждению для \phi(n)/n, только мучаться подольше придётся. Сделав это, уже можно радоваться. Ссылка на \phi(n)/n:
[offtopic]
В общем, наверно надо было мне раньше это понять.
А сейчас так хочется спать, и голова не работает. Но вроде всё сошлось с той асимптотикой, что считает программа.
Удачи!
[/offtopic]

e_movo

Ну ты вообще супер!
я бы тебе медаль дала за заслуги перед факультетом-)
надо тебе 5 поставить
Оставить комментарий
Имя или ник:
Комментарий: