119 lines
3.7 KiB
Plaintext
119 lines
3.7 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "5411064f",
|
|
"metadata": {},
|
|
"source": [
|
|
"# [Prime Summations](https://projecteuler.net/problem=77)\n",
|
|
"\n",
|
|
"We can once again adapt any of our methods from [problem 31](https://projecteuler.net/problem=31), including the easiest one: just let SageMath figure it out."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 1,
|
|
"id": "4c066047",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"71"
|
|
]
|
|
},
|
|
"execution_count": 1,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"from itertools import count\n",
|
|
"\n",
|
|
"for n in count(1):\n",
|
|
" p = Partitions(n, parts_in=prime_range(n)).cardinality()\n",
|
|
" if p > 5000:\n",
|
|
" break\n",
|
|
" \n",
|
|
"n"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "cd20554a",
|
|
"metadata": {},
|
|
"source": [
|
|
"Somewhat more interestingly, we could use generating functions again. This time, there's the added wrinkle that we don't know how far out we need to calculate our generating function, but we can work around this by just repeatedly increasing our precision and recalculating until we find our answer."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 2,
|
|
"id": "1b5376e2",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"1 + x^2 + x^3 + x^4 + 2*x^5 + 2*x^6 + 3*x^7 + 3*x^8 + 4*x^9 + 5*x^10 + 6*x^11 + 7*x^12 + 9*x^13 + 10*x^14 + 12*x^15 + 14*x^16 + 17*x^17 + 19*x^18 + 23*x^19 + 26*x^20 + 30*x^21 + 35*x^22 + 40*x^23 + 46*x^24 + 52*x^25 + 60*x^26 + 67*x^27 + 77*x^28 + 87*x^29 + 98*x^30 + 111*x^31 + 124*x^32 + 140*x^33 + 157*x^34 + 175*x^35 + 197*x^36 + 219*x^37 + 244*x^38 + 272*x^39 + 302*x^40 + 336*x^41 + 372*x^42 + 413*x^43 + 456*x^44 + 504*x^45 + 557*x^46 + 614*x^47 + 677*x^48 + 744*x^49 + 819*x^50 + 899*x^51 + 987*x^52 + 1083*x^53 + 1186*x^54 + 1298*x^55 + 1420*x^56 + 1552*x^57 + 1695*x^58 + 1850*x^59 + 2018*x^60 + 2198*x^61 + 2394*x^62 + 2605*x^63 + 2833*x^64 + 3079*x^65 + 3344*x^66 + 3630*x^67 + 3936*x^68 + 4268*x^69 + 4624*x^70 + 5007*x^71 + 5419*x^72 + 5861*x^73 + 6336*x^74 + 6845*x^75 + 7393*x^76 + 7979*x^77 + 8608*x^78 + 9282*x^79 + O(x^80)"
|
|
]
|
|
},
|
|
"execution_count": 2,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"prec = 20\n",
|
|
"while True:\n",
|
|
" R.<x> = PowerSeriesRing(ZZ, default_prec=prec)\n",
|
|
" G = 1 / prod(1 - x^p for p in prime_range(prec))\n",
|
|
" \n",
|
|
" d = G.dict()\n",
|
|
" if any(c > 5000 for c in d.values()):\n",
|
|
" break\n",
|
|
" \n",
|
|
" prec *= 2\n",
|
|
"\n",
|
|
"G"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "af318759",
|
|
"metadata": {},
|
|
"source": [
|
|
"We can see that $x^{71}$ is our first term with a coeffcient over 5000, so our answer is 71.\n",
|
|
"\n",
|
|
"## Relevant sequences\n",
|
|
"* Number of partitions of $n$ into prime parts: [A000607](https://oeis.org/A000607)\n",
|
|
"\n",
|
|
"#### Copyright (C) 2025 filifa\n",
|
|
"\n",
|
|
"This work is licensed under the [Creative Commons Attribution-ShareAlike 4.0 International license](https://creativecommons.org/licenses/by-sa/4.0/) and the [BSD Zero Clause license](https://spdx.org/licenses/0BSD.html)."
|
|
]
|
|
}
|
|
],
|
|
"metadata": {
|
|
"kernelspec": {
|
|
"display_name": "SageMath 9.5",
|
|
"language": "sage",
|
|
"name": "sagemath"
|
|
},
|
|
"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.11.2"
|
|
}
|
|
},
|
|
"nbformat": 4,
|
|
"nbformat_minor": 5
|
|
}
|