My Weblog

Blog about programming and math

Project Euler Problem 235

Problem Statement :-
Given is the arithmetic-geometric sequence u(k) = (900-3k)r^(k-1).
Let s(n) = Σ_(k=1…n)u(k).

Find the value of r for which s(5000) = -600,000,000,000.

Give your answer rounded to 12 places behind the decimal point.

If you notice the function then it is continious decreasing function ( if I remember my calculas days) so you can easily solve this problem binary search. Now the crux of the problem lies in the fact that what should be value of low and high.I often write programs in C/C++ so i had some experiment with some low and high value. First I chose low=1 and high=1000 and i completly messed with output so I wrote a program in Python to test value of low and high and i was amazed that value of function was 500 digit long number when input was 2. I decided to write a program in Pyhton and i got answer within a second. If you are curious to know the limits so my limit was lo=1.001999000000 and hi=1.002999000000. Now it is matter of simple binary search 🙂 ..

The value of function when r=2.0 is
-199115477520694888412659506759266289627304293815764761237225
609463277948402726478045313824136866823872851999842925696766
8726981505272498732522185805188443000607536912377746529870444
1609974216745569582043034637709397412088031109823747998448553
55671758999937658398764288691670085654835870832115119828213461
8293290664909036961871631670731032199014179744774522514941737
32241749630750454676214329480295775132463648051352728884331518
3975333181605489957952054846658340722269484296543631070758119
0852239594056973420623609518459032450092277471571074487315203
281803345383086408910468871286338252978071315407126900148544
495521349699618586678662660574635481030204946738319571316481
200120802396140032777007329713777544010672129449569871489341
241022057900605710333190193651527219317782863679280795743696
973981379893726733876776348894082338598665055608387786811387
8359259784025249745583076676821155292291210585632437909134407
104962533269578909780033873413400376653167685892027339037922
063328338936692933972123477902950298030272524770244037276214
1995093194230856587981776515573221428379693715933893908464346
2914218630665965118652861535982315104489049633342788603261419
001494356157103713998542329296695028766903756402004431994386
1778935288986215623692815957263782494931408519815151826542564
3531639167367473993399508011858130222159303124159750726591586
3656465258438502343507271578867991069307912043601450127365490
723249705963569239190357761752144543406890136501476102480211
7061349754576396769520117982888290241674659654346474375
Thnkx to python 🙂
Here is the c code


long double _eval(long double r)
	{
		long double sum=0;
		for(int i=1;i<=5000;i++)
		 sum+=(long double)(900.0-3.0*i)*pow(r,(long double)(i-1));
		//printf("r= %.12llf ",r);
		//printf("sum= %.12llf\n",sum);
		return sum;
	}

int main()
	{
		long double lo=1.001999000000,hi=1.002999000000;

		int cnt=0;
		while(cnt++<100)
		{
			long double mid=(lo+hi)*0.5;
			if(_eval(mid)<(-600000000000.0))hi=mid;
			else lo=mid;
		}
		printf("%.12llf\n",lo);
	}
Advertisements

March 17, 2009 - Posted by | Programming

5 Comments »

  1. I’m kind of shocked that you did a straight up brute force and it worked!

    I tried brute forcing this in python with binary search and got a reasonable value (1.00232..), but apparently its wrong since the website doesn’t accept my answer.

    For another attempt, on paper I did the mathematical simplification for an arithmetic-geometric series and ran binary rootfinding with that simplification. I got something almost the same, except differing in the 8th decimal place :/, apparently due to numerical issues? The Project didn’t like this one either.

    So, I simplified it even further by multiplying my already simplified expression by r^-5000 to make sure no terms get bigger than 1000 or so. Again, almost the same answer, but it was no go.

    How did you get it to work?!?

    Comment by maze | June 9, 2009 | Reply

    • If I remember correctly then there was some precession issue so look how to set it 12 place in python. There is no other catch in problem.If you want i can send you my python code.

      Comment by mukeshiiitm | June 9, 2009 | Reply

      • I’ve done this problem too and also get an answer of 1.00232… which is not accepted by project euler. I’ve used the Decimal package so precision shouldn’t be a problem.. 😦

        Comment by Nick | May 3, 2010

      • Hi Nick I don’t think there is any catch in problem.Its simple a matter of binary search.Above is the source code.

        Comment by tiwari_mukesh | May 3, 2010

  2. I think you are missing something.
    Here is my python code.

    def u(k, r):
    return (900 – 3*k) * pow(r, k – 1)

    lo = 1.001
    hi = 1.003
    eps = 1e-13
    tot = -600000000000

    while hi – lo > eps:
    r = (hi + lo) * .5
    s = sum(u(i,r) for i in xrange(1, 5001))
    if s < tot:
    hi = r
    else:
    lo = r

    print "%.13f" % r

    Comment by l0nwlf | March 19, 2011 | Reply


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: