Problem 006

ABC_TheCMan · Post by **ABC_TheCMan** » Sun Jul 26, 2009 9:11 pm

Hi,

the problems ask for
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
But is should be:
Find the difference between the square of the sum of the first one hundred natural numbers and the sum of the squares?

Did anybody hit the same problem?

ABC_TheCMan

daniel.is.fischer · Post by **daniel.is.fischer** » Sun Jul 26, 2009 9:37 pm

Fortunately, the example makes it clear that the desired answer is the absolute difference.
But yes, that irritated me, too.

userProjectEuler · Post by **userProjectEuler** » Mon Aug 10, 2009 6:16 am

the problem is asking:

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

which results in a negative value.
the problem should be reformulated to:
Find the difference between the square of the sum of the first one hundred natural numbers and the sum of the squares.

right?!!

genious999 · Post by **genious999** » Mon Aug 10, 2009 6:56 am

"Difference" in that context means find the absolute difference
see here:
viewtopic.php?f=50&t=1614

userProjectEuler · Post by **userProjectEuler** » Mon Aug 10, 2009 5:57 pm

I didn't understand why in that context it means absolute difference. :/

quilan · Post by **quilan** » Mon Aug 10, 2009 6:50 pm

userProjectEuler wrote:the problem is asking:

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
which results in a negative value.
the problem should be reformulated to:
Find the difference between the square of the sum of the first one hundred natural numbers and the sum of the squares.

right?!!

result = abs( SquareOfSum(100) - SumOfSquares(100) )

If there was any ambiguity, the example should be enough to show that the answer should be positive.

userProjectEuler · Post by **userProjectEuler** » Mon Aug 10, 2009 7:32 pm

quilan wrote:
userProjectEuler wrote:the problem is asking:

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
which results in a negative value.
the problem should be reformulated to:
Find the difference between the square of the sum of the first one hundred natural numbers and the sum of the squares.

right?!!
result = abs( SquareOfSum(100) - SumOfSquares(100) )

If there was any ambiguity, the example should be enough to show that the answer should be positive.

there's no ambiguity. the problem is asking a different thing. there's nothing mentioning that the result must be unsigned. but that is ok.

drsparky · Post by **drsparky** » Fri Aug 14, 2009 12:52 pm

I deleted my solution... apparently this is not the correct place. The forum in the puzzle is locked. That is so unfortunate. I was rather happy with my O(1) solution...

hk · Post by hk » Fri Aug 14, 2009 1:21 pm

The second and fourth post in the forum are O(1) too.
Please read the forum first.

drsparky · Post by **drsparky** » Fri Aug 14, 2009 4:44 pm

Mine was different than both. Please don't be so condescending.

daniel.is.fischer · Post by **daniel.is.fischer** » Fri Aug 14, 2009 7:31 pm

I doubt your solution will be fundamentally different from all posted variations of the sum formulae, but to check, could you please PM me your solution?

zwuupeape · Post by **zwuupeape** » Sat Aug 15, 2009 11:05 am

You can solve every problem in O(1).

Let x be the solution to problem y. In pseudocode:

### O(1) algorithm to solve problem y:
### t <- x
### output t

stijn263 · Post by **stijn263** » Mon Aug 17, 2009 1:33 pm

Actually, that solution is at least O( log x )

zwuupeape · Post by **zwuupeape** » Mon Aug 17, 2009 7:36 pm

...what? How so? This program is O(1) by definition since its execution time is independent of input (it has no input) and it obviously halts.

daniel.is.fischer · Post by **daniel.is.fischer** » Tue Aug 18, 2009 3:25 pm

How long does it take to output x (hint: if x is an integer, it has O(log |x|) digits

)

zwuupeape · Post by **zwuupeape** » Wed Aug 19, 2009 2:34 pm

daniel.is.fischer wrote:How long does it take to output x (hint: if x is an integer, it has O(log |x|) digits )

x is a constant, therefore log|x| is a constant...

elendiastarman · Post by **elendiastarman** » Wed Aug 19, 2009 4:15 pm

But not <=1 unless x only has one digit...

zwuupeape · Post by **zwuupeape** » Wed Aug 19, 2009 4:56 pm

O( 10^9999999999999999) = O(1)

elendiastarman · Post by **elendiastarman** » Wed Aug 19, 2009 5:42 pm

I think his point is that it will take longer to output a 100 digit answer rather than a 2 digit answer.

zwuupeape · Post by **zwuupeape** » Wed Aug 19, 2009 6:30 pm

It's true that it will take longer, but it will also take longer if you have a slower computer... Running time is measured relative to input. The running time of this algorithm is indeed O(|logx|) but O(|logx|) = O(1). Actually I don't even understand what's O(logx) supposed to mean. O(logn) means that the running time of the algorithm takes twice as long to halt if the input is raised to the power of 2. if 12 is the solution and it has 2 digits then what is O(2) supposed to mean?

Project Euler Forum

Problem 006

Problem 006

Re: Problem 6 - Wrong question?

Problem 006 error

Re: Problem 6 error

Re: Problem 6 error

Re: Problem 6 error

Re: Problem 6 error

Problem 006 solution in O(1)

Re: Problem 6 solution in O(1)

Re: Problem 6 solution in O(1)

Re: Problem 6 solution in O(1)

Re: Problem 6 solution in O(1)

Re: Problem 6 solution in O(1)

Re: Problem 6 solution in O(1)

Re: Problem 6 solution in O(1)

Re: Problem 6 solution in O(1)

Re: Problem 6 solution in O(1)

Re: Problem 6 solution in O(1)

Re: Problem 6 solution in O(1)

Re: Problem 6 solution in O(1)