Author Topic: Project Euler  (Read 120711 times)

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1829
Project Euler
« on: 一月 16, 2008, 01:18:36 pm »
This Project Euler is a fun event. Now, it has 177 computational problems that require a program to solve. Your job is to write a program and get the answer. Some of them are very easy, one line of MATLAB code. Some of them are tricky, such as find the sum of the digits in 2^1000; Some of them are really hard. If you can solve 60 or so problems, you will be on the top 1000. Here's the link

Project Euler

I have only tried (and solved) the first 15 problems. Haven't tried the others yet, welcome to discuss any of the problems here.

Dr Kevin Wang

  • Full Member
  • ***
  • Posts: 129
    • Math Zoom - Transform Gifited Youth into Successful Leaders
    • Email
Re: Project Euler
« Reply #1 on: 一月 19, 2008, 12:30:54 am »
I solved 21 of them so far, now I'm 12% genius :)

I googled #14. All the others are done by hand or a matlab program.  Some of the remaining ones could be easily done by programs, but I didn't have time to work on them.
« Last Edit: 一月 19, 2008, 12:32:38 am by SiYue »

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1829
Re: Project Euler
« Reply #2 on: 一月 19, 2008, 12:52:12 am »
Quote
I solved 21 of them so far, now I'm 12% genius

I googled #14. All the others are done by hand or a matlab program.  Some of the remaining ones could be easily done by programs, but I didn't have time to work on them.

I spent two evenings and solved the first 25 problems, then, some scattered later problems. e.g. if you solve No. 18, you can solve No. 67, it's the same problem, just bigger size. And I really like my solution to this problem.

I think I have solved total of 32 so far. All of them are done by MATLAB. #14 can be done by MATLAB quickly. Most of them are interesting, but some of them are tedious.


万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1829
Re: Project Euler
« Reply #3 on: 一月 22, 2008, 11:55:59 am »
It was a holiday yesterday. After taking my daughter to ski, I still had two hours to kill in the evening. I solved another 11 problems, I am now 24% genius according to that site. :)

Dr Kevin Wang

  • Full Member
  • ***
  • Posts: 129
    • Math Zoom - Transform Gifited Youth into Successful Leaders
    • Email
Re: Project Euler
« Reply #4 on: 一月 23, 2008, 01:43:16 am »
It was a holiday yesterday. After taking my daughter to ski, I still had two hours to kill in the evening. I solved another 11 problems, I am now 24% genius according to that site. :)
I was thinking of one problem a day; and you solved 11 in 2 hours??? You ARE a genius.  :-o
Anyway, I solved 29 so far, ranking 16%.
Some of my programs run about an hour. For example, I developed a program to find the first 100000 prime numbers, which will be used to solve some of the problems.  The primes are stored in an array and are used to determine larger primes. I'm not sure if there are more efficient ways to do this. That program (MATLAB) took an hour to run. Maybe it's because my computer's not fast enough (1.73GHz). Or maybe it's the environment---not really MATLAB, but GNU OCTAVE. I'm sure Java or C++ can run better, but can they do it in seconds? I have not tried perl; it should be faster too.

It looks like you and I are the only one posting these days. People do not participate even with posted problems.


万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1829
Re: Project Euler
« Reply #5 on: 一月 23, 2008, 09:34:13 am »
Quote
I was thinking of one problem a day; and you solved 11 in 2 hours??? You ARE a genius.


The two hour is just the coding time. I've read many of the problems and have been thinking about them during my driving and meetings. The actual time is much more than two hours.

 
Quote
Anyway, I solved 29 so far, ranking 16%.

Do another 29, you will be on the top 1000 list. I have 48 now.

Quote
Some of my programs run about an hour. For example, I developed a program to find the first 100000 prime numbers, which will be used to solve some of the problems.  The primes are stored in an array and are used to determine larger primes. I'm not sure if there are more efficient ways to do this. That program (MATLAB) took an hour to run. Maybe it's because my computer's not fast enough (1.73GHz). Or maybe it's the environment---not really MATLAB, but GNU OCTAVE.


May be you did not use MATLAB efficiently. Almost all of my program for this project runs under one minute. I don't remember any one run more than 5 minutes. I have worked for the Mathworks (MATLAB) for more than 5 years, naturally, my MATLAB coding skill should be better. :)

Quote
I developed a program to find the first 100000 prime numbers, which will be used to solve some of the problems.


You don't need to do that. There is a function in MATLAB named PRIMES to do that for you.

a = primes(1300000);

will give you the first 100000 primes (a little more). It takes less than 0.1 seconds. BTW, I wrote this function when I worked in the MathWorks. :)


BTW, many of my code for this project are short (under 10 lines), some of them (more than 5) are actually just one or two lines. e.g. my solution for problem 29 is only two lines. i.e. two statements. Takes about 0.002 seconds to run. I can actually make it into just one statement if I want.

Quote
I'm sure Java or C++ can run better, but can they do it in seconds? I have not tried perl; it should be faster too.

Not really. If you use Java or C++, you have to write many things yourself, which may be slow.

Quote
It looks like you and I are the only one posting these days. People do not participate even with posted problems.

This is because people like FZY and ID94 are busy in the WenXueCity forum. When they come back, there will be more post. I think this project is really interesting, testing people's puzzle skill and programing skill both. Packman should be good at this.
« Last Edit: 一月 23, 2008, 09:36:11 am by 万精油 »

packman

  • Full Member
  • ***
  • Posts: 226
Re: Project Euler
« Reply #6 on: 一月 23, 2008, 12:08:08 pm »
This is because people like FZY and ID94 are busy in the WenXueCity forum. When they come back, there will be more post. I think this project is really interesting, testing people's puzzle skill and programing skill both. Packman should be good at this.

I am still alive but just don't have time. Only browse qqsh (and CND) during lunch time, seldom post anything.  :-(
简单==完美

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1829
Re: Project Euler
« Reply #7 on: 一月 24, 2008, 08:51:49 am »
I have solved some other ones last night. Now I have 61 under my belt (34% genius :) ). 把五星红旗插上了top 1000 list. :) . From now on, I will do one problem a day.


Dr Kevin Wang

  • Full Member
  • ***
  • Posts: 129
    • Math Zoom - Transform Gifited Youth into Successful Leaders
    • Email
Re: Project Euler
« Reply #8 on: 一月 26, 2008, 02:13:11 pm »
I am now at 26%, 47 solved. I stll got very slow performance from my programs, but sometimes I didn't wait for it to finish and just guessed that that was all I needed. And it worked, so I just killed the program and claimed victory :)

One major difficulty now is the number of divisors and Euler's phi function. Is there an quick way to compute them?I wrote 2 functions for number of divisors and sum of divisors, but they are slow.

Another problem now is to find 100 digits of square root. I can't find an algorithm to compute the square root digit by digit without relying on the digits already found.

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1829
Re: Project Euler
« Reply #9 on: 一月 28, 2008, 09:47:28 am »
Quote
I am now at 26%, 47 solved.


Good, you need 12 more to be on the 1000 list.

Quote
I stll got very slow performance from my programs, but sometimes I didn't wait for it to finish and just guessed that that was all I needed. And it worked, so I just killed the program and claimed victory


The only problem that I need to wait for a long time so far is the one about computing Euler Phi. But it turned out I don't need to compute it at all. I guess this is the one you are talking about.

Quote
One major difficulty now is the number of divisors and Euler's phi function. Is there an quick way to compute them?I wrote 2 functions for number of divisors and sum of divisors, but they are slow.

The only problem I see that needs to compute Euler's phi is problem 69 which asks you to find the max of n/phi(n) for n less than 1 million. It is very costly to compute phi (takes a couple of days to compute up to 1 million). However, we can almost prove that the number of unique factors determines the ratio, they more the higher. Thus, the obvious choice is to multiply all the small primes until it reaches one million. Which turns out to be the answer.

As for number of divisors, I desinged the following line (I am very fond of oneliner solutions)

prod(diff([0 find(diff([factor(n) 1e20]))])+1)

the above line will compute the number of divisors of n for any n. It can be a good puzzle for the readers of this forum to figure out why this line works.

For non-MATLAB users, here's some notes to understand the above line

FACTOR(N) list the factors of n in ascending order, e.g. factor(60) = 2 2 3 5

square bracket means to put two array together, e.g. a=[1 3 5]; b=[2 7]; then [a b] = 1 3 5 2 7

DIFF means to find the difference of the array, e.g. diff([3 2 5 7]) = -1 3 2

FIND means to find indices of the non-zero elements

PROD means to find the product of all the elembent together



Quote
Another problem now is to find 100 digits of square root. I can't find an algorithm to compute the square root digit by digit without relying on the digits already found.

The only way I see it is to do it like you do it by hand. i.e. get a size 100 vector and compute each digit one by one. I did it this way for computing the digits of the 1000th power of 2 (problem 16) and find all the digits of 100! (problem 20). It is no fun to write such a code. Thus I start to cheat for later problems. I use the symbolic tool box, which can do arbitary long digits computation. e.g. if you ask for the first 100 digits of sqrt(2), it will give you the first 100 digits of sqrt(2) in no time.
« Last Edit: 二月 03, 2008, 02:50:18 pm by 万精油 »

idiot94

  • Sr. Member
  • ****
  • Posts: 484
Re: Project Euler
« Reply #10 on: 一月 28, 2008, 03:54:57 pm »
I am both too busy and too silly to chase those problem, prof. W and Prof. S :)

I tried the first problem and then did not continue (but I did login... :) so at some point, I will try. I like this project very much)

