Отличная от нуля последняя цифра факториала

@ssrstun · Регистрация: 04.01.2020

Студворк — интернет-сервис помощи студентам

Через циклы, не рекурсивно. Пример: Ввод - 5, Вывод - 2. Ограничения от 1 до 10^18. Ссылки на похожие темы не присылать, там смотрел.

Байт · 05.01.2020, 13:56

C++
1
2
3
4
int rest = 1;
for(k=2; k<=N; k++)
  if (k%5)
    rest = rest*k%10;

@alexu_007 · 06.01.2020, 11:14

Факториал 10000! - это цифра из 35660 чисел, 2499 нолей в конце, последняя цифра - 8. А это всего 10^5.
10^18 тупо в лоб не вычислишь никогда, нужен хитрый алгоритм, который быстро вычисляет только последнюю цифру.

Байт · 06.01.2020, 12:35

Сообщение от alexu_007

это цифра из 35660 чисел

Не перепутали? Или это шутка?

Но с утра посмотрев внимательнее, увидел, что код в посте 2 считает чуток не то. Приношу извинения.

Добавлено через 4 минуты
Вот так поточнее будет

C++
1
2
3
4
5
6
int rest = 1;
for(k=2; k<=N; k++) {
    rest = rest*k;
    while(rest%10==0) rest /= 10;
    rest %= 10;
}

@alexu_007 · 06.01.2020, 12:54

Сообщение от Байт

Не перепутали? Или это шутка?

Проверяйте:

@SandCat · 07.01.2020, 18:00

здесь есть формула http://oeis.org/A008904

Байт · 07.01.2020, 18:24

SandCat, простите за вопрос, не имеющий отношения к теме. Вам, как любителю чисел, не попадалось ли решение уравнения
x₁⁶ + x₂⁶ + x₃⁶ + x₄⁶ + x₅⁶ + x₆⁶ = z⁶
Для степеней 3. 4, 5 подобное уравнение нам удалось довольно быстро решить, а вот шестерка никак не дается. И где-то в интернете я встречал то ли решение, то ли обсуждение этого вопроса. А найти никак не могу. Есть владеете какой-либо информацией по этому вопросу - поделитесь.

Добавлено через 2 минуты
Блин, перепутал нижние и верхние индексы. Попробую исправить...

@SandCat · 07.01.2020, 21:55

https://afp-zp.livejournal.com/348521.html вот для 5 есть решение, для 6 не знаю

Байт · 07.01.2020, 22:39

SandCat, спасибо! Прочел с удовольствием, и... некоторой досадой.
Дело в том, что где-то на рубеже тысячелетий мы прогуливались по собачьим делам с человеком, который тоже оказался любителем математики, и вот он как-то высказал предположение, схожее с гипотезой Эйлера. Поскольку я, в отличии от него, владел и компом, и некоторыми навыками работы с ним, тут же бросился его подтверждать-опровергать. Для степени 3 он сам нашел решение, изрядно помучившись. Мой комп выплюнул серию решений за пол-секунды. С четверкой он (комп) уже подумал чуток, но несколько решений успел показать. А с пятеркой, о чудо! выдал вот то самое решение (5-4), что в этой короткой статье. Опоздали, значит, на треть века... Мы ж не знали, что сам Эйлер к этому ручку приложил. Так, развлекались между делами....
А вот с шестеркой прям бяда! Уж и пару лемм нашли, здорово сокращающих перебор. И комп я бросал на несколько дней - пусть сам подумает... Ясно одно, что числа-решения должны быть не маленькими.
А тут еще мой приятель покинул нас всех. И эта задачка осталась не только сама по себе, но и как память о нем. Так что я, хоть ничего для нее и не делаю, но мыслию постоянно возвращаюсь...

@SandCat · 07.01.2020, 23:15

https://en.wikipedia.org/wiki/... conjecture вот здесь есть решения для 7 и 8

Байт · 07.01.2020, 23:31

SandCat, Спасибо за материал! Это все очень интересно. Думаю, Алексея Сергеевича эти результаты порадовали бы.
А шестерка, да, камень преткновения... 730000 - хорошее число. Правда, еще не выходящее за машино-представимые.

Байт · 08.01.2020, 14:48

Уважаемые модераторы! Мне кажется, что ответы начиная с поста 7, будучи сами по себе весьма интересными, настолько выбиваются из темы топика и данного раздела, что неплохо бы их перенести например в подраздел "Алгебра и Теория чисел" раздела "Математика". Возможно, там они найдут заинтересованных читателей.
Если для этого что-то требуется от меня, например, создание соответствующей темы, я готов.

Добавлено через 1 час 56 минут
Нашел аналог на русском
https://ru.wikipedia.org/wiki/... 0%B6%D0%B0
Правда, ничего нового.
Но кто бы мог подумать, что эта задача вполне популярна? И что не только мы, два прогуливающихся дилетанта, но и вполне серьезные умы думали над ней.

Новые блоги и статьи Все статьи Все блоги /
Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .

@ssrstun 0 / 0 / 0 Регистрация: 04.01.2020 Сообщений: 1

	Отличная от нуля последняя цифра факториала 04.01.2020, 22:27. Показов 2875. Ответов 11 Метки нет (Все метки) Через циклы, не рекурсивно. Пример: Ввод - 5, Вывод - 2. Ограничения от 1 до 10^18. Ссылки на похожие темы не присылать, там смотрел. 0

@alexu_007 736 / 700 / 110 Регистрация: 29.05.2015 Сообщений: 4,279
	06.01.2020, 11:14
	Факториал 10000! - это цифра из 35660 чисел, 2499 нолей в конце, последняя цифра - 8. А это всего 10^5. 10^18 тупо в лоб не вычислишь никогда, нужен хитрый алгоритм, который быстро вычисляет только последнюю цифру. 0

@SandCat 245 / 17 / 5 Регистрация: 18.12.2019 Сообщений: 33
	07.01.2020, 18:00
	здесь есть формула http://oeis.org/A008904 1

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	07.01.2020, 18:24
	SandCat, простите за вопрос, не имеющий отношения к теме. Вам, как любителю чисел, не попадалось ли решение уравнения x₁⁶ + x₂⁶ + x₃⁶ + x₄⁶ + x₅⁶ + x₆⁶ = z⁶ Для степеней 3. 4, 5 подобное уравнение нам удалось довольно быстро решить, а вот шестерка никак не дается. И где-то в интернете я встречал то ли решение, то ли обсуждение этого вопроса. А найти никак не могу. Есть владеете какой-либо информацией по этому вопросу - поделитесь. Добавлено через 2 минуты Блин, перепутал нижние и верхние индексы. Попробую исправить... 0

@SandCat 245 / 17 / 5 Регистрация: 18.12.2019 Сообщений: 33
	07.01.2020, 21:55
	https://afp-zp.livejournal.com/348521.html вот для 5 есть решение, для 6 не знаю 1

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	07.01.2020, 22:39
	SandCat, спасибо! Прочел с удовольствием, и... некоторой досадой. Дело в том, что где-то на рубеже тысячелетий мы прогуливались по собачьим делам с человеком, который тоже оказался любителем математики, и вот он как-то высказал предположение, схожее с гипотезой Эйлера. Поскольку я, в отличии от него, владел и компом, и некоторыми навыками работы с ним, тут же бросился его подтверждать-опровергать. Для степени 3 он сам нашел решение, изрядно помучившись. Мой комп выплюнул серию решений за пол-секунды. С четверкой он (комп) уже подумал чуток, но несколько решений успел показать. А с пятеркой, о чудо! выдал вот то самое решение (5-4), что в этой короткой статье. Опоздали, значит, на треть века... Мы ж не знали, что сам Эйлер к этому ручку приложил. Так, развлекались между делами.... А вот с шестеркой прям бяда! Уж и пару лемм нашли, здорово сокращающих перебор. И комп я бросал на несколько дней - пусть сам подумает... Ясно одно, что числа-решения должны быть не маленькими. А тут еще мой приятель покинул нас всех. И эта задачка осталась не только сама по себе, но и как память о нем. Так что я, хоть ничего для нее и не делаю, но мыслию постоянно возвращаюсь... 0

@SandCat 245 / 17 / 5 Регистрация: 18.12.2019 Сообщений: 33
	07.01.2020, 23:15
	https://en.wikipedia.org/wiki/... conjecture вот здесь есть решения для 7 и 8 1

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	07.01.2020, 23:31
	SandCat, Спасибо за материал! Это все очень интересно. Думаю, Алексея Сергеевича эти результаты порадовали бы. А шестерка, да, камень преткновения... 730000 - хорошее число. Правда, еще не выходящее за машино-представимые. 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	08.01.2020, 14:48
	Уважаемые модераторы! Мне кажется, что ответы начиная с поста 7, будучи сами по себе весьма интересными, настолько выбиваются из темы топика и данного раздела, что неплохо бы их перенести например в подраздел "Алгебра и Теория чисел" раздела "Математика". Возможно, там они найдут заинтересованных читателей. Если для этого что-то требуется от меня, например, создание соответствующей темы, я готов. Добавлено через 1 час 56 минут Нашел аналог на русском https://ru.wikipedia.org/wiki/... 0%B6%D0%B0 Правда, ничего нового. Но кто бы мог подумать, что эта задача вполне популярна? И что не только мы, два прогуливающихся дилетанта, но и вполне серьезные умы думали над ней. 0