2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Последовательность и 2011
Сообщение31.03.2011, 09:55 


02/09/10
76
Целочисленная последовательность (ТМ Xenia1996 :-) ) задана следующей формулой:

$a_{n+1}=3a_n-a_{n-1}, 
a_1=1, a_2=1 $

Найти наименьший член последовательности, кратный 2011.

 Профиль  
                  
 
 Re: Последовательность и 2011
Сообщение31.03.2011, 11:03 
Заслуженный участник


08/04/08
8562
По-моему, таких нет:
$a_n=C_1 \alpha ^{n-1} + C_2 \beta ^{n-1}$
$\alpha = \frac{3+\sqrt{5}}{2}, \beta = \frac{3-\sqrt{5}}{2}, \alpha \beta = 1$
$C_1 = \frac{5-\sqrt{5}}{10}, C_2 = \frac{5+\sqrt{5}}{10}, C_1C_2 = 5^{-1}$
Тогда
$a_n \equiv 0 \pmod p \Leftrightarrow C_1 \alpha ^{2n-2} + C_2 \equiv 0 \pmod p \Leftrightarrow$
$\Leftrightarrow \alpha ^{2n-2} \equiv -C_2C_1^{-1} \equiv -5C_2^2 \pmod p,$
что возможно тогда и только тогда, когда $\left( \frac{-5}{p} \right) = 1$, в то время как
$\left( \frac{-5}{2011} \right) = \left( \frac{-1}{2011} \right) \left( \frac{5}{2011} \right) = -1 \cdot (-1)^{\frac{2011-1}{2} \cdot \frac{5-1}{2}} \left( \frac{2011}{5} \right) = -1$.
И еще забыл сказать, что символ Лежандра мы можем применить потому, что $\alpha \in \mathbb{Z}_p$, поскольку $\left( \frac{5}{2011} \right) =1$.
Проверьте.

(Оффтоп)

уверен, что Xenia1996 знает решение проще или найдет здесь ошибку :-)

 Профиль  
                  
 
 Re: Последовательность и 2011
Сообщение31.03.2011, 12:35 
Заслуженный участник
Аватара пользователя


23/07/08
10910
Crna Gora
Это последовательность Фибоначчи, из которой выброшены элементы с четными индексами.

 Профиль  
                  
 
 Re: Последовательность и 2011
Сообщение31.03.2011, 14:11 
Заслуженный участник
Аватара пользователя


23/07/08
10910
Crna Gora
Последовательность остатков от деления $a_n$ на $2011$ периодическая, период равен $1005$. Нулевой остаток не встречается.

 Профиль  
                  
 
 Re: Последовательность и 2011
Сообщение31.03.2011, 16:10 


02/09/10
76
Sonic86 в сообщении #429429 писал(а):
И еще забыл сказать, что ...

Отсюда подробнее, а то я уж хотел предложить
$\left( \frac{-5}{17} \right) посчитать :-)

svv в сообщении #429503 писал(а):
Последовательность остатков от деления $a_n$ на $2011$ периодическая, период равен $1005$. Нулевой остаток не встречается.
Вы реально проверяли? Респект. А если б я 62011 предложил?

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


18/05/06
13438
с Территории
"Подумаешь, бином Ньютона". Там всё то же самое, только период 3445.

 Профиль  
                  
 
 Re: Последовательность и 2011
Сообщение31.03.2011, 17:50 
Заслуженный участник
Аватара пользователя


23/07/08
10910
Crna Gora
Конечно. Проверяет-то программа. Ну, был бы ещё в 30 раз больший респект (если зависимость линейная).
И ещё интересно. Период состоит из двух зеркально-симметричных частей. Один элемент для обеих частей общий, поэтому период нечетный.
Так что размер "неповторимости" всего 503.

 Профиль  
                  
 
 Re: Последовательность и 2011
Сообщение31.03.2011, 18:59 


02/09/10
76
svv в сообщении #429602 писал(а):
Конечно. Проверяет-то программа.

Я вообще поначалу заподозрил использование A060305 :oops: , но потом понял - без железа никак.
ИСН в сообщении #429563 писал(а):
"Подумаешь, бином Ньютона".

Конечно, надо было сразу 10000002011 дать :-) А то вроде как получается, Sonic86 не по делу старался...

 Профиль  
                  
 
 Re: Последовательность и 2011
Сообщение31.03.2011, 22:03 
Заслуженный участник
Аватара пользователя


23/07/08
10910
Crna Gora
staric писал(а):
А то вроде как получается, Sonic86 не по делу старался...
Нет, ну что Вы... По умолчанию каждое следующее сообщение не отрицает, а дополняет предыдущие. :-)

 Профиль  
                  
 
 Re: Последовательность и 2011
Сообщение01.04.2011, 11:04 


23/01/07
3497
Новосибирск
По-видимому, в рассмотрении можно где-то попытаться использовать формулу $5a^2-4=b^2$, характеризующую элементы последовательности Фибоначчи, имеющие нечетные номера.

 Профиль  
                  
 
 
Сообщение01.04.2011, 16:15 


23/01/07
3497
Новосибирск
Если предположить, что какое-то число из рассматриваемой последовательности $a_n$ кратно $2011$, то $b^2+4=5a^2$ тоже должно делиться на $2011$.
Число, равное сумме двух квадратов, не может иметь делители, отличные от тех, что имеют остаток $1\pmod 4$, к которым $2011$ не относится.

 Профиль  
                  
 
 Re:
Сообщение02.04.2011, 10:21 


02/09/10
76
Батороев в сообщении #429943 писал(а):
Число, равное сумме двух квадратов, не может иметь ...

Это близко к авторскому решению. Можно воспользоваться ф-лой для Фибоначчи $F_{2n+1}=F_{n+1}^2+F_{n}^2$, и "спуститься" (ес-сно, для простых делителей вида 4k+3). Но мне отчего-то больше нравится решение Соника через символы Лагранжа.

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

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



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

Сейчас этот форум просматривают: YandexBot [bot]


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

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