I was given the following question in an interview...
Compute the following sum:
1/2 + 1/4 + 1/8 + ... + 1/1048576
I was told that this was a logic question and they weren't looking for the source code, however my answer was the following...
private static double computeSum(){
double x = 0.0;
for(double i=2; i<=1048576; i*=2){
x += (1 / i);
}
return x;
}
What is the correct logical answer to this question?
I fi was presented with that sum I would say the answer is 1 minus the nth term, so in your case it's
1 - 1/1048576 = 1048575/1048576
I wouldn't do any maths or code or anything. I guess that's the kind of answer they were looking for.
I might show some "working" by saying 1/2 + 1/4 = 3/4 = 1 - 1/4; // Edit here
1/2 + 1/4 + 1/8 = 7/8 = 1 - 1/8
The sum:
1/2 + 1/4 + 1/8 + ... + 1/1048576
is equivalent to:
(1 + 2 + ... 2 ^ 20) / (2 ^ 20) - 1 =
(2 ^ 21 - 1) / (2 ^ 20) - 1 =
2 - 1 / (2 ^ 20) - 1 =
1 - 1 / (2 ^ 20) ~= 0.99999
The sum will tend to one if the length of the series is increased.
They are adding fractions together until they come up with a fraction 1/1048576 which has a very negligible value. This means that the answer to the above will be very close to 1 but not exactly one.
This is a simple convergent geometric series
s=a+ar+ar^2+ar^3+... to infinity
So the sum is
s=1/(1-r) where in this case r =1/2
However, we are seeking s-a, since the given series starts at 1/2 and not at 1. hence
s-a = 1/(1-r) - a = 1/(1-1/2) -1 = 1.
Why they call it a logic problem is not clear to me, except that they may want an explanation why the given geometric series converges -- which is a simple proof: i.e. the ratio between any two consecutive terms is a constant less than 1.
