Home
About
Resume
Projects
Links
Blog
Download notebook
{ "cells": [ { "cell_type": "markdown", "id": "a469358e-2f57-4bd6-9c8d-c59f3d77920b", "metadata": {}, "source": [ "### Q48\n", "Find the last ten digits of the series, \\(1^1 + 2^2 + 3^3 + ... + 1000^{1000}\\)." ] }, { "cell_type": "code", "execution_count": 1, "id": "820c6f59-d5d1-4f67-a379-b41d8bb337ac", "metadata": {}, "outputs": [], "source": [ "def dec_to_bin(dec):\n", " return bin(dec).replace(\"0b\", \"\")\n", "\n", "def tranc_num_multiply(num_a,num_b,tranc):\n", " return (num_a * num_b) % (10 ** tranc)\n", "\n", "def tranc_num_pow2n(num,n,tranc):\n", " return tranc_num_pow2n(tranc_num_multiply(num,num,tranc),n-1,tranc) if n>=1 else num\n", "\n", "def tranc_num_pow(num,p,tranc):\n", " exponent = dec_to_bin(p)[::-1]\n", " result = 1\n", " for num in [tranc_num_pow2n(num,i,tranc) for i in range(len(exponent)) if exponent[i]==\"1\"]:\n", " result = tranc_num_multiply(result,num,tranc)\n", " return result\n", "\n", "def tranc_sum(x_vector,tranc):\n", " result = 0\n", " for i in x_vector:\n", " result = (result + i) % (10 ** tranc)\n", " return result\n", "\n", "def last_n_digit_of_self_powers_m(m,n):\n", " return tranc_sum((tranc_num_pow(i,i,n) for i in range(1,m+1)),n)" ] }, { "cell_type": "code", "execution_count": 2, "id": "af630329-9130-41b7-9eae-dbff1852f068", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "CPU times: user 8.22 ms, sys: 1.33 ms, total: 9.55 ms\n", "Wall time: 9.34 ms\n" ] }, { "data": { "text/plain": [ "9110846700" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%%time\n", "last_n_digit_of_self_powers_m(1000,10)" ] }, { "cell_type": "code", "execution_count": 3, "id": "66144a20-fad4-4ed4-aa76-4ce0dfc7e84a", "metadata": {}, "outputs": [], "source": [ "def last_n_digit_of_self_powers_m_2(m,n):\n", " return sum(i**i for i in range(1,m+1))%(10**n)" ] }, { "cell_type": "code", "execution_count": 4, "id": "bb719ffc-0cfb-4cb9-85f5-1cd3ac101294", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "CPU times: user 2.87 ms, sys: 713 µs, total: 3.58 ms\n", "Wall time: 3.58 ms\n" ] }, { "data": { "text/plain": [ "9110846700" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%%time\n", "last_n_digit_of_self_powers_m_2(1000,10)" ] }, { "cell_type": "code", "execution_count": null, "id": "86396837-af8c-4f05-9ccb-8ba7e0db24a2", "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.10" } }, "nbformat": 4, "nbformat_minor": 5 }
Previous Notebook:
Project Euler Q47
Next Notebook:
Project Euler Q49
Loading