Красивая формула для a^n

[CheOmsk]

Игрался на досуге с альтернативными теориями чисел и получил одну красивую формулу:

$a^n = \frac {x+(2a+2)\cdot y}{a-1}$

Определима для всех целых $a$ и $n\geqslant0$, кроме, естественно, $a=1$.

Также у меня есть алгоритм для вычисления $x$ и $y$ без вычисления $a^n$, при которых $x$ и $y$ всегда будут целыми, кроме четных $a$ (включая ноль) в степени $0$ (в этом случае $y = -\frac{1}{2}$)

Почему же я посчитал ее красивой? А посудите сами:

$2^2 = (4+6 \cdot 0)/1$
$2^3 = (2+6 \cdot 1)/1$
$2^4 = (4+6 \cdot 2)/1$
$2^5 = (2+6 \cdot 5)/1$
$2^6 = (4+6 \cdot 10)/1$

$3^2 = (2+8 \cdot 2)/2$
$3^3 = (6+8 \cdot 6)/2$
$3^4 = (2+8 \cdot 20)/2$
$3^5 = (6+8 \cdot 60)/2$
$3^6 = (2+8 \cdot 182)/2$

$4^2 = (8+10 \cdot 4)/3$
$4^3 = (2+10 \cdot 19)/3$
$4^4 = (8+10 \cdot 76)/3$
$4^5 = (2+10 \cdot 307)/3$
$4^6 = (8+10 \cdot 1228)/3$

$5^2 = (4+12 \cdot 8)/4$
$5^3 = (8+12 \cdot 41)/4$
$5^4 = (4+12 \cdot 208)/4$
$5^5 = (8+12 \cdot 1041)/4$
$5^6 = (4+12 \cdot 5208)/4$

Кроме того, если мы возьмем ряд чисел, явно прослеживающийся для $2^n$: $\lbrace 0, 1, 2, 5, 10... \rbrace$, то это окажется A000975

Вопроса, собственно, два:

1. Есть ли уже что-то подобное?
2. Есть ли в этом хоть какой-нибудь смысл?

[arseniiv]

Да уж, коль скоро есть хотя бы одно представление, $y$ можно безбоязненно увеличивать и уменьшать, компенсируя это изменениями $x$. А представление c $y=0$ всегда будет. Смысл «разложения» остаётся загадкой.

Так можно нагенерировать кучу уравнений вида

$$P(a) = \frac{x + yQ(a)}{R(a)}$$

относительно $(x,y)$, у которых всегда есть бесконечное число целых решений, если $a\in\mathbb Z$ и $P,Q,R\in\mathbb Z[a]$ и $R\not\equiv0$ (да и вообще знаменатель тут только для большего сходства, так-то он не нужен).

[CheOmsk]

arseniiv, да, я прекрасно понимаю о чем вы говорите и практически полностью с вами согласен.

Нагенерировать кучу уравнений-то мы сможем. Но сможем ли мы их алгоритмизировать для подобного случая $a^n$?

Смысл (кроме как повесить на стену рядом с картиной какого-нибудь художника, чтобы каждый день восхищаться красотой математики ) для меня пока тоже остается загадкой. Собственно, в основном, для ответа на вопрос "есть ли в этом хоть какой-нибудь смысл?" я и создал эту тему.

[ex-math]

Ну с $x$ понятно, это $(-1)^{n+1}\cdot2(\mathrm{mod}\,2a+2)$. А как $y$ "алгоритмизируется"?

[CheOmsk]

ex-math в сообщении #977015 писал(а):

Ну с $x$ понятно, это $(-1)^{n+1}\cdot2(\mathrm{mod}\,2a+2)$. А как $y$ "алгоритмизируется"?

Хм, разве при четных $n$ у вас не получится отрицательный $x$?

$y$ вычисляется заполнением ряда, подобного A000975. Там довольно простой алгоритм... Но я пока не нашел формулу для вычисления n-ного значения этого ряда, но могу вычислить n-ное значение зная значение предыдущего. Поэтому, приходится заполнять этот ряд с самого начала до нужного значения. После чего, опять же, возникает вопрос в смысле всего этого, так как вычислительные мощности для этого требуются большие, чем для простого вычисления значения $a^n$

[ex-math]

Имеется в виду наименьший неотрицательный вычет, т.е. $2a$ для четных и $2$ для нечетных.

Если для $y$ у Вас рекуррентное соотношение, то это не лучше, чем последовательное умножение $a$ на себя.

[CheOmsk]

ex-math, не совсем. Для нечетных $a$ по другому ($a-1$ для четных $n$ и $a+3$ для нечетных $n$)

Рекуррентное Да, я понимаю, что это не лучше, чем последовательное умножение $a$ на себя. Исходя из этого, вы считаете, что и общий смысл всего этого абсолютно нулевой?

[ex-math]

Да, верно. Модуль надо брать $a+1$ и вычет четный, то есть для нечетных $a$ как Вы сказали, а для четных как я написал.

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

[grizzly]

Общий член для $\lbrace 0, 1, 2, 5, 10... \rbrace$ есть у Слоана:
$y_2(n) = \lceil (2\cdot (2^n-1)/3) \rceil $.
Для тройки почти полная аналогия:
$y_3(n-1) = \lceil (3\cdot (3^n-1)/4) \rceil $.

Дальше такой аналогии нет, хотя наверняка общие члены для $y$ можно повыписывать подобным образом и, скорее всего, можно как-то обобщить все их одной формулой (взяв более подходящую общую формулу для $x$), только пользы от этого и правда никакой не будет.

[CheOmsk]

ex-math, понятно, спасибо!

grizzly, вот через $a^n$ как раз я и сам могу выразить с помощью формулы из первого поста Правда у меня будет для каждого $a$ по две разных формулы (для четных и нечетных $n$), но это не столь важно. Вот если бы получилось выразить в более простом виде, без $a^n$, - это было бы уже куда интересней, так как могло бы привести к получению вычислительного преимущества в сравнении с обычным последовательным умножением $a$ на себя.

И, кстати, если принять во внимание, что исходя из формулы в первом посте:

$2^1 = (2 + 6 \cdot 0)/1$

то на самом деле ряд в этом случае выглядит, как $\lbrace 0, 0, 1, 2, 5, 10...\rbrace$, что чуть более удобно в данном конкретном случае, так как $y_n$ будет коэффициентом конкретно для $2^n$.
...для тройки: $\lbrace 0, 2, 6, 20, 60, 182...\rbrace$
...а дальше уже интересней, так как уже не будет начинаться с нуля. Для четверки: $\lbrace 1, 4, 19, 76, 307, 1228...\rbrace$
...для пятерки: $\lbrace 1, 8, 41, 208, 1041, 5208...\rbrace$

Извиняюсь, что не указал это сразу, копировал из черновиков.

[grizzly]

CheOmsk в сообщении #977120 писал(а):

вот через $a^n$ как раз я и сам могу выразить с помощью формулы из первого поста

Ну это с какой стороны посмотреть :)
Дело в том, что последовательность для $y_2(n)$ уже была кому-то интересна, она возникает в каких-то самых разных задачах, и кто-то не поленился для неё общий член выписать на страничке Слоана.
Теперь вот попалась Вам она с другой стороны, просто в игрушках с цифрами. А я предлагаю Вам посмотреть дальше с этой стороны: поискать Вашу формулу общего члена для $y_2(n)$ через $2^n$ (говорите же, что можете) -- вдруг она будут лучше / удобнее; посмотреть, нельзя ли получить аналогичные формулы для $y_a(n)$ в $a^n$ и -- самое главное -- поискать, не возникнут ли эти $y_a(n)$ в каких-то задачах подобных или даже обобщающих те, для $y_2(n)$.
Это уже будет какая-то исследовательская задача и вряд ли Вам кто-то сразу уверено скажет, что она настолько же бесполезная и бесперспективная, как попытка оптимизировать расчёт степеней целых чисел.

[arseniiv]

(Оффтоп)

grizzly в сообщении #977152 писал(а):

