2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Представление числа в виде х+у+х*у
Сообщение28.01.2008, 19:50 


28/01/08
3
Числа вида 2^n (при n>16), по-видимому,
всегда можно представить в виде х+у+х*у
(если 2^n+1 не простое число Ферма).

А есть ли общий метод нахождения (минимального) х для произвольных степеней n?

Более частный вопрос: для n=32,64,128,...
минимальные значения х особенно велики.

Так ли это, и почему?
Thanks, Zak

Ещё вопрос вдогонку:
Число к разных представлений 2^n (при n>16), в виде х+у+х*у (x<y), по-видимому,
всегда нечетно, cм. несколько первых {n,k}:
{17,1},{18,7},{19,1},{20,1},{21,5},{22,3},{23,1},{24,3},{25,7},{26,7},{27,9},
{28,1},{29,3},{30,23},{31,1},{32,1},{33,11},{34,7},{35,15},{36,7},{37,3},
{38,7},{39,5},{40,1},{41,3},{42,31},{43,1},{44,3},{45,31},{46,15},{47,3},
{48,3},{49,3},{50,31},{51,23},{52,3},{53,3},{54,31},{55,23}}.

Так ли это, и почему?
Thanks, Zak


Разбил слишком длинную строку на части, чтобы было удобнее читать.
Jnrty

 Профиль  
                  
 
 
Сообщение28.01.2008, 20:33 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
Zak писал(а):
А есть ли общий метод нахождения (минимального) х для произвольных степеней n?

Конечно! Раскладываете $2^n+1$ на множители и выбираете из них минимальный :D

 Профиль  
                  
 
 Re: Представление числа в виде х+у+х*у
Сообщение28.01.2008, 21:25 
Модератор
Аватара пользователя


11/01/06
5660
Zak писал(а):
Числа вида 2^n (при n>16), по-видимому,
всегда можно представить в виде х+у+х*у
(если 2^n+1 не простое число Ферма).

А есть ли общий метод нахождения (минимального) х для произвольных степеней n?

Как уже справедливо заметил worm2, достаточно прибавить 1 и заметить, что $x+y+xy+1 = (x+1)(y+1)$. Таким образом, задача сводится к факторизации $2^n+1$. В случае, когда $n$ имеет нечетные делители это упрощается в виду применимости теоремы Безу: $2^{km}+1$ делится на $2^m+1$ для любого нечетного $k\geq 3$ и любого целого $m\geq 1$. Здесь также можно воспользоваться Aurifeuillean Factorization и проектом Cunningham, где числа $2^n+1$ уже факторизованы для многих маленьких $n$.
Zak писал(а):
Более частный вопрос: для n=32,64,128,...
минимальные значения х особенно велики.

Потому что в этом случае возникает известная (сложная) задача нахождения делителей чисел Ферма.

P.S. Переношу в Помогите решить/разобраться. Ничего олимпиадного тут нет.

 Профиль  
                  
 
 Re: Представление числа в виде х+у+х*у
Сообщение28.01.2008, 22:26 


28/01/08
3
maxal писал(а):
Zak писал(а):
Числа вида 2^n (при n>16), по-видимому,
всегда можно представить в виде х+у+х*у
(если 2^n+1 не простое число Ферма).

А есть ли общий метод нахождения (минимального) х для произвольных степеней n?

Как уже справедливо заметил worm2, достаточно прибавить 1 и заметить, что $x+y+xy+1 = (x+1)(y+1)$. Таким образом, задача сводится к факторизации $2^n+1$. В случае, когда $n$ имеет нечетные делители это упрощается в виду применимости теоремы Безу: $2^{km}+1$ делится на $2^m+1$ для любого нечетного $k\geq 3$ и любого целого $m\geq 1$. Здесь также можно воспользоваться Aurifeuillean Factorization и проектом Cunningham, где числа $2^n+1$ уже факторизованы для многих маленьких $n$.
Zak писал(а):
Более частный вопрос: для n=32,64,128,...
минимальные значения х особенно велики.

Потому что в этом случае возникает известная (сложная) задача нахождения делителей чисел Ферма.

P.S. Переношу в Помогите решить/разобраться. Ничего олимпиадного тут нет.


OK,
thank you all very much!

Остался вопрос о нечетном числе представлений -
есть ли (и) этому объяснение?
Zak

 Профиль  
                  
 
 Re: Представление числа в виде х+у+х*у
Сообщение29.01.2008, 01:54 
Модератор
Аватара пользователя


11/01/06
5660
Zak писал(а):
Число к разных представлений 2^n (при n>16), в виде х+у+х*у (x<y), по-видимому,
всегда нечетно, cм. несколько первых {n,k}:
{17,1}, {18,7}, {19,1}, {20,1}, {21,5}, {22,3}, {23,1}, {24,3}, {25,7}, {26,7}, {27,9}, {28,1}, {29,3}, {30,23}, {31,1}, {32,1}, {33,11}, {34,7}, {35,15}, {36,7}, {37,3}, {38,7}, {39,5}, {40,1}, {41,3}, {42,31}, {43,1}, {44,3}, {45,31}, {46,15}, {47,3}, {48,3}, {49,3}, {50,31}, {51,23}, {52,3}, {53,3}, {54,31}, {55,23}}.

Ну, во-первых, вы по-видимому не учитываете тривиальное представление:
0 + 2^n + 0*2^n
С его учетом, количество различных представлений равно ополовиненному числу делителей $d(2^n+1)/2$ (ну или $d(2^n+1)/2-1$, если не учитывать тривиальное представление). Тогда ваше утверждение о нечетности числа представление равносильно утверждение о том, что $4|d(2^n+1)$.
Нетрудно видеть, что для $n>3$ это не так, только если $2^n+1=pq^2,$ где $p$ - простое. В частности, ваше предположение окажется неверным, например, если найдется новой простое число Ферма. Но на самом деле похоже, что этим все и ограничивается, и из $2^n+1=pq^2,$ где $p$ - простое и $n>10$, следует, что $q=1$.

Разбил слишком длинную строку на части, чтобы было удобнее читать. // нг

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

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


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group