Now you solved my long time puzzle, Prof. W ---- that is why you are so good at Matlab... You are absolutely THE most competent person with Matlab that I ever know :)
In general, the men of lower intelligence won out. Afraid of of their own shortcomings ... they boldly moved into action. Their enemies, ...  thought there was no need to take by action what they could win by their brains. Thucydides, History

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1829
Re: Project Euler
« Reply #11 on: 一月 29, 2008, 10:55:00 am »
Quote
Now you solved my long time puzzle, Prof. W ---- that is why you are so good at Matlab... You are absolutely THE most competent person with Matlab that I ever know


According to Chinese custom, when someone praises you, you should say "where, where ( 哪里, 哪里) :)". In this case, MATLAB programming happens to be one of the few things that I am proud of, I think the appropriate way to reply to your praise is: Thanks.

When I just came to Boston (10+ years ago), I met a guy who just came back from a ski trip (He happens to be one of the pioneers in Genetic programming field). This was not ordinary ski. He (and his friends) were not satisfied with ordinary ski, and hired a helicoptor to drop them off (with skii on) at the top of the mountain and go down from there (they do that every year). After I heard his description, I said: "You must be very good at ski". He looked at me in the eye and seriously said "I am THE best skier you will ever met in your life". From that moment, I realized that when you are proud of and confident about something, you can reply to a praise in a totally positive way. I guess I can say the same thing to you about my MATLAB programming. :), I will back up this claim with the following appendix.

Mathworks (MATLAB) hold a world wide MATLAB contest every year (or twice a year) for the past 10+ years. It is usually participated by several thousands of "best" MATLAB programmers in the world. When I worked in the MathWorks, we usually hold an internal contest (to test the problem, the scoring weight, etc.) before we put the problem out to the public contest. I have won the internal contest 3 years in a row, and my scores were usually better than the (later) public best scores. At that time, I could claim to be one of the top MATLAB programmers in the world. Now, my work does not rely on MATLAB (for many years), I cannot make that claim any more. :(

Now, back to the Project Euler. I agree this is a very interesting project, especially for people who love puzzles and knows how to program.

« Last Edit: 一月 29, 2008, 04:41:26 pm by 万精油 »

idiot94

  • Sr. Member
  • ****
  • Posts: 484
Re: Project Euler
« Reply #12 on: 一月 30, 2008, 12:50:39 am »
Wow ! I am extremely happy to read the story and your reply :)  I am proud of you!
(and proud of being able to tell others that I know such a person :) )...

I bet FZY will love to try out those problems in the project as well, provided he has the time.
In general, the men of lower intelligence won out. Afraid of of their own shortcomings ... they boldly moved into action. Their enemies, ...  thought there was no need to take by action what they could win by their brains. Thucydides, History

Dr Kevin Wang

  • Full Member
  • ***
  • Posts: 129
    • Math Zoom - Transform Gifited Youth into Successful Leaders
    • Email
Re: Project Euler
« Reply #13 on: 一月 30, 2008, 11:04:27 pm »
Quote
I am now at 26%, 47 solved.


Good, you need 12 more to be on the 1000 list.

62 now; got within 900.

Quote
The only problem I see that needs to compute Euler's phi is problem 69 which asks you to find the max of n/phi(n) for n less than 1 million. It is very costly to compute phi (takes a couple of days to compute up to 1 million). However, we can almost prove that the number of unique factors determines the ratio, they more the higher. Thus, the obvious choice is to multiply all the small primes until it reaches one million. Which turns out to be the answer.
In fact problem 72 is just the sum of the phi function up to 1 million. That was why I needed to compute it. With the factor function in matlab, I computed the phi function up to 1 million in a couple hours. I didn't know about "factor" until I saw your num of divisors line.


Quote
Quote
Another problem now is to find 100 digits of square root. I can't find an algorithm to compute the square root digit by digit without relying on the digits already found.

The only way I see it is to do it like you do it by hand. i.e. get a size 100 vector and compute each digit one by one. I did it this way for computing the digits of the 1000th power of 2 (problem 16) and find all the digits of 100! (problem 20). It is no fun to write such a code. Thus I start to cheat for later problems. I use the symbolic tool box, which can do arbitary long digits computation. e.g. if you ask for the first 100 digits of sqrt(2), it will give you the first 100 digits of sqrt(2) in no time.


I did the 100! and 2^1000 problems the same way. Also there is a problem about finding maximum digital sum for a^b (1<=a,b<=100).

Many people in the forum there used the big number capabilities of languages (Java, Python, Ruby, Mathematica ...), which I also regard as cheating :) A few solutions from other people did surprise me for their elegance.

Dr Kevin Wang

  • Full Member
  • ***
  • Posts: 129
    • Math Zoom - Transform Gifited Youth into Successful Leaders
    • Email
Re: Project Euler
« Reply #14 on: 一月 30, 2008, 11:13:54 pm »
Now you solved my long time puzzle, Prof. W ---- that is why you are so good at Matlab... You are absolutely THE most competent person with Matlab that I ever know :)
The reason I admire Prof. W so much is that he is at the very top at everything he does.
Even though I can also claim to be good at a few things, I never reached that level.