Итальянка

[Doctor Boom]

Выписать последние три цифры $100500$ члена последовательности Фибоначчи

[Andrey A]

$100500=134\cdot750.$ Каждое $750$-е Фибоначчи делится на $1000.$ Выписываю: $000.$ Почему Итальянка?

(Оффтоп)

— Откуда вы выписываете такое вкусное вино?
— Отсюда пьём, видишь? А отсюда выписываем.

[Doctor Boom]

Andrey A
А вы могли бы для любого числа решить, для $432757$ и др?

Andrey A в сообщении #1612150 писал(а):

Каждое $750$-е Фибоначчи делится на $1000.$

А как вы это доказали?

-- 03.10.2023, 05:25 --

(Оффтоп)

Andrey A в сообщении #1612150 писал(а):

Почему Итальянка?

Потому что Пиза

[Andrey A]

Пиза? А...

Doctor Boom в сообщении #1612151 писал(а):

А как вы это доказали?

См. Вычисление наименьшего Фибоначчи, кратного данному модулю. У меня там табличка Excel в конце прикреплена. Насчет $432757$ не так просто. Если только по основанию некоторой сис.счисления, но подумаю.

[realeugene]

Andrey A в сообщении #1612152 писал(а):

Если только по основанию некоторой сис.счисления, но подумаю.

Логарифмическим алгоритмом по модулю 1000 конечно же. А максимум с миллионного повторения происходит зацикливание, так что несложно и в лоб, посчитав сначала период.

[wrest]

Doctor Boom в сообщении #1612151 писал(а):

для любого числа решить, для $432757$ и др?

Pari/gp вычисляет без проблем:
? fibonacci(432757)%1000
%92 = 737
? ##
*** last result computed in 9 ms.
?

[realeugene]

(Оффтоп)

wrest в сообщении #1612197 писал(а):

*** last result computed in 9 ms.

А после прогрева 1 мс

[Doctor Boom]

realeugene
wrest
Я недооценил мощь современных компов Тогда для вас выписать последние три цифры $358436853268954357854468657567$ члена последовательности Фибоначчи

[realeugene]

Doctor Boom в сообщении #1612224 писал(а):

Я недооценил мощь современных компов

Вы недооценили пакеты вычислений. А как за микросекунды посчитать то, что вы спрашиваете, я написал ранее: классическим алгоритмом вычисления Фибоначчи за логарифмическое время, проводя все вычисления по модулю 1000. Но писать код мне лень.

[mihaild]

Doctor Boom, тривиальная реализация (без учета периодичности) - примерно 5мс https://colab.research.google.com/drive ... sp=sharing.

[TOTAL]

Doctor Boom в сообщении #1612224 писал(а):

realeugene
wrest
Я недооценил мощь современных компов Тогда для вас выписать последние три цифры $358436853268954357854468657567$ члена последовательности Фибоначчи

Остатки (от деления на $1000$) периодичны с периодом $6000$

[wrest]

TOTAL в сообщении #1612228 писал(а):

Остатки (от деления на $1000$) периодичны с периодом $6000$

Тогда наверное так
? fibonacci(358436853268954357854468657567%6000)%1000
%98 = 978
? ##
*** last result computed in 0 ms.
?

[Doctor Boom]

realeugene в сообщении #1612188 писал(а):

максимум с миллионного повторения происходит зацикливание, так что несложно и в лоб, посчитав сначала период.

TOTAL в сообщении #1612228 писал(а):

Остатки (от деления на $1000$) периодичны с периодом $6000$

Ага, а если последние 10 цифр?

[TOTAL]

wrest в сообщении #1612229 писал(а):

TOTAL в сообщении #1612228 писал(а):

Остатки (от деления на $1000$) периодичны с периодом $6000$

Тогда наверное так ...

Про период это я без доказательства сказал, полагая, что период по модулю $P^k$ ($P$ - простое) равен $P^{k-1}$ периодам по модулю $P$. Легко доказать?

[mihaild]

TOTAL в сообщении #1612231 писал(а):

Легко доказать?

Википедия утверждает, что это открытый вопрос. Но что известно, что $\pi(p^k) | p^{k - 1}\cdot \pi(p)$. Впрочем это я за 5 минут в уме доказать тоже не смог.