Thread: project Euler

im getting back to learning c so doing some project euler questions. Are they all such huge numbers why go for an answer in the 10's of millions if not bigger. The last one i have just done was work out which triangular number had over 500 multiples. it took 8 min 50 seconds to compute because i had to count from 100 to 12375 dividing each triangular number calculated by its self down to 1.

My point is why not calculate the number with 20 multiples or better yet 10 why 500!!

is there a better source of simple problems to practice with

many thanks
coop

thanks for the response. It occurred to me this morning after reading your reply that maybe finding the factors of a number could be done recursively.

after several hours reading up on recursion and trying different things all i have achieved is a dent in the wall and a flat spot on my skull.

i found this code on the internet

Code:

int factors(int n, int i)
{
    int count = 0;
    // Checking if the number is less than N
    if (i <= n)
    {
        if (n % i == 0)
        {
            count += 1;
        }

        // Calling the function recursively
        // for the next number
        return count + factors(n, i + 1);
    }
    return count;
}

but playing with it and stepping through the code line by line all it does is count from 1 to n+1 where the for loop beaks and then back down again to 1. I don't understand how that saves time infact as i was counting from n down to 1 and trying each individual number the above function does twice the work surly

many thanks
ben

here is the link #12 Highly divisible triangular number - Project Euler

this is the code i have so far however it causes a seg fault when base hits 591

Code:

#include <stdio.h>
#include <stdlib.h>

long long int factors( long long int, long long int );

int main()
{
    long long int iFactor = 0, iBase = 590;
    long long int iTrinum = 174345;
    
    //loop untill ifactor is greater than 140
    while ( iFactor <= 140 )
    {
        //increment base by 1
        iBase += 1;
        //add the value of ibase to the running total of itrinum
        iTrinum += iBase;
        //calculate the number of factors of trinum
        iFactor = factors( iTrinum, 1 );
        printf("triangular number = %lld and no. of factors is %lld\n\n", iTrinum, iFactor);
    }
    //print the triangular number that has over 500 factors
    printf(" triangular number %lld has %lld factors\n", iTrinum, iFactor);

    return 0;
}

long long int factors( long long int n, long long int i )
{
    long long int count = 0;
    // Checking if the number is less than N
    if (i <= n)
    {
        if (n % i == 0)
        {
            count += 1;
        }

        // Calling the function recursively
        // for the next number
        return count + factors(n, i + 1);
    }
    return count;
}

the function i wrote last night that took nearly 10 mins was

Code:

int NumofDivisors( int x )
{
    //declare function variables
    int i, iDivisorCount = 0;

    //loop counting down from x to 1
    for ( i = x; i >= 1; i-- )
    {
        //test if x is divisable by i
        if ( x % i == 0 )
        {
            //i is a multiple of x so increment idivisorcount by 1
            iDivisorCount += 1;
        }
    }

    //return the number of multiples found
    return iDivisorCount;
}

i take it i'm barking up the wrong tree then with recursion.

Originally Posted by cooper1200

ok now i am completely confused.

to recap some fundamentals....

Code:

x *= y  /*same as*/ x = x * y

order of operations is * / + -

so how the hell can....

Code:

int x = 2, y = 2;

x *= y + 1 == 6 /*not*/ 5!!!

Calc right hand side, (y+1) then multiply the left hand side by that value.

I am going to give that puzzle a try... long time sicne I did any project Euler.

Originally Posted by john.c

Code:

x *= y  /*same as*/ x = x * y

Nope

Code:

x *= y /*is the same as*/ x = x * (y)

So

Code:

x *= y + 1 /*is the same as*/ x = x * (y + 1)

The number of factors can be calculated by finding only the prime factors then multiplying the exponents of the prime factors (i.e., how many times they occur) plus one together. E.g., if the number is 360 = 2*2*2*3*3*5 then the number of factors is 4 * 3 * 2 = 24.

Code:

#include <stdio.h>
 
int main() {
    // Loop through triangular numbers
    for (int i = 1, n = 1; ; n += ++i) {
        int m = n, nfacts = 1, cnt = 0;
 
        // Calculate number of factors
        for (int d = 2; m > 1; ) {
            if (m % d == 0) {
                ++cnt;
                m /= d;
            }
            else {
                nfacts *= cnt + 1;
                cnt = 0;
                ++d;
            }
        }
        nfacts *= cnt + 1;
 
        if (nfacts >= 500) {
            printf("%5d %8d %5d\n", i, n, nfacts);
            break;
        }
    }
 
    return 0;
}

You are double-counting some 'degenerate' solutions.

Result: the 12375th triangular number, 76576500, has 576 factors.

The 'x'th triangular numbers have the formula (x)(x+1)/2. You want both (x+1) and x to have lots of unique prime factors as this will give x(x+1)/2 to have lots of factors.

Using this knowledge you can filter candidates, and you only need to work with numbers less than x+1.

Pick a hopeful value for x,
factorize x and x-1,
remove a factor of '2' from one of those,
see how many unique combinations of the factors are left.

Then also test x and x+1.

Originally Posted by john.c

Mine is quite a bit faster.

Had another hack at it...

Code:

$ time ./a
The 560th triangular number 157080 has 128 factors
The 2079th triangular number 2162160 has 320 factors
The 12375th triangular number 76576500 has 576 factors
The 41040th triangular number 842161320 has 1024 factors
The 313599th triangular number 49172323200 has 2304 factors
gcc -o bThe 1890944th triangular number 1787835551040 has 4480 factors


real    0m9.750s
user    0m9.751s
sys     0m0.000s

$ time ./john-c
1890944 1787835551040 4480


real    15m21.553s
user    15m21.543s
sys     0m0.010s

It's a little bit more code, but works pretty well:

Code:

The 560th triangular number 157080 has 128 factors
The 2079th triangular number 2162160 has 320 factors
The 12375th triangular number 76576500 has 576 factors
The 41040th triangular number 842161320 has 1024 factors
The 313599th triangular number 49172323200 has 2304 factors
The 1890944th triangular number 1787835551040 has 4480 factors
The 10497024th triangular number 55093761676800 has 8640 factors
The 37425024th triangular number 700316229412800 has 16128 factors
The 302464799th triangular number 45742477468287600 has 34560 factors