/prog/ - Project Euler

Name: Anonymous 2010-09-24 23:18

Hey /prog/, I know I'm a little late to the party, but I was wondering how many problems you've solved thus far.
Other discussion regarding Project Euler is also welcome!

Name: Anonymous 2010-09-25 23:03

>>39
>>40
Please include code tags using brackets in the same manner as other tags in BBCODE by inserting "code" in the brackets.

Name: Anonymous 2010-09-25 23:10

>>41
I understand C++ well, but BBcode will never make sense to me.
Heres my last one



#include <iostream>

#include <gmp.h>



using namespace std;

int sumdigs(mpz_t * num);

int main()

{

    mpz_t result;

    mpz_init(result);

    int best = 0;

    for(int a = 1; a < 101;a++)

    {

        for(int b = 1; b <101;b++)

        {

            mpz_ui_pow_ui(result,a,b);

           int temp = sumdigs(&result);

            if( temp > best)

            {

                best = temp;

            }





        }

    }

    cout<<best;

    return 0;

}

int sumdigs(mpz_t * num)

{



    char holder[202];

    mpz_get_str(holder,10,*num);

    int length = 0;

    int sum = 0;

    while(1)

    {

        if(holder[length] == 0)

        {

            break;

        }

        length++;

    }

    for(int i = 0; i < length;i++)

    {

        sum += holder[i] - 48;

    }

    return sum;

}

Name: Anonymous 2010-09-26 0:08

>>42
BBCODE is rather simple.
Put tags around shit to manipulate how it appears. Close tags like you would with braces in a programming language.

Name: Anonymous 2010-09-26 1:53

>>41
Please optimize your post references.

>>43
BBCODE's HTML-inspired verbosity means it doesn't work nearly as conveniently as just using }.

Name: Anonymous 2010-09-27 17:27

>>16
say [+] grep {$_ %% 2}, ( 0,1, { $^a + $^b } ...^ * > 4_000_000);

Name: Anonymous 2010-09-28 13:50

Problem 303
For a positive integer n, define f(n) as the least positive multiple of n that, written in base 10, uses only digits ≤2.

Thus f(2)=2, f(3)=12, f(7)=21, f(42)=210, f(89)=1121222.

Also sum_n=1^100 {f(n)/n} = 11363107

Find sum_n=1^10000 {f(n)/n}.
http://projecteuler.net/index.php?section=problems&id=303

f[n_] := FromDigits@IntegerDigits[n, 3]

Timing[Sum[For[i = 1, Mod[f[i], n] != 0, i++]; f[i]/n, {n, 100}]]

{0.206891, 11363107}

Above is a brute force that is really slow and inefficient. This is ok for some of the earlier problems, but not this one.

I was thinking using a some divisibility tests and modular arithmetic such as checking ending digits and adding blocks of digits described here http://webspace.ship.edu/msrenault/divisibility and here http://webspace.ship.edu/msrenault/divisibility/StupidDivisibilityTricks.pdf

Name: Anonymous 2010-09-28 14:28

>>46
Example for finding a multiple of 999 that fits the using only 0, 1, and 2 for digits criterion.

999 factors to 3³ × 37.

999 can be checked for divisibility by both 27 and 37 by summing the digits into blocks of 3 and checking their divisibility.

Because 999 is the LCM of 37 and 27, the lowest sum we are aiming for is 999.

{0, 1, 2, 10, 11, 12, 20, 21, 22, 100, 101, 102, 110, 111, 112, 120, 121, 122, 200, 201, 202, 210, 211, 212, 220, 221, 222}

So we get there using the fewest amount of digits and trying to aim for the smallest number possible using what we have above.

111 + 222 + 222 + 222 + 222 = 999

111,222,222,222,222 is the resulting number.

Name: Anonymous 2010-11-03 2:38

Name: Anonymous 2011-02-03 0:16

Newer Posts

Project Euler

1 Name: Anonymous 2010-09-24 23:18

41 Name: Anonymous 2010-09-25 23:03

42 Name: Anonymous 2010-09-25 23:10

43 Name: Anonymous 2010-09-26 0:08

44 Name: Anonymous 2010-09-26 1:53

45 Name: Anonymous 2010-09-27 17:27

46 Name: Anonymous 2010-09-28 13:50

47 Name: Anonymous 2010-09-28 14:28

48 Name: Anonymous 2010-11-03 2:38

49 Name: Anonymous 2011-02-03 0:16

50 Name: Anonymous 2011-03-10 17:47