My Weblog

Blog about programming and math

Project Euler Problem 207

import Data.List
import Data.Ratio
import Data.Bits

recur::Integer ->Integer
recur n | (%) ( truncate.logBase 2.fromIntegral $ n ) ( n - 1 ) < (%) 1 12345 = n 
	 | otherwise = recur ( n + 1 )

solve::Integer
solve = x^2 - x where 
	x = recur 2

main = print solve

Project Euler Problem 207 is really nice and cryptic problem. Most of time was spend to understand the problem statement. We can write the given equation 2^{2*t} - 2^t = K . Its given that 2^t is positive integer so K will be of form x^2 - x .When K will be power of 2 [ t will be positive integer ] then we have perfect partition. In short we have to find the \frac {\log_2 n } { n-1 } < \frac 1 {12345} .

Advertisements

June 22, 2011 - Posted by | Programming | , ,

No comments yet.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: