Задача 338: За любителите на аритметиката и информатиката (накуп)

[MitkoS]

Вчера, публикувах задачата с доста предизвикателни коментари. Днес, (след като преспах) установявам че доста съм надценил сложността и сега коментарите ми изглеждат излишно самонадеяни и звучат глупаво. Затова ги изтривам с лека ръка (а и все още никой не е писал след мен)

Самата задача е такава:

Да се намери алгоритъм за намиране на последната ненулева цифра на N! (ЕН фактуриел), където N е голямо, да речем повече от 1000.

Доколкото виждам, съществуват поне десетина алгоритъма.
Всеки да се чувства добре дошъл да напише някакъв (в свободен текст или както му е удобно).
Ще се ценят такива, при които циклите са къси, рекурсиите са плитки, не се работи с прекалено големи числа и т.н., т.е. гони се "оптимизация" (на алгоритъма).

[MitkoS]

Имам голямо желание малко да променя и поокрася условието така:

Влюбили сте се в красивата принцеса на местното царство.
Но нейния баща (царят) е строг и леко зъл. Мрази счетоводителите си защото го послъгват. Мрази и програмистите, защото постоянно му се гътват компютърните системи. ... неква фобия има към тия хора.

Принцесата вече е порастнала достатъчно и се оглежда нетърпеливо за партньри.
Току-що, царят е обявил, че след два дни ще има изпит за кандидатите за принцесата и вие се колебаете дали да отидете, защото царят измъчван от фобията си е определил следните условията за изпита:
- ще ви се предостави само молив и тетрадка, никакви лаптопи, никакви калкулатори
- ще бъде казано число N межди 8000 и 9999
- трябва да се намери последната ненулева цифра на N! (ЕН факториел)
- ще бъде отпуснат 1 час за решаване и смятане
- който не се справи, отива на бесилката

И така, имате цели два дни за да решите дали да отидете на изпита.

И това е въпроса на задачата - ще отидете ли ?

[Edin_Lud]

Нещо се мъча да направя с 2 и 5, но не ми се получава докрай...а може и да бъркам

Елиминирам нулите - те са толкова, колкото пъти в умножението участват числа кратни на 2 и на 5. Числата кратни на 2 са повече, така че броим само числата кратни на 5.
Т.е. нулите са n, ако в N! участват n числа кратни на 5 => последната цифра е N!/(2^n*5^n) mod 10 и е четно число.

После търсим колко е n. T.e. делим N n пъти на 5 до резултат <= 4 (тук не ми трябва цикъл или рекурсия, защото 9999 < 5^5, т.е. няма да деля повече от 5 пъти - не е трудно)

Остава въпроса как да намерим N!/(2^n*5^n) като функция на 2 и 5. За целта представяме N!/(2^n*5^n) като {N!/(2^m*5^n) * 2^(m-n)} или 2^(m-n) mod 10 ни дава последната цифра. Само че не мога да се сетя как да намеря m или 2^(m-n)

P.S. Намерих си грешка, но не помага да намеря резулатата...
представяме N!/(2^n*5^n) mod 10 като {N!/(2^m*5^n) mod 10 * 2^(m-n) mod 10} mod 10, за да намерим последната цифра...забравят се елементарни правила...

[MitkoS]

Я, кой бил тук !
Edin_Lud, от много време не си се появявал, радвам се че пишеш тук в задачата. ... Бе знаех си аз, че с принцеси по-лесно се събира аудитория.

А иначе по задачата, добре си го подкарал по принцип. Сега остава да поодялкаш туй-унуй и да го изпипаш докрай (някак си)

[Bibi]

@Edin_Lud,
броя на множителите 2, които участват в n! би трябвало да е
[n/2] + [n/4] + [n/8] + ...
Това е функцията скобка, или целочислено деление.
Разбира се, това важи не само за 2, а и за всяко друго просто число. Примерно 5.

Имам предложение как задачата може да се смята на ръка
Но и то е с цикъл, понеже за да сметна n!, последователно пресмятам всички по-малки.
Всъщност пресмятам само последната ненулева цифра на всички 1!, 2!, ... (n-1)!
Налага се да го правя само защото за да сметна последната ненулева на n! ми е нужно да знам последната ненулева на (n-1)!

