코딩 연습

The radical of \(n\), \({\rm rad}(n)\), is the product of the distinct prime factors of \(n\). For example, \(504 = 2^3 \times 3^2 \times 7\), so \({\rm rad}(504) = 2 \times 3 \times 7 =42\). If we calculate \({\rm rad}(n)\) for \(1 \le n \le 10\), then sort them on \({\rm rad}(n)\), and sorting on \(n\) if the radical values are equal, we get: Unsorted Sorted \(n\) \({\rm rad}(n)\) \(n\) \({\rm..

Let \(p_n\) be the \(n\)th prime : \(2,\; 3,\; 5,\; 7,\; 11,\; \cdots,\) and let \(r\) be the remainder when \((p_n -1)^n + (p_n +1)^n\) is divided by \(p_n ^2\). For example, when \(n=3, \; p_3 = 5\), and \(4^3 + 6^3 = 280 \equiv 5\) mod \(25\). The least value of \(n\) for which the remainder first exceeds \(10^9\) is \(7037\). Find the least value of \(n\) for which the remainder first exceed..

The most naive way of computing \(n^{15}\) requires fourteen multiplications: \[ n \times n \times \cdots \times n = n^{15}\] But using a "binary" method you can compute it is six multiplications: \[\begin{split} n \times n &= n^2 \\ n^2 \times n^2 &= n^4 \\ n^4 \times n^4 &= n^8 \\ n^8 \times n^4 &= n^{12} \\ n^{12} \times n^2 &= n^{14} \\ n^{14} \times n &= n^{15} \end{split}\]However it is ye..