на страничке Слоана

Ну, это уже давно не страничка одного Слоана. Хотя founded by.

[CheOmsk]

grizzly, действительно! Спасибо, я как-то и не догадался с такого ракурса взглянуть.
К сожалению, с английским у меня очень туго, но давайте попробуем. (С математикой тоже далеко не все идеально, буду разбираться по ходу с не совсем понятными вещами, если что - поправляйте, пожалуйста)

Если я правильно понимаю, то для A000975 формула общего члена считается, как:

$y_2(n) = ceiling(2 \cdot (2^n-1)/3)$

где CEILING(X) - возвращает наименьшее целое число, не меньшее, чем X? Тогда:

$y_2(0) = ceiling(0) = 0$
$y_2(1) = ceiling(2/3) = 1$
$y_2(2) = ceiling(2) = 2$
$y_2(3) = ceiling(14/3) = 5$
$y_2(4) = ceiling(10) = 10$
$y_2(5) = ceiling(62/3) = 21$

Работает. Но ниже есть еще одна формула для четных и нечетных членов:

Цитата:

$y_2(n) = 2 \cdot (2^n - 1)/3$, for even n; $y_2(n) = (2^{n+1} - 1)/3$, for odd n. - Hieronymus Fischer, Nov 22 2012

(там для нечетных $n$ через знак равенства идет еще какая-то длинная конструкция, практический смысл которой я не понял)

$y_2(0) = 2 \cdot (2^0 - 1)/3 = 0$
$y_2(1) = (2^{1+1} - 1)/3 = 1$
$y_2(2) = 2 \cdot (2^2 - 1)/3 = 2$
$y_2(3) = (2^{3+1} - 1)/3 = 5$
$y_2(4) = 2 \cdot (2^4 - 1)/3 = 10$
$y_2(5) = (2^{5+1} - 1)/3 = 21$

Работает.

Только я не понял, почему ноль считается нулевым членом последовательности, это всегда так принято? (простите, если вопрос уровня дошкольной математики. А то я как-то всегда думал, что ноль должен быть первым членом )

Теперь о том, почему я заинтересовался именно формулами для четных и нечетных членов. Из формулы в заглавном посте я не придумал, как выразить формулу общего члена (слишком там все завязано на четность/нечетность). Но зато с формулами для четных и нечетных членов получилось все просто прекрасно:

Для четных $n$: $y_2(n) = (2^{n+1} - 2)/3$
Для нечетных $n$: $y_2(n) = (2^{n+1} - 1)/3$

Формула для нечетных членов совпадает с формулой от Hieronymus Fischer, привидение же к подобному виду формулы для четных членов нам поможет в дальнейшем для общего случая $a^n$.

Проверяем:

$y_2(0) = (2^{0+1} - 2)/3 = 0$
$y_2(1) = (2^{1+1} - 1)/3 = 1$
$y_2(2) = (2^{2+1} - 2)/3 = 2$
$y_2(3) = (2^{3+1} - 1)/3 = 5$
$y_2(4) = (2^{4+1} - 2)/3 = 10$
$y_2(5) = (2^{5+1} - 1)/3 = 21$

Работает. И выглядит более красиво, хоть и чуть менее оптимизировано, чем у Hieronymus Fischer

Теперь выводим общий случай для $a^n$:

Для четных $a$ и четных $n$: $y_a(n) = ((a-1)(a^{n+1}) - 2)/(2a+2) $
Для четных $a$ и нечетных $n$: $y_a(n) = ((a-1)(a^{n+1}) - 2a)/(2a+2) $

Для нечетных $a$ и четных $n$: $y_a(n) = ((a-1)(a^{n+1}) - (a+3))/(2a+2) $
Для нечетных $a$ и нечетных $n$: $y_a(n) = ((a-1)(a^{n+1}) - (a-1))/(2a+2) $

Проверяем, не допустили ли мы где ошибку:

$y_4(0) = (3 \cdot 4^{0+1} - 2)/10 = 1$
$y_4(1) = (3 \cdot 4^{1+1} - 8)/10 = 4$
$y_4(2) = (3 \cdot 4^{2+1} - 2)/10 = 19$
$y_4(3) = (3 \cdot 4^{3+1} - 8)/10 = 76$

Совпадает с рядом для четверки: $\lbrace 1, 4, 19, 76, 307, 1228... \rbrace$

$y_5(0) = (4 \cdot 5^{0+1} - 8)/12 = 1$
$y_5(1) = (4 \cdot 5^{1+1} - 4)/12 = 8$
$y_5(2) = (4 \cdot 5^{2+1} - 8)/12 = 41$
$y_5(3) = (4 \cdot 5^{3+1} - 4)/12 = 208$

Совпадает с рядом для пятерки: $\lbrace 1, 8, 41, 208, 1041, 5208... \rbrace$

Правда, для общего случая, ряд для двойки тогда все-же будет иметь вид: $\lbrace 0, 0, 1, 2, 5, 10... \rbrace$

Мы, конечно, чтобы отбросить первый член последовательности, можем привести формулы к виду:
Для четных $a$ и четных $n$: $y_a(n) = ((a-1)(a^{n+2}) - 2a)/(2a+2) $ и т.д.

Но что-то мне подсказывает, что для общего случая вышеописанные формулы более каноничны. (Но, на всякий случай, будем держать это в голове)

Цитата:

и -- самое главное -- поискать, не возникнут ли эти $y_a(n)$ в каких-то задачах подобных или даже обобщающих те, для $y_2(n)$.

А вот с этим у меня небольшой тупик. Так как моего знания английского языка не достаточно, чтобы все основательно прочитать про A000975, а вот подобную информацию на русском, я так понимаю, найти практически нереально. Надеюсь, кто-нибудь из вас натолкнет меня на мысль, как выйти из этого положения, пока я отсыпаюсь и пытаюсь найти формулу общего члена для $a^n$ наподобие вышеописанной $y_2(n) = ceiling(2 \cdot (2^n-1)/3)$. Буду вам за это весьма благодарен.

[grizzly]

CheOmsk в сообщении #977175 писал(а):

А вот с этим у меня небольшой тупик. Так как моего знания английского языка не достаточно, чтобы все основательно прочитать про A000975, а вот подобную информацию на русском, я так понимаю, найти практически нереально. Надеюсь, кто-нибудь из вас натолкнет меня на мысль, как выйти из этого положения

Да, с информацией на русском будет посложнее. Хотя, поверьте, информационная насыщенность /сложность этой странички значительно превышает "трудности перевода". Но в любом случае заниматься подобными исследовательскими задачами "методом тыка" на незнакомом языке будет очень сложно. Потому как путь, предложенный мной, -- это сунуться в сотни разных мест, дойти в каждом из них до тупика, потом попробовать ещё раз. Не очень оптимальный путь, но он хотя бы расширит кругозор и не даст зациклиться на одной задаче (что даже для здоровья может быть не особенно полезно).

Но хотя бы в качестве примера приведу (переведу) для Вас упомянутую там аналогию между последовательностью $y_2(n)$ и треугольными числами: 0, 1, 3, 6, 10... Треугольные числа обладают следующим простым свойством: это минимальная из последовательностей, в которой расстояние от $n$-го до $(n-1)$-го числа равно $n$. А $y_2(n)$, записанные в двоичном виде, обладает тем же свойством в метрике Хэмминга (погуглите определение на Вики и проверьте на первых числах): $y_2(n)$ является минимальным из тех, для которых расстояние в этой метрике $y_2(n-1)$ будет равно $n$.

И Ваш вопрос про нулевой член последовательности -- зачастую принято начинать с нулевого, а не с первого члена (и началом натурального ряда считать 0). Привыкайте.

[CheOmsk]

Да, как раз информационная насыщенность/сложность и есть вторая половина проблемы. Так как я не имею высшего математического образования, и многие термины встречаются мне впервые.
Но ничего страшного, попробуем разобраться.

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

Спасибо вам, grizzly, за помощь и ценные замечания.