solves projectEuler 271

euler271.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{2: 1,\n",
       " 3: 1,\n",
       " 5: 1,\n",
       " 7: 1,\n",
       " 11: 1,\n",
       " 13: 1,\n",
       " 17: 1,\n",
       " 19: 1,\n",
       " 23: 1,\n",
       " 29: 1,\n",
       " 31: 1,\n",
       " 37: 1,\n",
       " 41: 1,\n",
       " 43: 1}"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n=13082761331670030\n",
    "from sympy import *\n",
    "factorint(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{2: [1],\n",
       " 3: [1],\n",
       " 5: [1],\n",
       " 7: [1, 2, 4],\n",
       " 11: [1],\n",
       " 13: [1, 3, 9],\n",
       " 17: [1],\n",
       " 19: [1, 7, 11],\n",
       " 23: [1],\n",
       " 29: [1],\n",
       " 31: [1, 5, 25],\n",
       " 37: [1, 10, 26],\n",
       " 41: [1],\n",
       " 43: [1, 6, 36]}"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f=factorint(n)\n",
    "assert all(v ==1 for v in f.values())\n",
    "xmod=dict()\n",
    "for p in f.keys():\n",
    "    xmod[p]=[]\n",
    "    for y in range(1,p):\n",
    "        if y**3%p==1:\n",
    "            xmod[p].append(y)\n",
    "xmod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(153416670, 1.3412904813498665)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# s=0\n",
    "# for x in range(2,n):\n",
    "#     if all(x%p in l for p,l in f.items()):\n",
    "#         s+=x\n",
    "# s\n",
    "\n",
    "\n",
    "from functools import reduce\n",
    "singulars=[p for p,l in xmod.items() if l[-1]==1]\n",
    "m=reduce(lambda x,y:x*y,singulars)\n",
    "m,m/n**.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "045ff1d6a8ec4a0eaf2ca46b29fa275c",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "  0%|          | 0/85276008 [00:00<?, ?it/s]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "4617456485273129588"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from tqdm.notebook import tqdm\n",
    "euler271=0\n",
    "for x in tqdm(range(m+1,n,m)):\n",
    "    if x**3%n==1:\n",
    "        euler271+=x\n",
    "euler271"
   ]
  }
 ],
 "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.12.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}