Регистрация    Вход    Форум    Поиск    FAQ   alexlarin.net

Список форумов » Интересные задачки

Текущее время: 11 окт 2024, 02:22
Часовой пояс: UTC + 3 часа
Сообщения без ответов | Активные темы
 



 Страница 2 из 2 [ Сообщений: 15 ] На страницу Пред.  1, 2
Начать новую тему">
Ответить

Задача из серии <The Putnam Archive>

Автор Сообщение
OlG
 Заголовок сообщения: Re: Интересная задача с произведением логарифмов.
 Сообщение Добавлено: 21 июл 2019, 17:18 
Не в сети
Аватар пользователя

Зарегистрирован: 09 апр 2011, 14:49
Сообщений: 6868
Откуда: Москва
hpbhpb писал(а):
Может, OlG поможет.

Я не собирался оформлять решение (время и etc). Очень кратко:
Подробности:
1.

а) `{(x^m=1), (m in NN):} quad iff quad {(x=e^((2*pi*i*b)/m)), (b=1..m),(m in NN):} quad .`

б) `{(x^m-1=prod_{b=1}^m (x-e^((2*pi*i*b)/m))), (m in NN):} quad => quad {(m=2k-1), (k in NN), ((-1)^m-1=prod_(b=1)^m (-1-e^((2*pi*i*b)/m))) :} quad, quad {(m=2k-1), (k in NN), (prod_(b=1)^m (1+e^((2*pi*i*b)/m))=2) :} quad .`

2.

а) `n=2l-1, quad l in NN, quad d=gcd(a, quad n), quad m=n/d.`

б) `prod_(b=1)^n (1+e^((2*pi*i*a*b)/n))=(prod_(b=1)^m (1+e^((2*pi*i*b)/m)))^d=2^(gcd(a, quad n)).`

3.

а) `2015=3*13*31, quad x=3, quad y=13, quad y=31.`

б) `log_(2)(prod_(a=1)^2015 prod_(b=1)^2015 (1+e^((2*pi*i*a*b)/(2015))))=sum_(a=1)^2015(log_(2)( prod_(b=1)^2015 (1+e^((2*pi*i*a*b)/(2015)))))=sum_(a=1)^2015(gcd(a, quad 2015))=`

`qquad=1*(x-1)(y-1)(z-1)+x*(y-1)(z-1)+y*(x-1)(z-1)+z*(x-1)(y-1)+xy*(z-1)+xz*(y-1)+yz*(x-1)+xyz*1=`

`qquad =(2x-1)(2y-1)(2z-1)=13725.`

_________________
Никуда не тороплюсь!
Вернуться наверх 
hpbhpb
 Заголовок сообщения: Re: Интересная задача с произведением логарифмов.
 Сообщение Добавлено: 21 июл 2019, 22:22 
Не в сети
Аватар пользователя

Зарегистрирован: 18 ноя 2015, 07:49
Сообщений: 2290
Откуда: Ставрополь
OlG писал(а):
hpbhpb писал(а):
Может, OlG поможет.

Я не собирался оформлять решение (время и etc). Очень кратко:
Подробности:
1.

а) `{(x^m=1), (m in NN):} quad iff quad {(x=e^((2*pi*i*b)/m)), (b=1..m),(m in NN):} quad .`

б) `{(x^m-1=prod_{b=1}^m (x-e^((2*pi*i*b)/m))), (m in NN):} quad => quad {(m=2k-1), (k in NN), ((-1)^m-1=prod_(b=1)^m (-1-e^((2*pi*i*b)/m))) :} quad, quad {(m=2k-1), (k in NN), (prod_(b=1)^m (1+e^((2*pi*i*b)/m))=2) :} quad .`

2.

а) `n=2l-1, quad l in NN, quad d=gcd(a, quad n), quad m=n/d.`

б) `prod_(b=1)^n (1+e^((2*pi*i*a*b)/n))=(prod_(b=1)^m (1+e^((2*pi*i*b)/m)))^d=2^(gcd(a, quad n)).`

