Find the largest integer k for which 2^k divides 59!
", "hints_md": "The title of this problem is a little bit of a clue ", "hints_html": "The title of this problem is a little bit of a clue
", "editorial_md": "The problem requires us to find the largest power of $2$ that divides $59!$. This is a classic application of **Legendre's formula**, which is used to determine the highest power of a prime $p$ dividing $n!$. The formula is:\n\n$k = \\displaystyle\\sum_{i=1}^{\\infty}\n\\left\\lfloor \\frac{n}{p^i} \\right\\rfloor$ \n\nWhere:\n- $n=59$ in our case,\n- $p = 2$, since we are interested in powers of $2$,\n- $\\left\\lfloor x \\right\\rfloor$ denotes the floor function, which rounds down to the nearest integer.\n\nWe will calculate $k$ by summing the number of multiples of $2$, $4$, $8$, and so on, up to the largest power of $2$ that is less than or equal to $59$:\n\n$k=\\left\\lfloor \\frac{59}{2^1}\\right\\rfloor +\\left\\lfloor \\frac{59}{2^2} \\right\\rfloor+\\left\\lfloor \\frac{59}{2^3} \\right\\rfloor+\\left\\lfloor \\frac{59}{2^4} \\right\\rfloor+\\left\\lfloor \\frac{59}{2^5} \\right\\rfloor$ \n\nSince $2^6 > 59$, all subsequent terms will be zero, solving further, we get:\n\n$k=\\left\\lfloor 29.5\\right\\rfloor +\\left\\lfloor 14.75\\right\\rfloor+\\left\\lfloor 7.375 \\right\\rfloor+\\left\\lfloor 3.8675 \\right\\rfloor+\\left\\lfloor 1.84375 \\right\\rfloor$ \n\n$k = 29 + 14 + 7 + 3 +1 + 0 = 54$\n\nThus our answer is $54$.\n\n- botman\n", "editorial_html": "The problem requires us to find the largest power of 2 that divides 59!. This is a classic application of Legendre’s formula, which is used to determine the highest power of a prime p dividing n!. The formula is:
k = \\displaystyle\\sum_{i=1}^{\\infty} \\left\\lfloor \\frac{n}{p^i} \\right\\rfloor
Where:
We will calculate k by summing the number of multiples of 2, 4, 8, and so on, up to the largest power of 2 that is less than or equal to 59:
k=\\left\\lfloor \\frac{59}{2^1}\\right\\rfloor +\\left\\lfloor \\frac{59}{2^2} \\right\\rfloor+\\left\\lfloor \\frac{59}{2^3} \\right\\rfloor+\\left\\lfloor \\frac{59}{2^4} \\right\\rfloor+\\left\\lfloor \\frac{59}{2^5} \\right\\rfloor
Since 2^6 > 59, all subsequent terms will be zero, solving further, we get:
k=\\left\\lfloor 29.5\\right\\rfloor +\\left\\lfloor 14.75\\right\\rfloor+\\left\\lfloor 7.375 \\right\\rfloor+\\left\\lfloor 3.8675 \\right\\rfloor+\\left\\lfloor 1.84375 \\right\\rfloor
k = 29 + 14 + 7 + 3 +1 + 0 = 54
Thus our answer is 54.