Представление числа в виде х+у+х*у

[Zak]

Числа вида 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

[worm2]

Zak писал(а):

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

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

[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. Переношу в Помогите решить/разобраться. Ничего олимпиадного тут нет.

[Zak]

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

[maxal]

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$.

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