3.

а) `2015=3*13*31, quad x=3, quad y=13, quad y=31.`

б) `log_(2)(prod_(a=1)^2015 prod_(b=1)^2015 (1+e^((2*pi*i*a*b)/(2015))))=sum_(a=1)^2015(log_(2)( prod_(b=1)^2015 (1+e^((2*pi*i*a*b)/(2015)))))=sum_(a=1)^2015(gcd(a, quad 2015))=`

`qquad=1*(x-1)(y-1)(z-1)+x*(y-1)(z-1)+y*(x-1)(z-1)+z*(x-1)(y-1)+xy*(z-1)+xz*(y-1)+yz*(x-1)+xyz*1=`

`qquad =(2x-1)(2y-1)(2z-1)=13725.`


Спасибо, OlG!
Вернуться наверх 
ar54
 Заголовок сообщения: Re: Задача из серии <The Putnam Archive>
 Сообщение Добавлено: 06 окт 2019, 20:59 
Не в сети

Зарегистрирован: 17 дек 2015, 18:58
Сообщений: 897
Уважаемый OIG!
В своем кратком решении Вы привели простую формулу для вычисления ответа: если `N` является произведением `n=3`-х простых чисел (`N=p_1*p_2*p_3)`, то ответ равен `(2p_1-1)*(2p_2-1)*(2p_3-1)`.
Непосредственно проверяется, что при `n=1` ответ будет `(2p_1-1)`, при `n=2` -- `(2p_1-1)*(2p_2-1)`.
Напрашивается общая формула: если `N=prod_(k=1)^n p_k`, то ответ `prod_(k=1)^n (2p_k-1)`.
Так ли это? Если так, то должно существовать изящное доказательство (метод мат. индукции?)
Возможно, существуют простые формулы и для общего представления `N=prod_(k=1)^n p_k^(m_k)`?
Вернуться наверх 
nnosipov
 Заголовок сообщения: Re: Задача из серии <The Putnam Archive>
 Сообщение Добавлено: 07 окт 2019, 17:25 
Не в сети

Зарегистрирован: 14 фев 2012, 19:11
Сообщений: 468
ar54 писал(а):
Возможно, существуют простые формулы и для общего представления `N=prod_(k=1)^n p_k^(m_k)`?

Да, существуют. Сначала можно получить равенство $\sum_{a=1}^N \gcd{(a,N)}=N\sum_{d \mid N}\frac{\varphi(d)}{d}$, а затем воспользоваться мультипликативностью последнего выражения как функции $N$ (здесь $\varphi$, как обычно, обозначает функцию Эйлера). Вот формула и получится.
Вернуться наверх 
ar54
 Заголовок сообщения: Re: Задача из серии <The Putnam Archive>
 Сообщение Добавлено: 07 окт 2019, 20:24 
Не в сети

Зарегистрирован: 17 дек 2015, 18:58
Сообщений: 897
nnosipov писал(а):
ar54 писал(а):
Возможно, существуют простые формулы и для общего представления `N=prod_(k=1)^n p_k^(m_k)`?

Да, существуют. Сначала можно получить равенство $\sum_{a=1}^N \gcd{(a,N)}=N\sum_{d \mid N}\frac{\varphi(d)}{d}$, а затем воспользоваться мультипликативностью последнего выражения как функции $N$ (здесь $\varphi$, как обычно, обозначает функцию Эйлера). Вот формула и получится.

Спасибо большое, уважаемый nnosipov, за информацию.
Вернуться наверх 
Показать сообщения за:  Сортировать по:  
 
 Страница 2 из 2 [ Сообщений: 15 ] На страницу Пред.  1, 2

Список форумов » Просмотр темы - Задача из серии <The Putnam Archive>

Текущее время: 11 окт 2024, 02:22 | Часовой пояс: UTC + 3 часа
Удалить cookies форума | Наша команда | Вернуться наверх

Кто сейчас на форуме

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

 
 

 
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти: