Investigating Ulam sequences
I do not like this problem when I first tried to solve it simply because I googled a lot about this sequence and got a lot of information about it. Then I use some brute force method to solve it. It is fast, but I cheated. It took me 0.8 second.
Today, I read the discussion thread and find an algorithm that used bitset to solve this problem. I thought about it for some time, finally I understand why it works. Really amazing method! We can got the period and span with very simple code in a very short amount of time. It takes 60 ms to solve the whole problem!
I strongly recommend this problem! It is one of the most difficult problems in the first 200 problems. No wonder only 839 people solved it.
Showing posts with label bitset. Show all posts
Showing posts with label bitset. Show all posts
Sunday, May 12, 2013
Sunday, February 17, 2013
project euler problem 016
power digit sum
problem is simple. but a neat solution is not that easy.
There are many ways to solve this problem. mathematica, python, gmp, etc.
My first version also used my bigInteger class. But actually this is overkill.
One may use two bitset as carry and one vector to solve this problem. I learnt
this in the discussion thread.
problem is simple. but a neat solution is not that easy.
There are many ways to solve this problem. mathematica, python, gmp, etc.
My first version also used my bigInteger class. But actually this is overkill.
One may use two bitset as carry and one vector to solve this problem. I learnt
this in the discussion thread.
Subscribe to:
Posts (Atom)