## 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); }

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 |

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 |

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

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 |