?

Log in

No account? Create an account
entries friends calendar profile Арбуз - занимательный мир Previous Previous Next Next
две чудные задачи - кросспосты из блога
sklyarevskiy
sklyarevskiy
две чудные задачи
34 комментов или Написать
Comments
From: (Anonymous) Date: February 2nd, 2007 07:33 am (UTC) (Link)

Факториал - последние 250 000 цифр

Последнюю ненулевую цифру (ПНЦ) можно определить следующим образом. Совершенно правильно, что ключевую роль играет ПНЦ в числе 9! - восьмерка. так как
1*2*...*1000000 можно перегруппировать как (1*2*...*9)*10*(11*...*19)*...*1000000
ПНЦ (1000000!) совпадает с ПНЦ (8**(100000)*100000!) и по цепочке с
ПНЦ(8**(100000+10000+1000+100+10+1)). Здесь мы пользуемся свойством
ПНЦ (х*у)= ПНЦ (ПНЦ(х)*ПНЦ(у)).
Таким образом, искомое число равно ПНЦ(8**111111)=ПНЦ(2**333333). Так как
2**5=32, ПНЦ (2**х)= ПНЦ(2**(МОД(х,4)) и искомое число равно ПНЦ (2**1)=2.

Более интересный вопрос, сколько нулей после этой злосчастной двойки. Все нули в факториале пораждаются числами кратными 5, а более точно степенями 5-ки, поэтому нулей в факториале 1 000 000! ровно
200000+40000+8000+1600+320+64+13+2= 249 999. Таким образом, мы знаем 250 000 последних цифр из порядка 5 600 000 цифр - 4,5% всех цифр - совсем неплохо!

А какая первая цифра этого большого числа и сколько вообще в нем цифр?




From: (Anonymous) Date: February 2nd, 2007 07:40 am (UTC) (Link)

Re: Факториал - последние 250 000 цифр

По похожей схеме можно определить ПНЦ любого числа, исходя из рекуррентной формулы
ПНЦ [(10*х+у)!] = ПНЦ [ПНЦ(x!)*ПНЦ(8**х)*ПНЦ(у!)]
и общее количество нулей используя Целую часть (ЦЧ)

ЦЧ(x)+ЦЧ(х/5)+ЦЧ(х/5**)+...

что асимптотически равно (х-1)/4

AZ
sklyarevskiy From: sklyarevskiy Date: February 2nd, 2007 08:08 am (UTC) (Link)

Re: Факториал - последние 250 000 цифр

Спасибо! Жаль, что Вы анонимно.. на кого сослаться если опубликую решение?
From: kdmtr Date: February 8th, 2007 08:41 pm (UTC) (Link)

Re: Факториал - последние 250 000 цифр

Немножко непонятно Ваше доказательство. Я не вникал, но по внешнему виду оно больше остальных напоминает моё решение.

ПНЦ (х*у)= ПНЦ (ПНЦ(х)*ПНЦ(у))
ПНЦ(12*5) = 6
ПНЦ(ПНЦ(12)*ПНЦ(5)) = ПНЦ(10) = 1

Насчёт количества нулей: по-моему, их 249998, т.к. 64/5 = 12, а не 13 :-)

У меня самого получилась ещё не встречавшаяся здесь четвёрка!
Но сначала проверю на компьютере, а то тут уже и без меня столько ерунды понаписано :-)))
From: kdmtr Date: February 12th, 2007 07:58 pm (UTC) (Link)

Re: Факториал - последние 250 000 цифр

В общем, вся прогрессивная общественность давным-давно знает, что последняя ненулевая цифра числа 1000000! находится на 249999-ой позиции с конца и является четвёркой. Если кого-то ещё интересует доказательство, то могу написать своё (кривое), либо порекомендовать походить по интернету, где оно непременно найдётся, либо порекомендовать вычислить самому и убедиться. Вот программа на Питоне:
import gmpy
print gmpy.fac(1000000)
34 комментов или Написать