Totient maximum ¶ Euler's Totient function, φ( n ) [sometimes called the phi function], is used to determine the number of numbers less than n which are relatively prime to n . For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6. n Relatively Prime φ( n ) n /φ( n ) 2 1 1 2 3 1,2 2 1.5 4 1,3 2 2 5 1,2,3,4 4 1.25 6 1,5 2 3 7 1,2,3,4,5,6 6 1.1666... 8 1,3,5,7 4 2 9 1,2,4,5,7,8 6 1.5 10 1,3,7,9 4 2.5 It can be seen that n =6 produces a maximum n /φ( n ) for n ≤ 10. Find the value of n ≤ 1,000,000 for which n /φ( n ) is a maximum. As we know that to find the value of Euler Totient Function $\phi(n)$ we can use the following formula: $$\phi(n) = n\prod_{i = 1}^{k}\left(1 - \frac{1}{p^k}\right)$$ Where $p_1, p_2, p_3.....p_k$ are the prime factors of a given number $n$. But if we had to generate prime factors for each and every number using brute force method would increase
Magic 5-gon ring ¶ Consider the following "magic" 3-gon ring, filled with the numbers 1 to 6, and each line adding to nine. Example magic 3-gon ring Working clockwise, and starting from the group of three with the numerically lowest external node (4,3,2 in this example), each solution can be described uniquely. For example, the above solution can be described by the set: 4,3,2; 6,2,1; 5,1,3. It is possible to complete the ring with four different totals: 9, 10, 11, and 12. There are eight solutions in total. Total Solution Set 9 4,2,3; 5,3,1; 6,1,2 9 4,3,2; 6,2,1; 5,1,3 10 2,3,5; 4,5,1; 6,1,3 10 2,5,3; 6,3,1; 4,1,5 11 1,4,6; 3,6,2; 5,2,4 11 1,6,4; 5,4,2; 3,2,6 12 1,5,6; 2,6,4; 3,4,5 12 1,6,5; 3,5,4; 2,4,6 By concatenating each group it is possible to form 9-digit strings; the maximum string for a 3-gon ring is 432621513. Using the numbers 1 to 10, and depending on arrangements, it is possibl