Problem 338 (2)

Damn, this problem is really difficult!

There is something to do with parity of arguments in function F, but I haven’t solved what exactly yet. I know that if both arguments are odd, then the result is 0. I am also considering cases when one of the arguments is odd and the other is even and I have spotted that results repeat periodically. For given a, the period starts at b given below and looks as follows:

a = 1        b >= 4          [1]
a = 3        b >= 10        [2 ,3]
a = 5        b >= 14        [1, 2, 2, 2, 1, 3]
a = 7        b >= 18        [2, 1, 1, 3, 1, 1, 2, 2, 1, 2, 1, 2]
a = 9        b >= 26        [2, 3, 3, 4, 2, 3, 2, 5, 2, 3, 2, 4, 3, 3, 2, 4, 2, 4, 2, 4]

I have also spotted that periods are palindromic.

Anyway, even if I implemented a structure to remember periods and used already calculated values, I would have to do this for all a < 10^12, which may take A BIT more than one minute. I really would like to know how to solve this problem in a minute.

About Jaroslaw Pawlak

I have done MSci in Computer Science at King’s College London and currently work as Software Engineer specialising in Java. I spend most of my time in front of computer improving my programming (and other) skills or just relaxing with a good game. I also train some sports but at the moment I am not a member of any club. I love cycling and volleyball, but I have also played a lot of football, tennis and trained martial arts.

Posted on June 9, 2011, in Project Euler. Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: