Having to comment out loop for program to work correctly

Hey all, this is a problem on project euler #6. I did all of this code myself. With the for() loop comment removed the two printf() functions are resulting in wrong calculations (wrong). With the for() commented out the printf is resulting in the correct calculation for sum*sum (3025). also, i know to work the problem correctly I am going to need to set const int limit to 101; Here's problem on project euler ;);)

Code:

---

#include <stdio.h>


int main (void)
{
        int j, k;
        int i;
        const int limit = 11;       
        int squares_sum;
        int sum;


        /*
        for (j = 1; j < limit; j++)
        {
                // 1^2 + 2^2 + ... +10^2 = 385
                squares_sum = squares_sum += j*j;
        }


        printf("%d\n", squares_sum);
        */


        while (i < limit) // let i itierate limit times then print sum
        {
                // 1+2+3+4+5+6+7+8+9+10
                sum = sum += i;       
                i++; // loop while loop limit times
        }


        printf("%d", sum*sum); // sum^2


        printf("\n");


        return 0;
}

---

You need to initialize your sums to 0.

In your second loop (which for some reason you've made a while loop) you forgot to start i at 1.

This is wrong

Code:

---

sum = sum += i;

---

It's just

Code:

---

sum += i;

---

Similarly for the other use of +=.

Code:

---

#include <stdio.h>
 
int main()
{
    const long long limit = 100;
 
    long long sum_of_squares = 0;
    for (long long i = 1; i <= limit; ++i)
        sum_of_squares += i * i;
 
    // Or use the formula (if it doesn't overflow):
    //long long sum_of_squares = limit * (limit + 1) * (2 * limit + 1) / 6;
 
    printf("sum_of_squares: %9lld\n", sum_of_squares);
 
    long long sum = 0;
    for (long long i = 1; i <= limit; ++i)
        sum += i;
    // Or use the formula (if it doesn't overflow):
    //long long sum = limit * (limit + 1) / 2;
 
    long long square_of_sum = sum * sum;
 
    printf("square_of_sum : %9lld\n", square_of_sum);
 
    printf("difference    : %9lld\n", square_of_sum - sum_of_squares);
 
    return 0;
}

---

Code:

---

#include <stdio.h>


int main (void)
{
        long long j;
        long long i;
        const long long limit = 100;       
        long long squares_sum = 0;
        long long sum_squares = 0;


        for (j = 1; j <= limit; j++)
        {
                // 1^2 + 2^2 + ... +10^2 = 385
                squares_sum += j*j;
        }


        //printf("%lld\n", squares_sum);


        for (i = 1; i <= limit; i++)
        {
                // 1+2+3+4+5+6+7+8+9+10
                sum_squares += i;
        }
        sum_squares *= sum_squares;


        // printf("%lld\n", sum_squares);


        printf("Difference: %lld\n", sum_squares-squares_sum);


        printf("\n");


        return 0;
}

---

john.c, Should I do a calculation on my on my calculator (bc on linux or a generic calculator on a android smart phone) to prepare for the "long long" data type when seeing I will be getting a max value too big for the int to prevent a "overflow" that you mentioned? Someone a few days ago posted a limits.h program I ran and I saw the MAX range for each data type, I can find this on my post history here on the forum. Also, i learned the <= operator is letting me define limit as 100 instead of 100 therefore not using the < in the for loop. Thanks for clearing up the compound assignment operator issues, i will study these, and clearing up I needed to set the variables to '0'. Also instead of using a while and for loop as I did in my first program, now I know to just use two for loops as i believe this is why the program was getting confused. I've read in my book about the difference and similarities and why to choose one or the other.

I believe my code gets the right answer, I don't have access to my bookmarks at current computer but looks familiar.

Your code does get the correct answer.
There's no reason to worry about overflow with limit set to 100, alghouth if it was necessary you can calculate it using the forumula for the sum of numbers from 1 to Limit and the quadratic formula.

But you shouldn't declare all your variables at the top of a function.
I might write it more like this:

Code:

---

#include <stdio.h>
 
typedef unsigned long long ull;
 
int main()
{
    const ull Limit = 100;   
 
    ull squares_sum = 0;
    // 1**2 + 2**2 + 3**2 + ... + Limit**2
    for (ull i = 1; i <= Limit; ++i)
        squares_sum += i * i;
 
    //printf("%llu\n", squares_sum);
 
    ull sum_square = 0;
    // 1 + 2 + 3 + ... + Limit
    for (ull i = 1; i <= Limit; i++)
        sum_square += i;
    sum_square *= sum_square;
 
    //printf("%llu\n", sum_square);
 
    printf("%llu\n", sum_square - squares_sum);
 
    return 0;
}

---

And here's the way to do it using formulas instead of loops.
I calculated the highest Limit that won't overflow an unsigned 64-bit value.

Code:

---

#include <stdio.h>
 
#define FORMAT "%20llu"
typedef unsigned long long ull;
 
int main()
{
    const ull Limit = 92681; // as high as we can go using 64-bit unsigned
 
    ull sum = Limit * (Limit + 1) / 2;
    ull sum_of_squares = sum * (2 * Limit + 1) / 3;
    ull square_of_sum = sum * sum;
 
    printf("sum_of_squares: "FORMAT"\n", sum_of_squares);
    printf("sum          : "FORMAT"\n", sum);
    printf("square_of_sum : "FORMAT"\n", square_of_sum);
    printf("difference    : "FORMAT"\n", square_of_sum - sum_of_squares); 
 
    return 0;
}

---

For reference, the concepts this question relies on are:

(a) sum of consecutive natural numbers
(b) triangle numbers and the sum of consecutive triangle numbers (this is because the formula for concept (c) can be derived from the triangle number equation)
(c) square numbers and the sum of consecutive square numbers (see Square number - Wikipedia)

The equation for (a) is (n * (n + 1)) / 2
The equation for (c) is (n * (n + 1) * (2 * n + 1)) / 6

Using pen and paper you can arrive at solution = (n * (n * n - 1) * (3 * n + 2)) / 12 or come up with other intermediate equations to maximise, how big an answer you can get given the size of, say, unsigned long ( by keeping the numerator as small as possible, for example, as john.c has apparently done). That said, if I was writing a program for this problem I think I'd keep the calculations simple and do it in steps like john.c has because that results in code that's more self-documenting.

Reading:

1 + 2 + 3 + 4 + ⋯ - Wikipedia
Triangular number - Wikipedia
Square number - Wikipedia

Quote:

---

Originally Posted by Hodor

For reference, the concepts this question relies on are:

(a) sum of consecutive natural numbers
(b) triangle numbers and the sum of consecutive triangle numbers (this is because the formula for concept (c) can be derived from the triangle number equation)
(c) square numbers and the sum of consecutive square numbers (see Square number - Wikipedia)

The equation for (a) is (n * (n + 1)) / 2
The equation for (c) is (n * (n + 1) * (2 * n + 1)) / 6

Using pen and paper you can arrive at solution = (n * (n * n - 1) * (3 * n + 2)) / 12 or come up with other intermediate equations to maximise, how big an answer you can get given the size of, say, unsigned long ( by keeping the numerator as small as possible, for example, as john.c has apparently done). That said, if I was writing a program for this problem I think I'd keep the calculations simple and do it in steps like john.c has because that results in code that's more self-documenting.

Reading:

1 + 2 + 3 + 4 + ⋯ - Wikipedia
Triangular number - Wikipedia
Square number - Wikipedia

---

thanks for the response Hodor

Quote:

---

Originally Posted by _jamie

thanks for the response Hodor

---

You're welcome. I guess I should have also mentioned that there is nothing "wrong" with your approach, especially for all the PE problems rated at 5% difficulty. All the 5% problems can be brute forced AFAIK (and at least one that I know of has to be brute forced). I guess I expanded on what john.c wrote because lots of the later PE problems cannot be brute forced (or cannot be brute forced in a reasonable amount of time; I admit that I "cheated" on at least one and let the computer run overnight hehe but in general the 1 minute rule should be observed otherwise the only one you're cheating is yourself). I don't know how much programming and mathematics experience you have so keep implementing the way you've been doing them, because so far there is nothing wrong with your approach, but I think it's useful to always ask yourself "is there a better or other way I can solve this". You're gaining experience no matter what your current experience is just by working on problems in your own way, so keep it up. Even if you cannot solve a particular problem (and there are lots of PE problems I've skipped over because I didn't -- or still don't -- have the experience) you're still gaining experience just by attempting a problem even if you don't solve it.

Quote:

---

Originally Posted by Hodor

You're welcome. I guess I should have also mentioned that there is nothing "wrong" with your approach, especially for all the PE problems rated at 5% difficulty. All the 5% problems can be brute forced AFAIK (and at least one that I know of has to be brute forced). I guess I expanded on what john.c wrote because lots of the later PE problems cannot be brute forced (or cannot be brute forced in a reasonable amount of time; I admit that I "cheated" on at least one and let the computer run overnight hehe but in general the 1 minute rule should be observed otherwise the only one you're cheating is yourself). I don't know how much programming and mathematics experience you have so keep implementing the way you've been doing them, because so far there is nothing wrong with your approach, but I think it's useful to always ask yourself "is there a better or other way I can solve this". You're gaining experience no matter what your current experience is just by working on problems in your own way, so keep it up. Even if you cannot solve a particular problem (and there are lots of PE problems I've skipped over because I didn't -- or still don't -- have the experience) you're still gaining experience just by attempting a problem even if you don't solve it.

---

Thanks for the support and encouragement

Quote:

---

Originally Posted by Hodor

You're welcome. I guess I should have also mentioned that there is nothing "wrong" with your approach, especially for all the PE problems rated at 5% difficulty. All the 5% problems can be brute forced AFAIK (and at least one that I know of has to be brute forced). I guess I expanded on what john.c wrote because lots of the later PE problems cannot be brute forced (or cannot be brute forced in a reasonable amount of time; I admit that I "cheated" on at least one and let the computer run overnight hehe but in general the 1 minute rule should be observed otherwise the only one you're cheating is yourself). I don't know how much programming and mathematics experience you have so keep implementing the way you've been doing them, because so far there is nothing wrong with your approach, but I think it's useful to always ask yourself "is there a better or other way I can solve this". You're gaining experience no matter what your current experience is just by working on problems in your own way, so keep it up. Even if you cannot solve a particular problem (and there are lots of PE problems I've skipped over because I didn't -- or still don't -- have the experience) you're still gaining experience just by attempting a problem even if you don't solve it.

---

Hodor, please, what do you mean "brute force" (method) for the 5% difficulty Euler problems? What is this referred to as? Thanks!

Quote:

---

Originally Posted by _jamie

Hodor, please, what do you mean "brute force" (method) for the 5% difficulty Euler problems? What is this referred to as? Thanks!

---

Edit: the 5% project euler problems are those that are rated at 5% difficulty. I guess this means that are easy. They can all be solved using brute force (exhaustive calculation) as far as I know. The harder problems can't because they take too long


Brute force: Basically it means calculating every single step without using any shortcuts.

For example, and keeping with the theme of this thread, to sum the natural numbers <= 100 a brute force approach iterates over each number and adds them to a result. E.g.

Code:

---

/* untested */

/* Find the sum of natural numbers <= N; i.e. 1 + 2 + 3 ... + N
 * Brute force method... iterate over every number.
 */
unsigned long sumNaturalNums(size_t N)
{
    unsigned long sum = 0;
    for (size_t i = 1; i <= N; i++)
        sum += i;
    return sum;
}

---

The brute force method, above, for this is going to be pretty fast anyway but say N was 4 billion (for the sake of explanation assume that the sum of the first 4 billion natural numbers will fit into an unsigned long) the code above has to loop 4 billion times.

An approach that is not brute force might be

Code:

---

unsigned long sumNaturalNums(size_t N)
{
    return N * (N + 1) / 2;  // Ignore that N is size_t and the function is returning an unsigned long... this is just an example
}

---

This uses mathematics to arrive at the solution in one step. It doesn't step over every single number and it will get the result for N = 4 billion, in effect, instantly. Both the above functions give the same answer... the second is quite a lot faster though

Brute-force search - Wikipedia
Proof by exhaustion - Wikipedia

Comparing the brute force and the smarter solution for an input of 4 billion:
* the first does 4 billion additions to sum, 4 billion increments of i, 4 billion comparisons, and 4 billion jumps back to the beginning of the loop; so about 16 billion operations.
* the second does 3 (an addition, a multiplication, and a division).

Quote:

---

Originally Posted by Hodor

Using pen and paper you can arrive at solution = (n * (n * n - 1) * (3 * n + 2)) / 12

---

I didn't even think of boiling it down to a single equation. That's pretty nifty. As written it will overflow at a lower value (49796), which I guess is an advantage of doing it in pieces. Your equation can be broken down into pieces to make it work for the same limit:

Code:

---

#include <stdio.h>
 
typedef unsigned long long ull;
 
int main()
{
    const ull n = 92681;
 
    ull x = n;
    ull y = n * n - 1;
    ull z = 3 * n + 2;
 
    if (x % 2 == 0) { x /= 2; z /= 2; }
    else              y /= 4;
 
    if (x % 3 == 0)  x /= 3;
    else              y /= 3;
 
    printf("%llu\n", x * y * z);
 
    return 0;
}

---

The limit of 92681 can be calculated like this:

Code:

---

s = (n * (n + 1)) / 2
2s = n**2 + n
0 = n**2 + n - 2s    (quadratic form)
 
answer = s * s
So s can't go above sqrt(2**64) = 2**32 = 4294967296 (actually, one less)
 
0 = n**2 + n - 2(4294967295)
 
In the quadratic formula
a = 1
b = 1
c = -8589934590
 
(-b +- sqrt(b**2 - 4*a*c)) / (2 * a)        (quadratic formula)
(-1 +- sqrt(1 - -34359738360)) / 2
(-1 +- sqrt(34359738361)) / 2
(-1 + 185363) / 2  (only + of +- makes sense)
185362 / 2
92681

---

Quote:

---

Originally Posted by john.c

Comparing the brute force and the smarter solution for an input of 4 billion:
* the first does 4 billion additions to sum, 4 billion increments of i, 4 billion comparisons, and 4 billion jumps back to the beginning of the loop; so about 16 billion operations.
* the second does 3 (an addition, a multiplication, and a division).

---

Yeah, that's a good way of expressing it as well. I have to admit I was a little lost for words and my explanation is a bit lacking. I often use methods to narrow down the range of possibilities and then brute force the last stretch (better to brute force over a few thousand numbers than 4 billion). I guess algorithm choice is related (or the same?) as well. I.e. a brute force search will check every item but that's not necessary depending on the data and the algorithm.

Quote:

---

Originally Posted by john.c

I didn't even think of boiling it down to a single equation. That's pretty nifty. As written it will overflow at a lower value (49796), which I guess is an advantage of doing it in pieces. Your equation can be broken down into pieces to make it work for the same limit:

Code:

---

#include <stdio.h>
 
typedef unsigned long long ull;
 
int main()
{
    const ull n = 92681;
 
    ull x = n;
    ull y = n * n - 1;
    ull z = 3 * n + 2;
 
    if (x % 2 == 0) { x /= 2; z /= 2; }
    else              y /= 4;
 
    if (x % 3 == 0)  x /= 3;
    else              y /= 3;
 
    printf("%llu\n", x * y * z);
 
    return 0;
}

---

The limit of 92681 can be calculated like this:

Code:

---

s = (n * (n + 1)) / 2
2s = n**2 + n
0 = n**2 + n - 2s    (quadratic form)
 
answer = s * s
So s can't go above sqrt(2**64) = 2**32 = 4294967296 (actually, one less)
 
0 = n**2 + n - 2(4294967295)
 
In the quadratic formula
a = 1
b = 1
c = -8589934590
 
(-b +- sqrt(b**2 - 4*a*c)) / (2 * a)        (quadratic formula)
(-1 +- sqrt(1 - -34359738360)) / 2
(-1 +- sqrt(34359738361)) / 2
(-1 + 185363) / 2  (only + of +- makes sense)
185362 / 2
92681

---

---

Thanks for the programs and making it work for the same limit. I didn't intend to boil it down to a single equation but I was scribbling on paper and got carried away :) I think I'd approach it the way you originally did... easier to make things fit (and maybe the sum of natural numbers could be a reusable function whereas my single equation has a pretty narrow range of uses... probably just one use :P)