Home
About
Resume
Projects
Links
Blog
Download notebook
{ "cells": [ { "cell_type": "markdown", "id": "a469358e-2f57-4bd6-9c8d-c59f3d77920b", "metadata": {}, "source": [ "### Q29\n", "How many distinct terms are in the sequence generated by \\( a^{b} \\) for \\( 2 \\le a \\le 100 \\) and \\( 2 \\le b \\le 100 \\)?" ] }, { "cell_type": "code", "execution_count": 1, "id": "d4f3859a-662a-49ea-9d4b-e6767fd6f717", "metadata": {}, "outputs": [], "source": [ "def int_log(n,base):\n", " result = 0\n", " while int(n) >= base:\n", " n /= base\n", " result += 1\n", " return result\n", "\n", "def distinct_a_pow_b(a_lims,b_lims):\n", " reduce_map = dict()\n", " reduce_map_a_lim = a_lims[1]**0.5\n", " reduce_map_b_lim = int_log(a_lims[1],2)\n", " distinct_set = set()\n", " for a in range(a_lims[0],a_lims[1]+1):\n", " for b in range(b_lims[0],b_lims[1]+1):\n", " temp_set = (reduce_map[a][0],reduce_map[a][1]*b) if a in reduce_map else (a,b)\n", " if 1 < a <= reduce_map_a_lim and b <= reduce_map_b_lim and temp_set[0]**temp_set[1] <= a_lims[1]:\n", " reduce_map[a**b] = temp_set\n", " distinct_set.add(temp_set)\n", " return len(distinct_set)" ] }, { "cell_type": "code", "execution_count": 2, "id": "5ff502a6-14d0-4bd4-9fc1-31b51849761e", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "CPU times: user 1.89 ms, sys: 472 µs, total: 2.36 ms\n", "Wall time: 2.36 ms\n" ] }, { "data": { "text/plain": [ "9183" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%%time\n", "distinct_a_pow_b([2,100],[2,100])" ] }, { "cell_type": "code", "execution_count": 3, "id": "1948584e-48e5-4835-8fad-bdc4865cac2d", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "CPU times: user 5.13 ms, sys: 0 ns, total: 5.13 ms\n", "Wall time: 4.93 ms\n" ] }, { "data": { "text/plain": [ "9183" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%%time\n", "len(list(set(i**j for i in range(2,101) for j in range(2,101))))" ] }, { "cell_type": "code", "execution_count": null, "id": "89c0a855-6f57-43f5-aee1-67036ce605a7", "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 Q28
Next Notebook:
Project Euler Q30
Loading