Разлагам n на прости множители така:
n = 2p.5q.m, като m не се дели нито на 5, нито на 2.

Сега различавам 3 случая:
1. p > q
n = (2q.5q).m.2p-q
Търсената последна цифра получавам като умножа предната по m.2p-q

2. p = q
Търсената последна цифра получавам като умножа предната по m

3. p < q
Тук вместо да умножавам по 5, предпочитам да си мисля, че умножавам по 10 и деля на 2.
Затова първо предната последна цифра умножавам по m и после полученото деля на 2 (q-p) пъти.
Но как деля число на 2, щом знам само последната му цифра?
Ако последната цифра е била примерно 6, разделеното число може да завършва или на 3, или на 8. И как да избера кое?
Ами ето как - в случая, във вички n!, дори да им премахнем нулите отзад, ще са четни.
А всички двусмислени деления на 2 ме карат да избирам между едно четно и едно нечетно винаги.
Така че просто при всяко делене на 2 избирам четния вариант за отговор.
Това е.

Освен това мисля, че ако напишем отговорите на всички задачи един след друг, ще забележим цикличност.
Заради "принципа на чекмеджетата", понеже имаме краен брой цифри, а безкраен брой задачи.
Ако успея да видя при кое n нещата започват да се повтарят, ще пиша допълнително.
Това ще помогне да решаваме задачата дори за особено големи n.

P.S.
За последното изглежда не съм права.

[MitkoS]

А на мен ми се налага да призная, че в моя алгоритъм се появи един недостатък, който ме праща директно на бесилото.
Остава ми единствено да перефразирам мисълта „Пътя към ада е осеян с добри намерения” на „Пътя към бесилката е осеян с добри намерения”.
Последните ми „предсмъртни” думи са, че попаднах в капана на една красива и изкусителна идея. Толкова е великолепна, че си заслужава да я разкажа, но предупреждавам, че е фалшива.

И така, имаме
N!=1.2.3.4.5.6.7.8.9….(N-1).N
Разделяме множителите на три групи от които правим три отделни произведения.

Първата я означавам с P5 – тук са всички числа, по-малки от N и завършващи с цифрата 5
P5=5.15.25.35.45.55.65.75. …
Втората я означавам с P0 – тук са тук са всички числа, по-малки от N и завършващи с цифрата 0
P0=10.20.30.40.50.60…
Третата група P са всички останали числа по-малки от N
Т.е. имаме
N! = P.P0.P5
Сега, като разгледаме всяко едно от тези P-та, забелязваме следните три неща, (които евентуално при интерес ще опиша в детайли в отделен пост):
1. За P
На пръв поглед , това произведение P изглежда много страшно. Но всъщност въобще не е така и с лекота могат да бъдат изчислени последните две цифри на ръка. Бих казал, че P е най-безпроблемния от трите множителя P.P0.P5.
2. За P5
При N>15, последните две цифри на P5 са винаги или 25 или 75, при това, ако ни е известна точната стойност на N, с лекота можем да изчислим на ръка кои точно цифри са – 25 или 75
3. За P0 имаме
P0=10[N/10].N1!,
Тук N1 е числото което се получава като на числото N махнем най-дясната цифра.
Разкошно, нали – рекурсия при която скъсяваме порядъка. При нашата конкретна задача, дълбочината на тази рекурсия ще бъде най-много 4.
Т.е., ще имаме N, N1, N2, N3, където N3 е едноцифрено и без проблеми можем на ръка да сметнем N3! .
Т.е., прилагаме следния алгоритъм за да изчислим на ръка последната ненулева цифра на N!
1. За едноцифреното N3 изчисляваме на ръка N3! или поне последната цифра
2. Сега гледаме N2! – разлагаме го на съответните P, P0, P5 за двуцифреното N2
N2! = P.P0.P5
И на P, и на P0, и на P5 знаем последните две ненулеви цифри ==> знаем последната цифра на N2!
(червеното ==> на горния ред всъщност е невярното в моя алгоритъм)
3. Сега гледаме N1! – разлагаме го на съответните P, P0, P5 за трицифреното N1
N1! = P.P0.P5
Знаем последните две ненулеви цифри на P и на P5, знаем последната ненулева цифра на P0 ==> знаем последната цифра на N1!
4. Остана четирицифреното N, за което правим аналогичните (и неверни) сметки.

…
Красиво, но невярно

[MitkoS]

Edin_Lud,
Ако комбинирам твоята идея с моя псевдоалгоритъм, май ще ми се размине бесилката.

ПП.
Но няма като теб да вадя всички петици в самостоятелен множител - част от петиците ще си ги оставя в общия кюп, за да мога да направя множител, който е фактуриел на число с по-малък порядък.

[Bibi]

Снощи комбинирахме всички налични идеи и решихме задачата.
По-дълго е за разказване, отколкото самото смятане. И така:

Съображение 1: ако вземем кои да е 10 поредни цели числа и от тях премахнем двете, които се делят на 5, произведението на останалите осем завършва на 76.
Нас ни интересуват произведения от вида (d+1).(d+2).(d+3).(d+4).(d+6).(d+7).(d+8).(d+9), където d е някакво цяло число, кратно на 10. примерно 1321.1322.1323...1329
(ако се наложи, ще го докажа по-натам)

Съображение 2: ако произволно четно число, което не се дели на 10, се умножи по друго, което завършва на 6, последната му ненулева цифра остава непроменена.

Заради горните две, процедираме така:
- от всички множители, участващи в n!, в една група отделяме делящите се на 5.
Кръщаваме я P5. Тя съдържа някакво произведение от вида 5.10.15.20.25...
- оставащите множители образуват няколко серии от оня вид, дето произведението им завършва на 76, плюс една подобна, но непълна група.
Поради С.2 всички пълни серии можем да ги пренебрегнем, защото произведението им завършва на 6 и те няма да се отразят на резултата. Вместо всички тях ще пиша 6. А непълната група (тя има максимум 8 множители) ще кръстя P.
В крайна сметка стигаме до:
n! = 6.P.P5
В случая "=" означава "има еднаква последна ненулева цифра". За да пиша по-малко.

Последната ненулева цифра на 6.P можем лесно да сметнем на ръка.
Имаме да уможим последните цифри на десетина числа, а понеже са еднотипни, даже можем предварително да ги пресметнем всичките и после да си ги ползваме наготово.
Да кръстим последната ненулева цифра на 6.P с Q.

Сега да видим какво да правим с P5
P5 = 5.10.15.20.25... = 5m.(1.2.3.4.5...) = 5m.m!
Тук m е броят числа, по-малки от n и делящи се на 5, т.е.
m = [n/5]

Понеже новото число m < n, това ще бъде нашата рекурсия - за да сметнем задачата за n! ще ни трябва да решим задачата за m!.
Първоначалната идея на MitkoS успяваше да свали с цял порядък новата задача, спрямо първоначалната. Тук редуцираме по-слабо, но все пак достатъчно, за да можем да смятаме на ръка. При 4-цифрено n, получаваме до 5 стъпки, което е поносимо.
Да кръстим последната ненулева цифра на m! с R.
Стигнахме до
n! = Q.5m.R
n! = Q.R/2m.10m
Горе разделям и умножавам по 2m, с което постигам следното - всяка 5-ица успя да се комбинира с по една 2-ка. Повече нули няма да получаваме и спокойно моем да смятаме, без да ни е страх, че решението ще се измести с един порядък напред и ще изгубим представа за търсената цифра.

Вече смело можем да кажем, че последната цифра на n! е същата като последната цифра на Q.R/2m

[Bibi]

Стигнахме до следната задача:
Да се намери последната цифра (тук тя със сигурност е ненулева) на
Q.R/2m,
където Q и R са едноцифрени (четни).

Разбира се можем да ги умножим двете, нищо не губим. И стигаме до въпроса как да разделим едно цяло четно число (на което знаем само последната цифра) на 2m. При положение, че сме сигурни, че числото се дели на толкова много двойки.
Ако знам как да разделя всяко такова число на 2, ще мога да разделя и на 2m, просто m пъти делейки на 2.

Съображение 3: 2:2 = 6, 6:2 = 8, 8:2 = 4, 4:2 = 2.
Горното да се чете така: "ако разделим на 2 число, с последна цифра 6, частното ще има последна цифра 8".
Както описах в един мой преден пост, при условията, с които разполагаме можем напълно да се доверим на това твърдение.

Последното, което ни остава да преборим е как да разделим (използвайки табличката от С.3) някакво число примерно 1357 пъти? Адски досадно би било!

Съображение 4: при всички условия, с които разполагаме, разделянето на нашето число на 2m е еквивалентно на разделянето му на 2s, където s е остатъка от делението на m с 4.
Като разгледаме табличката, виждаме, че нещата се зациклят на всеки 4 стъпки. Т.е. делението на 24 = 16 не променя последната цифра, така че можем да не го правим. Това много прилича на С.2, направо си е същото и ще го ползваме.

Така че в крайна сметка ще ни се наложи да делим 0-3 пъти, което не е никакъв пролем за правене на ръка.
Ами това е!

[Bibi]

След толкова дълъг текст трябва да покажа, че на практика нещата изобщо не са дълги.
Мисля вместо абстрактния алгоритъм да покажа конкретен пример.
6543!

6543!

= 6 . 51308 . 1308! (пренебрегнала съм пълните групи,[br]първия множител 6 идва от последната непълна група 3!,[br]1308 е 6543/5)

1308!

= 4 . 5261 . 261!

261!

= 6 . 552 . 52!

52!

= 2 . 510 . 10!

Сега започвам от последната нагоре.
52! =2/210.1010.8 = (2.8)/22 = 6/2/2 = 4
(Това 8 дойде като последна цифра от 10!, което сметнах на ръка.
Ако някой го мързи да змята до 10!, може да си пусне още една итерация.)
261! = 6/252.1052.4 = (6.4)/20 = 4
(4 дойде от току-що сметнатото в предната итерация)
1308! = 4/2261.10261.4 = (4.4)/21 = 6/2 = 8
6543! = 6/21308.101308.8 = (6.8)/20 = 8

Както виждата става много бързо, без трудни сметки.
Последната ненулева цифра на 6543! е 8

[Bibi]

Така като гледам, сама си говоря

Та, понеже MitkoS е отправил задачата към любителите на аритметиката и информатиката, а то до тоя момент само сметки имаше, затова реших да направя и едно скриптче, което да работи по описаната идея. Тук:
http://bibi.li/factoriel.html
Преди да измислим самата идея, нямаше смисъл от компютърно смятане, освен по дърварския начин, но той щеше да е адски бавен при тия огромни резултати.

Иначе човек може да види всички цифри на някое n! в тоя сайт:
http://www.wolframalpha.com/input/?i=6543%21

[MitkoS]

Ако някой очаква някакъв коментар от мен като автор (на условието) , то такъв коментар няма да има - Bibi e споменала по-горе, че решението е колективно, а аз бях част от колектива (снощи).

Обаче това последното си е 100% нейно дело, за което и свалям шапка. ... и не само затова де.

[Bibi]

Моя е грешката, че не го казах. Ама защото се радвах, че вече е решена поне по един начин и...

А всъщност то MitkoS я направи. Тия "съображения" са негово откритие, а без тях нямаше никаква смислена идея, по която да се умува.
Опитах да я опиша. Все още има доста неточности и полуизказани неща. Ако Krusteva се появи, ще има за какво да ме мъмри, та обещавам да поправя обясненията, докато не е станало късно.
А на MitkoS багодарности и за условието, и за решението!

[MitkoS]

Хайде стига си скромничила ... това тук не е конкурс "Мис Логически задачи"
Ако знаех, че така здраво ще я захапеш тази задача, щях да дам условието за принцове, а не за принсеси.


По-нагоре казах, че нямам коментари, ама всъщност имам.
Това "мъчното" с двойките може да отпадне. Не е нужно да имаме последователно "делене" на 2. Нищо че е най-много три-пъти. Защото последния знак на 2m е известен при известно m и просто за двата дни ще "научим наизуст" една табличка 4x4 състояща се само от четни едноцифрени числа.

[dedis]

Както и в много предишни изяви, вие двамата ме оставяте безмълвен.
Една съвсем проста за вас задачка, която ме занимаваше преди мно-о-о-го години:
Най-бърз алгоритъм за подреждане по случаен начин на първите N последователни естествени числа. Така, че времето за изпълнение да расте пропорционално на N, а не много по-стръмно.
Навремето аз измислих един такъв, но може би има и по-бърз.
Забележка: На времето пробвахме с Бъзик интерпретатор, така, че времената за изпълнение се различаваха забележимо. (BASIC, де).