2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Красивая формула для a^n
Сообщение11.02.2015, 20:20 


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

$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. Есть ли в этом хоть какой-нибудь смысл? :D

 Профиль  
                  
 
 Re: Красивая формула для a^n
Сообщение11.02.2015, 21:34 
Заслуженный участник


27/04/09
28128
Да уж, коль скоро есть хотя бы одно представление, $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$ (да и вообще знаменатель тут только для большего сходства, так-то он не нужен).

 Профиль  
                  
 
 Re: Красивая формула для a^n
Сообщение11.02.2015, 22:00 


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

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

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

 Профиль  
                  
 
 Re: Красивая формула для a^n
Сообщение11.02.2015, 22:05 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Красивая формула для a^n
Сообщение11.02.2015, 22:27 


10/02/15
12
ex-math в сообщении #977015 писал(а):
Ну с $x$ понятно, это $(-1)^{n+1}\cdot2(\mathrm{mod}\,2a+2)$. А как $y$ "алгоритмизируется"?

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

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

 Профиль  
                  
 
 Re: Красивая формула для a^n
Сообщение11.02.2015, 22:30 
Заслуженный участник
Аватара пользователя


24/02/12
1842
Москва
Имеется в виду наименьший неотрицательный вычет, т.е. $2a$ для четных и $2$ для нечетных.

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

 Профиль  
                  
 
 Re: Красивая формула для a^n
Сообщение11.02.2015, 22:40 


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

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

 Профиль  
                  
 
 Re: Красивая формула для a^n
Сообщение11.02.2015, 23:03 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Красивая формула для a^n
Сообщение11.02.2015, 23:35 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Общий член для $\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$), только пользы от этого и правда никакой не будет.

 Профиль  
                  
 
 Re: Красивая формула для a^n
Сообщение12.02.2015, 01:48 


10/02/15
12
ex-math, понятно, спасибо!

grizzly, вот через $a^n$ как раз я и сам могу выразить с помощью формулы из первого поста :D Правда у меня будет для каждого $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$

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

 Профиль  
                  
 
 Re: Красивая формула для a^n
Сообщение12.02.2015, 03:27 
Заслуженный участник
Аватара пользователя


09/09/14
6328
CheOmsk в сообщении #977120 писал(а):
вот через $a^n$ как раз я и сам могу выразить с помощью формулы из первого поста

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

 Профиль  
                  
 
 Re: Красивая формула для a^n
Сообщение12.02.2015, 03:30 
Заслуженный участник


27/04/09
28128

(Оффтоп)

grizzly в сообщении #977152 писал(а):
на страничке Слоана
Ну, это уже давно не страничка одного Слоана. :-) Хотя founded by.

 Профиль  
                  
 
 Re: Красивая формула для a^n
Сообщение12.02.2015, 07:35 


10/02/15
12
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$

Работает.

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

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

Для четных $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 :D

Теперь выводим общий случай для $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)$. Буду вам за это весьма благодарен.

 Профиль  
                  
 
 Re: Красивая формула для a^n
Сообщение12.02.2015, 12:07 
Заслуженный участник
Аватара пользователя


09/09/14
6328
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). Привыкайте.

 Профиль  
                  
 
 Re: Красивая формула для a^n
Сообщение12.02.2015, 19:43 


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

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

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

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

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



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

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


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

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