две чудные задачи

Log in

10:20 pm January 26th, 2007

No account? Create an account

Remember me




			кросспосты из блога

sklyarevskiy


	две чудные задачи
	Опубликовано на сайте Арбузный блог. Можно оставить комментарий здесь или в блоге. Подробнее о них и о других здесь 2. Какая цифра находится непосредственно слева от цепочки нулей, которой заканчивается факториал миллиона? 6. Предположим, орбиты планет круговые. Какая планета в среднем ближайшая к Плутону? Какая планета будет ближайшей к Плутону с наибольшей вероятностью? Какая - с наименьшей?

34 комментов или Написать


	Comments

	From: yaroslaw	Date: January 26th, 2007 06:14 pm (UTC)		(Link)

2. ответ "6"?:) вроде все правильно посчитали...
ЗЫ уфффф... упарился...:))))
ЗЫ2 а может все же 42? ну то, самое, которое жизни, вселенной и всего такого...:))))

(Reply) (Thread)

	From: sklyarevskiy	Date: January 26th, 2007 07:54 pm (UTC)		(Link)

а у меня 8 получается????

(Reply) (Parent) (Thread)

From: zur_kosmonaft	Date: January 26th, 2007 08:27 pm (UTC)		(Link)

1*2*3*4*5*6*7*8*9 - последняя цифра 8. 8^2 - 4. 4^2 - 6. 6^2 - 6 и т.д. Т.е. уже начиная с 30! последней будет "6" для любого n! при n делящемся на 10. Скучноватая задачка. Про Плутон интереснее. Пока не осилил

(Reply) (Parent) (Thread) (Expand)


	(no subject) - zur_kosmonaft - Expand


	(no subject) - sklyarevskiy - Expand


	(no subject) - georgick - Expand


	(no subject) - zur_kosmonaft - Expand


	(no subject) - yaroslaw - Expand


	(no subject) - georgick - Expand


	(no subject) - yaroslaw - Expand


	(no subject) - georgick - Expand


	(no subject) - georgick - Expand


	(no subject) - yaroslaw - Expand


	(no subject) - georgick - Expand


	(no subject) - (Anonymous) - Expand


	(no subject) - georgick - Expand


	(no subject) - yaroslaw - Expand


	(no subject) - georgick - Expand


	(no subject) - yaroslaw - Expand


	(no subject) - yaroslaw - Expand

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% всех цифр - совсем неплохо!

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

(Reply) (Thread)

From: (Anonymous)	Date: February 2nd, 2007 07:40 am (UTC)		(Link)
Re: Факториал - последние 250 000 цифр

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

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

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

AZ

(Reply) (Parent) (Thread)

	From: sklyarevskiy	Date: February 2nd, 2007 08:08 am (UTC)		(Link)
	Re: Факториал - последние 250 000 цифр

Спасибо! Жаль, что Вы анонимно.. на кого сослаться если опубликую решение?

(Reply) (Parent) (Thread)

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 :-)

У меня самого получилась ещё не встречавшаяся здесь четвёрка!
Но сначала проверю на компьютере, а то тут уже и без меня столько ерунды понаписано :-)))

(Reply) (Parent) (Thread)

From: kdmtr	Date: February 12th, 2007 07:58 pm (UTC)		(Link)
Re: Факториал - последние 250 000 цифр

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

(Reply) (Parent) (Thread)

From: (Anonymous)	Date: February 2nd, 2007 12:04 pm (UTC)		(Link)

мне кажется есть один неучтенный момент:
ПНЦ (5*6)=3
ПНЦ (15*16)=4
ПНЦ (25*26)=5
ПНЦ (35*36)=6
ПНЦ (45*46)=7
....
т.е.

(Reply) (Thread)

From: (Anonymous)	Date: February 2nd, 2007 12:21 pm (UTC)		(Link)

т.е. ПНЦ(1*..*9)=8,
ПНЦ(11*..*19)=4 (отнюдь не 8!)
ПНЦ(21*..*29)=4
ПНЦ(31*..*39)=6
ПНЦ(41*..*49)=2
....
т.е.

(Reply) (Parent) (Thread)

	From: yaroslaw	Date: February 2nd, 2007 10:01 pm (UTC)		(Link)

Да!
если посмотрите выше, там мое решение, и оно как раз совпадало с вашим 8^111111
Но сразу после публикации я нашел несоответствие вычисленных пнц для первых факториалов. То что вы показали -- это и есть причина ошибки.
Соответствующий член мною найден и учтен:)
Завтра с утречка напишу все выкладки а заодно перепроверю все ошибки. А то уже третий раз я абсолютно уверен в решении -- не облажаться бы:)
Самое интересное, что этот добавочный член -- при правильной постановке вопроса -- тоже 8 :) и таким образом логика решения в конце усложняется не сильно. Если я все (в уме) посчитал правильно то должно получится 8^122222, но это завтра уточню вместе с решением:) (это я так, застолбить если что).

(Reply) (Parent) (Thread)

	From: teofast	Date: February 2nd, 2007 04:04 pm (UTC)		(Link)
	За задачу 2

Решение задачи 2, которое мелькало, вроде, в комментах, надо, насколько я понимаю, записать за S. Kakutani - который в 1967 соответствующую последовательность изучал. Смотреть надо здесь: http://www.research.att.com/~njas/sequences/A008904 - это вообще суперполезная энциклопедия целочисленных последовательностей.

(Reply) (Thread)

	From: sklyarevskiy	Date: February 2nd, 2007 06:18 pm (UTC)		(Link)
	Re: За задачу 2

Поясните, пожалуйста, как расстояния между планетами связаны с целочисленными последовательностями?

А про энциклопедию знаю, даже когда-то статью про нее писал...

(Reply) (Parent) (Thread)

	From: teofast	Date: February 2nd, 2007 06:23 pm (UTC)		(Link)
	Re: За задачу 2

Евгений, задача 2 - это ж про факториалы, вроде. Я её имел в виду.

(Reply) (Parent) (Thread) (Expand)


	Re: За задачу 2 - sklyarevskiy - Expand


	Re: За задачу 2 - teofast - Expand

From: (Anonymous)	Date: April 25th, 2007 03:33 am (UTC)		(Link)
MP3 приколы бесплатно и без регистрации

Скачайте телефонные приколы с Романом Петровичем! http://pizdopidor.ru/mp3.php
Без рекламы, регистраций, ограничений скокрости!

(Reply) (Thread)


	34 комментов или Написать