Положим, что у меня имеются значения двух первых членов последовательности и формула, рекуррентно задающая все последующие члены. Количество членов не превышает 10^1000000. Как найти последнюю цифру некоторого n-го члена?

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

Математики, может есть более рациональное решение?

задан 29 Янв '14 15:46

Как правило, в таких задачах всё удаётся найти, если есть рекуррентная зависимость последней цифры очередного члена от последних цифр предыдущих членов. В этом случае последовательность последних цифр всегда периодична, поэтому значение $%n$%-го члена можно найти, поделив $%n$% с остатком на длину периода. Даже если здесь участвует возведение в степени с очень большими показателями, то это не препятствие, так как последние цифры образуют периодическую последовательность.

(29 Янв '14 15:56) falcao

В моём случае последовательность получается очень уж странной.

Как бы я ни старался, не могу увидеть период.

0, 1, 2, 1, 5, 7, 8, 2, 9, 6, 5, 3.

f(k)=f(k-2)+3*f(k-3)

(29 Янв '14 16:34) MathMike
10|600 символов нужно символов осталось
2

Для того, чтобы в такой последовательности получился период, нужно повторение трёх подряд идущих членов последовательности. Поскольку остатки от деления на 10 принимают 10 значений, для подряд идущих троек получается $%10^3$% значений, то есть в пределах тысячи период должен себя проявить. Значение при этом может оказаться и меньше -- за счёт того, что не все тройки оказываются задействованы. Однако вычислять такое количество членов вовсе не обязательно. Можно учесть тот факт, что 10 -- число составное, и рассмотреть отдельно остатки от деления на 2 и остатки от деления на 5.

Для первого случая всё оказывается совсем просто: 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, ..., откуда ясно, что длина периода равна 7. Для остатков от деления на 5 дело обстоит чуть хуже: там все тройки, кроме нулевой, участвуют в последовательности, и непосредственная проверка показывает, что период там равен 124.

Таким образом, длина периода для последовательности остатков от деления на 10 оказывается равна $%7\cdot124=868$%. Это не что иное как $%(2^3-1)(5^3-1)$%.

Если $%n$% -- какое-то большое число, то мы его делим с остатком на 7 и на 124, после чего выясняем, какими должны быть остатки от деления на 2 и на 5. Например, пусть $%n=2014$%. При делении на 7 получается 5, а на пятом месте в последовательности нулей и единиц у нас стоит 1. Значит, последняя цифра будет нечётной. Далее, при делении на 124 число 2014 даёт в остатке 30. Здесь надо иметь "шпаргалку" в виде периода последовательности остатков от деления на 5. Вот она: 0, 1, 2, 1, 0, 2, 3, 2, 4, 1, 0, 3, 3, 3, 2, 2, 1, 3, 2, 1, 1, 2, 4, 0, 0, 2, 0, 2, 1, 2, 2, 0, 3, 1, 3, 0, 1, 4, 1, 2, 3, 0, 4, 4, 4, 1, 1, 3, 4, 1, 3, 3, 1, 2, 0, 0, 1, 0, 1, 3, 1, 1, 0, 4, 3, 4, 0, 3, 2, 3, 1, 4, 0, 2, 2, 2, 3, 3, 4, 2, 3, 4, 4, 3, 1, 0, 0, 3, 0, 3, 4, 3, 3, 0, 2, 4, 2, 0, 4, 1, 4, 3, 2, 0, 1, 1, 1, 4, 4, 2, 1, 4, 2, 2, 4, 3, 0, 0, 4, 0, 4, 2, 4, 4, 0, 1, 2, 1, 0, 2

На 30-м месте находится остаток 2, который дают цифры 2 и 7. Нас интересует нечётная цифра, то есть это будет 7. Именно на эту цифру оканчивается 2014-й член последовательности.

ссылка

отвечен 29 Янв '14 17:57

10|600 символов нужно символов осталось
1

Если Вы все-таки решили использовать возможности ЭВМ, то для решения поставленной задачи абсолютно необязательно хранить сами переменные (хотя и это возможно), а достаточно хранить только последние цифры членов последовательности. Именно они однозначно определяют последнюю цифру следующего члена этой же последовательности. Вот пример кода на одном алгоритмическом языке var i: longint; a,b,c,f: integer;

begin a:=0; b:=1; c:=2; for i:=1 to 1000000 do begin f:=(b+3*a) mod 10; a:=b; b:=c; c:=f; write(f,' '); end; writeln(f); end.

ссылка

отвечен 29 Янв '14 20:44

@aid78: там, насколько я понимаю, числа имеют диапазон не порядка миллиона, а порядка 10 в степени миллион. То есть до них всё равно не досчитать, и надо опираться на периодичность в процессе нахождения остатков.

(29 Янв '14 20:49) falcao

@falcao согласен с Вами, недосмотрел.

(30 Янв '14 3:01) aid78
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×2,946
×221
×127
×37
×25

задан
29 Янв '14 15:46

показан
720 раз

обновлен
30 Янв '14 3:01

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru