Euler 030 - Digit fifth powers.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Euler Problem 30\n",
    "================\n",
    "\n",
    "Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:\n",
    "\n",
    "$$1634 = 1^4 + 6^4 + 3^4 + 4^4$$\n",
    "$$8208 = 8^4 + 2^4 + 0^4 + 8^4$$\n",
    "$$9474 = 9^4 + 4^4 + 7^4 + 4^4$$\n",
    "As $1 = 1^4$ is not a sum it is not included.\n",
    "\n",
    "The sum of these numbers is 1634 + 8208 + 9474 = 19316.\n",
    "\n",
    "Find the sum of all the numbers that can be written as the sum of fifth powers of their digits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "443839\n"
     ]
    }
   ],
   "source": [
    "pow = [d**5 for d in range(10)]\n",
    "print(sum(k for k in range(2,10**6)\n",
    "          if sum(pow[d] for d in map(int, str(k))) == k))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Explanation:** If the number $N$ has $d$ digits, then $10^{d-1} \\le N < 10^d$\n",
    "and the sum of the fifth powers of the digits of $N$ is at most $9^5 d$.\n",
    "Therefore, if the sum of fifth powers of the digits of $N$ is equal to $N$,\n",
    "then $10^{d-1} \\le 9^5 d$, which implies that $d \\le 6$.\n",
    "Hence we need only check $N \\le 10^6$.\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}