After solving about 20 of problems from Project Euler I have decided to choose more difficult problem. Maybe it is a bit too difficult, but yes – I have chosen the most difficult problem available in Project Euler.
I have already written first implementation of functions F and G, which has taken me almost 4 hours today morning. Both functions work correctly and return correct values, but they are not well optimized. Even though G(10) is calculated almost immediately and G(10^3) in about two seconds, calculation of G(10^4) takes 31 minutes and I am not even going to try with G(10^5).
My current implementation of function F uses two separate loops with a lot of divisions and a set of edges to avoid repetitions. This implementation cannot be used for final solution, but it gives correct answers so I am able to ensure that my future implementation works correctly. More details may be found here. I will describe everything more precisely when I solve the problem (hopefully it will happen).
I have spot some connections between the result of F and divisors of edges given. I am not quite sure if I should consider prime divisors and their exponents (e.g. 12 = 2^2 * 3) or maybe just a total number of divisors. The first approach seems to be more promising so now I will focus on this.
I have already implemented some structure for divisors finding – I have used the code from the problem 12, which I will describe later.
At this point I am sure that F(1, a) returns 1 – a & 1 for any a > 2, but I don’t think that this optimization will be enough to change anything…