# 情趣生活

## 情趣生活 => 灵机一动 => Topic started by: 万精油 on 一月 16, 2008, 01:18:36 pm

Title: Project Euler
Post by: 万精油 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

I have only tried (and solved) the first 15 problems. Haven't tried the others yet, welcome to discuss any of the problems here.
Title: Re: Project Euler
Post by: Dr Kevin Wang 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.
Title: Re: Project Euler
Post by: 万精油 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.

Title: Re: Project Euler
Post by: 万精油 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. :)
Title: Re: Project Euler
Post by: Dr Kevin Wang 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.

Title: Re: Project Euler
Post by: 万精油 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.&nbsp; 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.
Title: Re: Project Euler
Post by: packman 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.  :-(
Title: Re: Project Euler
Post by: 万精油 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.

Title: Re: Project Euler
Post by: Dr Kevin Wang 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.
Title: Re: Project Euler
Post by: 万精油 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.
Title: Re: Project Euler
Post by: idiot94 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 :)
Title: Re: Project Euler
Post by: 万精油 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.

Title: Re: Project Euler
Post by: idiot94 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.
Title: Re: Project Euler
Post by: Dr Kevin Wang 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.
Title: Re: Project Euler
Post by: Dr Kevin Wang 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.
Title: Re: Project Euler
Post by: Dr Kevin Wang on 一月 30, 2008, 11:17:11 pm
I solved #176 and #179, and those still count as one each. I think they should have some kind of weight system and give more point for the harder problems.  For example, 1 point for problems 1-9, 2 points for problems 10-99, 3 points for problems 100+, etc.
Title: Re: Project Euler
Post by: 万精油 on 一月 31, 2008, 10:02:47 am
Quote
62 now; got within 900.

Great! One more MATLAB player in the top 1000. From the statistics, C/C++ wins by far. The next one is Python, which is just a free version of MATLAB (very similar to MATLAB, I heard).

Quote
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).

I think these are the only three problems I used that approach.

Quote
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.

Many C/C++ users will think MATLAB is cheating too. :). My view is that if I know how to do it in that approach, then I have proved I can do it,  I don't have to do it for every problem with the slow approach.

BTW, I didn't know there's a forum until you mentioned it. I went in and checked, it is a great forum, but where do people discuss these problems? There are quite a few subforums, which one do they use to discuss these problems?

I think they should have a contest on what is the shortest code for each problem. I may win a couple of problems for the shortest solution. :) I have four problem solutions under 30 charactors, and two of them under 15.

Quote
The reason I admire Prof. W so much is that he is at the very top at everything he does.

I wish this was true. The fact is that I suck at many things I do.

Quote
I solved #176 and #179, and those still count as one each. I think they should have some kind of weight system and give more point for the harder problems.  For example, 1 point for problems 1-9, 2 points for problems 10-99, 3 points for problems 100+, etc.

After I got on the top 1000, I started to do problems by their natural order. There is no reason for me to select later ones, since I will meet them later anyway. Now, I have solved every problem from 1 to 59, the next one will be No. 60.

My question is how do we get to the top? Suppose I solve all the problems some day, I will still be behind to those who solve those problems earlier.
Title: Re: Project Euler
Post by: Dr Kevin Wang on 一月 31, 2008, 11:27:23 am
Quote
62 now; got within 900.

Great! One more MATLAB player in the top 1000. From the statistics, C/C++ wins by far. The next one is Python, which is just a free version of MATLAB (very similar to MATLAB, I heard).

I marked myself as "Pencil/Paper" :)

Quote
BTW, I didn't know there's a forum until you mentioned it. I went in and checked, it is a great forum, but where do people discuss these problems? There are quite a few subforums, which one do they use to discuss these problems?
There's a forum where they DON'T discuss the problems? I didn't know that :)
I just clicked on the column to the right of the green checkmark. It will be the forum where people discuss how they solved the problem and show code.

Title: Re: Project Euler
Post by: 万精油 on 一月 31, 2008, 12:56:17 pm
Quote
I marked myself as "Pencil/Paper"

Then you are cheating when you use programs. :) .

Actually, many problems there needs to be tried out with pencil/paper first.

Quote
There's a forum where they DON'T discuss the problems? I didn't know that
I just clicked on the column to the right of the green checkmark. It will be the forum where people discuss how they solved the problem and show code.

Ahh, we are learning from each other. Very good. I didn't know the area right of the green checkmark was clickable. Now I know and will certainly take a look at some of the problems. That's a good way to communicate while not allowing people who haven't solved that problem to see them.

Now, here's the fun part. This project actually has a seperate forum where they discuss all sort of math problems, programming problems and so on. A very good site. I didn't know it exist until you mentioned some kind of discussion place in your post. I went and look and found it. I thought that's the one you were talking about. OK, here it is:

Project Euler forum (http://forum.projecteuler.net/)
Title: Re: Project Euler
Post by: 万精油 on 二月 01, 2008, 11:40:04 am
Quote
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.

I estimated it will take 2 days for my code to computer phi up to 1 million, and I don't have patient to wait for that long. So I get around it by not computing it (problem 69). However, problem 72 comes in, and I cannot avoid it any more. I designed a new approach, and now, my phi function can compute phi up to 1 million in about 5 minutes. Really happy.

Title: Re: Project Euler
Post by: Dr Kevin Wang on 二月 04, 2008, 03:04:45 am
My question is how do we get to the top? Suppose I solve all the problems some day, I will still be behind to those who solve those problems earlier.&nbsp;

If you solve all the problems, then when the next problem comes out you solve it first, then you will be on top.

Is there a way to prevent those spammers from posting?  (Filters, etc.)
Title: Re: Project Euler
Post by: 万精油 on 二月 04, 2008, 09:29:58 am
Quote
If you solve all the problems, then when the next problem comes out you solve it first, then you will be on top.

I thought that was the case, but the top one stays there after two new problems. So, I thought I was wrong until today when I noticed the top has changed after problem 180. Good, we have some hope. :)

When I solved 72 problems, I noticed a familar name among people who also solved 72 problems, i.e. supertramp. There used to be an active ID in this forum with that name, and from his post here, he's good in programming. I am almost certain that these two are the same person. I have sent him a note to the register email address, hopefully, he will come back to this forum to join discussion with us.

Quote
Is there a way to prevent those spammers from posting?  (Filters, etc.)

Not really, I always get rid of them by hand. Fortunately, we don't have them very often, once a week on average.
Title: Re: Project Euler
Post by: jeff_gao on 二月 05, 2008, 10:17:50 am
Haven't posted for a while, but I do read the forum regularly.

These problems interest me, so I set my goal to get into top 1000 before Super Tuesday. I did last night with 74 solved, rank 673 as of today!
Title: Re: Project Euler
Post by: 万精油 on 二月 05, 2008, 10:39:01 am
Hurray. Another Five Star Red Flag!

From what I can tell (from the first post of the first problem), this project has been there more than 3 years. I found out this project on January 14th, 2008, and gave the link here on January 16th (after I tried the first 15 problems and determined it was worth the effort). Now, 22 days later, I have solved 79 problems. An average of 3.6 problem a day. The problem is getting harder as we move along, it will not be possible to solve 3.6 problems each day. One problem a day might be manageable, but may not be true after another week.

Anyway, it is good to see more people are interested in this project. I am surprised FZY hasn't jumped in yet. He's very good in both puzzle solving and programming. This is exactly his cup of tea.

ID94, may be you can post a link in WenXueCity puzzle forum, and get more people interested.

Title: Re: Project Euler
Post by: fzy on 二月 05, 2008, 01:37:37 pm
I have been extremely busy the past couple of months, and may get more so now. I did come here regularly and read the posts, but do not have time for anything else. I also followed the link to the site, but decided not to register since I would not have the time to do much. May be some of us can form a group and collectively solve the problems. How about that, ID94?
Title: Re: Project Euler
Post by: idiot94 on 二月 06, 2008, 05:50:18 pm
Of course, my master! :)

If I team up with you and Prof. W and SiYue, LOL ... I do not have to anything, but my rank will be top 99% in no time :)

I believe my login name is
idiot94
my pwd is
XXXXXX
(project Euler, huh?:) )
Title: Re: Project Euler
Post by: 万精油 on 二月 06, 2008, 07:43:58 pm
Title: Re: Project Euler
Post by: idiot94 on 二月 06, 2008, 09:58:26 pm
Thanks a lot, Prof. W. I am too careless indeed. I will PM fzy on that. :)
Title: Re: Project Euler
Post by: shortstop on 二月 07, 2008, 10:07:18 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.

Title: Re: Project Euler
Post by: shortstop on 二月 07, 2008, 10:28:31 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.

Prof. W:

I spent 2 evenings on this and have solved 12 so far. As you mentioned, probs 18 & 67 are basically the same problem. I think the algorithm is pretty simple, however  I am kinda frustrated to get answers right. Would you just please check it for me.

Here is my code in Java:
int sum = data[0][0];
System.out.println("data[0][0] = " + data[0][0] + "--- sum = " + sum);
int i = 0;
for (int j = 1; j < index; j++) {
if (data[j] < data[j][i+1]) {
sum += data[j][i+1];
i++;
}
else {
sum += data[j];
}
System.out.println("data["+j+"]["+i+"] = " + data[j]+ "--- sum = " + sum);
}
System.out.println("the maximum sum traveling from the top of the triangle to the base is " +  sum);

For prob 18, index = 15 and output as follows
data[0][0] = 75--- sum = 75
data[1][0] = 95--- sum = 170
data[2][1] = 47--- sum = 217
data[3][2] = 87--- sum = 304
data[4][2] = 82--- sum = 386
data[5][3] = 75--- sum = 461
data[6][3] = 73--- sum = 534
data[7][3] = 28--- sum = 562
data[8][4] = 83--- sum = 645
data[9][4] = 47--- sum = 692
data[10][5] = 43--- sum = 735
data[11][5] = 73--- sum = 808
data[12][6] = 91--- sum = 899
data[13][6] = 67--- sum = 966
data[14][7] = 98--- sum = 1064
the maximum sum traveling from the top of the triangle to the base is 1064

Why 1064 isn't correct?

Thanks a lot!

shortstop.
Title: Re: Project Euler
Post by: 万精油 on 二月 07, 2008, 10:48:34 am
Quote
Would you just please check it for me.

Why 1064 isn't correct?

It is very hard to check other people's code, one has to get into the same kind of thinking first. I haven't looked at your code carefully. One thing I noticed is that you are going top down, which may be a mistake. A max path at the top level may end up to be not the max for the whole. e.g. if the bottom right corner has a huge number (bigger than the sum of everything else), if you work from top to bottom, any time you take a left, you will never reach that number. You should work bottom up, and it is very straight forward this way.

Title: Re: Project Euler
Post by: shortstop on 二月 07, 2008, 11:06:30 am
Quote
Would you just please check it for me.

Why 1064 isn't correct?

It is very hard to check other people's code, one has to get into the same kind of thinking first. I haven't looked at your code carefully. One thing I noticed is that you are going top down, which may be a mistake. A max path at the top level may end up to be not the max for the whole. e.g. if the bottom right corner has a huge number (bigger than the sum of everything else), if you work from top to bottom, any time you take a left, you will never reach that number. You should work bottom up, and it is very straight forward this way.

I got you. You are the best!
Thanks a lot!
Title: Re: Project Euler
Post by: 万精油 on 二月 11, 2008, 08:46:12 am
Got another 10 problems this weekend, now I have solved 94. One problem a day this week, I will break 100 by the end of this week.

I like this project more and more. As Siyue pointed out to me, once you solve a problem, the discussion board of that problem opens to you and you can see other people's idea and code. Very interesting. I don't have much time to read them, but for the problems that I spent quite some time, I would read other people's solution and find out the differece between their code and my code.

One bad thing (or interesting thing, depends on your point of view) that I just found out yesterday is that there is a programming language website posted all the solutions for problem from 1 to 40 (their reason is to prove that their language is powerful). Many people are mad about this, because they have spent a lot of time for problem 1 to 40 and now it is freely available to everyone.
Title: 100 Problems, I am taking a break
Post by: 万精油 on 二月 13, 2008, 03:08:18 pm
It's been almost a month since I found out this Euler Project (Jan. 14). I have now solved 100 problems in there. It's been interesting but I need a break (at least for a week). I will still participate discussion if other people are interested. There are 6 problems under 100 that I haven't solved yet, they will be the target when I come back. :)

Title: Re: Project Euler
Post by: 万精油 on 二月 15, 2008, 12:14:52 pm
I said I was going to take a break, but back in my mind I am still thinking about the unsolved problems. One of them is problem 83. My original approach (simple code, brute force, because I was lazy) took more than one day to converge and the answer was wrong. I had a new idea last night before falling sleep, and tried it out this morning, it took 22 minutes, and the answer is correct. I was quite happy until I saw other people's approach (once you solve a problem, the discussion for that problem is open to you). Some other people have some code (which I don't understand since it is in different language) that get the answer in 0.6 second. When I have time, I really need to investigate that code. :) Furthermore, one guy solved the problem in 12 minutes (i.e. 12 minutes after the problem was posted) using Excel !!!. Amazing, and the approach is very easy and smart, but you need to know some features of Excel (obviously I didn't). I have learnt something from this problem.

Now, I have 102 problems under my belt.
Title: Re: Project Euler
Post by: 万精油 on 二月 15, 2008, 03:18:54 pm
I took some time to look through posts of the problem 83, and saw many of them use something called Dijkstra Algorithm. I have never heard of Dijkstra Algorithm, so I went to Wikipedia and checked it out. To my surprise (and delight) that the so called Dijkstra Algorithm is almost exactly equivalent to the idea I have for this problem. May be it should change its name (if oly we had a time machine :) ).

Title: Re: Project Euler
Post by: 万精油 on 二月 15, 2008, 05:45:01 pm
The more I read this problem, the more I learn. One of the method mentioned there is rediculously simple.  I implemented it in MATLAB with about 15 lines (mostly protocals, essentially just one line), and get the result in 0.1 second.

Title: Re: Project Euler
Post by: Dr Kevin Wang on 二月 16, 2008, 09:19:56 pm
I took some time to look through posts of the problem 83, and saw many of them use something called Dijkstra Algorithm. I have never heard of Dijkstra Algorithm, so I went to Wikipedia and checked it out. To my surprise (and delight) that the so called Dijkstra Algorithm is almost exactly equivalent to the idea I have for this problem. May be it should change its name (if oly we had a time machine :) ).

Indenpendently discover the Dijkstra Algorithm ... that removes any doubt that you are a genius  :-D
Title: Re: Project Euler
Post by: 万精油 on 二月 18, 2008, 02:18:25 am
Quote
Indenpendently discover the Dijkstra Algorithm ... that removes any doubt that you are a genius

The dijkstra Algorithm is suitable for general graph, mine is for this problem only. But it has the similar idea. After reading the official Dijkstra algorithm, I changed one way of updating my array and significantly reduced the computing time.
Title: Anyone knows J?
Post by: 万精油 on 二月 18, 2008, 12:13:57 pm
For problem 101, I have a very neat short MATLAB code, and I was very happy with my code. Here's my MATLAB code (c is the answer).

Code: [Select]
`c = 1;for i = 2:10, c = c + round(((((1:i).^11+1)./(2:i+1))/exp((0:(i-1))'*log(1:i)))*((i+1).^(0:i-1))'); end`
I thought it can't be simpler than this until I saw someone's code in J language (as I mentioned before, once you solve a problem, the discussion board for that problem opens to you). I don't know J, but I am certainly impressed by this. It is much shorter than my MATLAB code (which I thought can't be shorter). If anyone knows J and can explain in detail about what does what, I will really appreciate it. Here's the J code.

Code: [Select]
`ps=: %.@(^/ <:)@:>:@i.@# +/ .*+/(p. >:@#)@ps\(11\$1 _1)p.1+i.10x `
Title: Re: Project Euler
Post by: 万精油 on 二月 20, 2008, 12:54:28 am
Wikipedia is really wonderful. It has almost everything. I found a link in there about the J_programming language. Very interesting.

J_Programming Language (http://en.wikipedia.org/wiki/J_programming_language)

I can't help myself, can't really take a break, still solve a problem or two each day. Now, I have 110 problems solved and got into the 3rd page (i.e. below 300). I think it will take me at least another month to get to the 2nd page. I still have one problem under 100 that I haven't solved. :(

I also noticed that id94 is moving up in the rank amazingly fast. With that speed, you will over pass me in notime. After all, two people (assuming FZY is helping you) is stronger than one. :(
Title: Re: Project Euler
Post by: jeff_gao on 二月 20, 2008, 11:10:26 am
I have been quite busy recently: recovering from Miami ING marathon; 11 month baby got cold, then his mom, and then myself (interestingly, I am always the last one to get cold if at all - which may due to that fact I am stronger :-) ).

In any case, I got 93 solved so far. I don't have time to read the forum yet, but I think I get the fastest factorization algorithm in the world:-) It help me solved both the Euler phi problems in less than 1 second, and continues to help me solve factorization-related problem. My method does require 2 integers of storage per integer although (which is not an issue for the scale of these problems).

I agree with Prof Wan, the project is interesting enough that I can do it as a way to kill spare time and relax :-)
Title: Re: Project Euler
Post by: fzy on 二月 20, 2008, 12:56:51 pm
We have 77 now, on the 6th page I think. I solved about 2/3 of them. Tomorrow I will go on a 3 week trip to China. As of now I am not sure whether I have more or less spare time, most likely less.  :-(

So far no problem used more than one minute of computer time. If my program runs more than a few minutes, I would just kill it and start over. I do this for one reason: I almost never get the right number in the first try, usually in the fourth or fifth. So I cannot afford long programs.
Title: Re: Project Euler
Post by: 万精油 on 二月 20, 2008, 02:39:30 pm
Quote
I have been quite busy recently: recovering from Miami ING marathon; 11 month baby got cold, then his mom, and then myself (interestingly, I am always the last one to get cold if at all - which may due to that fact I am stronger  ).

Another marathon runner. Great.

I don't remember the last time that I had a cold. All my sickness is due to sports injuries.

Quote
In any case, I got 93 solved so far.

7 more to get to 100. There are not too many 5-star red flags above 100. We need you up there.

Quote
I don't have time to read the forum yet, but I think I get the fastest factorization algorithm in the world:-)

I doubt it. Factorization has been investigated by so many people, the fastest algorithm for factoring, if there is such a thing, must be discovered by many people already. On the other hand, the problems in this Project all involve small numbers (they are big numbers, but for factoring algorithm, they are small, since most of the advanced factor algorithms deal with numbers with hundreds of digits), factoring small numbers should not take long, even MATLAB can factor a 10 digit number in less than 1 milli-second.

Quote
It help me solved both the Euler phi problems in less than 1 second, and continues to help me solve factorization-related problem.

It means you have a good way of computing Phi. Under 1 second is really impressive. Are we talking about problem 72? Problem 69 talks about phi, but it takes less than 1 milli-second.

Quote
I agree with Prof Wan, the project is interesting enough that I can do it as a way to kill spare time and relax

Yes, very entertaining.

Quote
We have 77 now, on the 6th page I think. I solved about 2/3 of them.

I suggest you change the profile of that account to China, so that we can have more 5-star red flags there. :)

Quote
Tomorrow I will go on a 3 week trip to China. As of now I am not sure whether I have more or less spare time, most likely less.

Let me know if you can access this site. I had trouble accessing this site from China.

Quote
So far no problem used more than one minute of computer time. If my program runs more than a few minutes, I would just kill it and start over. I do this for one reason: I almost never get the right number in the first try, usually in the fourth or fifth. So I cannot afford long programs.

Out of all the problems that I have solved, there are 3 of them takes longer than 1 minute. The website says all problems should be done within one minute.
Title: Re: Project Euler
Post by: fzy on 二月 25, 2008, 12:53:00 am
Quote
I suggest you change the profile of that account to China, so that we can have more 5-star red flags there. :)

You need to ask Id94 for that. Technically he still owns the account.

Quote
Let me know if you can access this site. I had trouble accessing this site from China.

Yes I can access this site, but basically nothing else.
Title: Re: Project Euler
Post by: 万精油 on 二月 25, 2008, 05:01:47 pm
Quote
You need to ask Id94 for that. Technically he still owns the account.

ID94, what do you say?

Quote
Yes I can access this site, but basically nothing else.

Great. I am glad it works now. Last time when I went back, I had trouble accessing it.

Now, I have 120 problems solved, that include every problem from 1 to 117 and 3 others that happens to be mentioned by someone some where and I went ahead and solved. Problem 118 doesn't look very hard, but don't have time for it right now. Really need a break. :)
Title: Re: Project Euler
Post by: idiot94 on 三月 06, 2008, 02:28:35 pm
Quote
You need to ask Id94 for that. Technically he still owns the account.

ID94, what do you say?

Quote
Yes I can access this site, but basically nothing else.

Great. I am glad it works now. Last time when I went back, I had trouble accessing it.

Now, I have 120 problems solved, that include every problem from 1 to 117 and 3 others that happens to be mentioned by someone some where and I went ahead and solved. Problem 118 doesn't look very hard, but don't have time for it right now. Really need a break. :)

haha, I did not do anything to Project Euler, although people are talking about ... "me" ... :)
Oh, I do not even know how to put on the flags... what is the flag on me right now? I will go check it out. Anyway, since I do not know how to do problems, at least I should contribute a little to that part. It may take very long time to figure out how to do it though :D
Title: Re: Project Euler
Post by: idiot94 on 三月 06, 2008, 03:03:15 pm

Title: Re: Project Euler
Post by: 万精油 on 三月 09, 2008, 11:35:22 pm

Title: Re: Project Euler
Post by: idiot94 on 三月 10, 2008, 12:17:35 am

Title: Re: Project Euler
Post by: 万精油 on 四月 02, 2008, 03:58:40 pm
Just finished Problem 152. This is by far the most difficult problem (from 1 to 152). I actually found the approach in the first 10 minutes, but spent days to find bugs in my code since I kept missing some terms.

Will really take a break, at least until tax season is over. :)
Title: Re: Project Euler
Post by: fzy on 四月 05, 2008, 12:18:27 pm
Just finished Problem 152. This is by far the most difficult problem (from 1 to 152). I actually found the approach in the first 10 minutes, but spent days to find bugs in my code since I kept missing some terms.

Will really take a break, at least until tax season is over. :)

Don't remember spending too much time on 152. Probably was lucky.

I still have many early problems left. I am sure most are due to silly mistakes, but too time consuming to find them.

Also need a break until tax is done.
Title: Re: Project Euler
Post by: 万精油 on 四月 05, 2008, 03:33:41 pm

Quote
Don't remember spending too much time on 152. Probably was lucky.

There are some problems I got in first try, many problems I need to correct some error. However, for problem 152, I missed one term in my first try, and corrected and introduced other errors. My final code is not very much different from my first code, but took a long detour.
Title: Re: Project Euler
Post by: fzy on 四月 06, 2008, 12:25:12 pm
My solution for 152 is very silly. Just exclude some (most) denominators and then do a brute force search. But it did give the right answer after a while.
Title: Re: Project Euler
Post by: fzy on 五月 15, 2008, 12:37:37 pm
Hi, professor,

We finally met at 168 problems
Title: Re: Project Euler
Post by: 万精油 on 五月 15, 2008, 03:05:50 pm
You guys are amazing. I had a very big head start. Unfortunately, I move like a turtle in the past two one month or so. Finally, I decide to not follow the problem sequence and pick some easy problems from the later list, thus, I moved a little bit in the past week. Now, I am back to original problem sequence, try to do one problem per week, this way, I will catch the top guys at the end of the year (I hope).

The problems are getting harder, and sometimes not hard but require large memory. MATLAB is not the right tool for these problems and I am stuck many times. There's a couple of problems I have to use C.

I just put in a problem and I am now at 169. I hope I can get into the first page by the summer.
Title: Re: Project Euler
Post by: fzy on 五月 22, 2008, 10:13:39 am
We are on page 1 now, and hope to see you there soon.

You are probably at the most difficult stretch now. The most recent problems are easier. We also have only the really difficult ones left, and it will be quite slow from now on.
Title: Re: Project Euler
Post by: 万精油 on 五月 22, 2008, 02:17:03 pm
I have been working crazy on the Earthquake donation relief for the past week (after all, it is my hometown), don't have time to do anything else. I think I will start to crack on PE problems next week.
Title: Re: Project Euler
Post by: 万精油 on 五月 22, 2008, 09:32:25 pm
Quote
You are probably at the most difficult stretch now. The most recent problems are easier.

I think you are right, I looked at some of the later problems and feel I can solve them (not easily), but there are some problems that I do not see any direct ways.

So far, I have solved every problem from 1 to 160 and some scattered ones from 161 to 194.
Title: Re: Project Euler
Post by: fzy on 五月 23, 2008, 08:44:32 am
I have been working crazy on the Earthquake donation relief for the past week (after all, it is my hometown), don't have time to do anything else. I think I will start to crack on PE problems next week.

Good luck to you, your family, and everybody in Si Chuan.
Title: Re: Project Euler
Post by: 万精油 on 六月 19, 2008, 12:42:09 pm
Congratulations to FZY and ID94 for making to the top (100% problem solved)!! Really impressive.

I am also in page one now.  I still have about 15 problems to go.

I plan to do one problem a week, but it seems they are posting new problems once a week. With this rate, I can never catch up. :(  I thought they used to post new problems once every two weeks.
Title: Re: Project Euler
Post by: idiot94 on 六月 21, 2008, 10:09:17 am
Prof. W, FZY did more than 95% of the problems. The rest are done by the other friends of WXC. I did not do anything at all :D ... haha....
Title: Re: Project Euler
Post by: fzy on 六月 21, 2008, 10:29:17 am
I did about 80% of the problems. In the beginning people were quite ensusiastic, and the problems were easier. I remember we became ranked in a very short time. At the end we also got a lot of help, when there is light at the end of the tunnel.

The recent problems are very good, particulously 195, 198, and this week's 199. Still it is difficult to get a higher ranking. timing seems always a problem.
Title: Re: Project Euler
Post by: 万精油 on 六月 21, 2008, 10:52:43 am
Quote
The recent problems are very good, particulously 195, 198, and this week's 199. Still it is difficult to get a higher ranking. timing seems always a problem.

I am back to my old routine, i.e. solve problem by their natural order. Thus, I haven't tried 198 and 199.

Yes, 195 is interesting. I did it because I "saw" a quick way to do it. Unfortunately, I missed the factor 3 problem and keep missing the upper bound, took me a while to catch the missing part. My final code was just one line different from my original code.

The timing for the new problem is good for Europe people (or west cost people), but not good for East cost people. My brain stop functioning after 1am (I know that because most of my losing WeiQi games on the internet are played after 1am :)).  It used to be the other way around. When I was young, my brain start up after 10pm. :(

Title: Re: Project Euler
Post by: fzy on 六月 26, 2008, 09:23:37 am
Hi Professor,

Have you seen this news item on PE? Now you have time to catch up.

Quote
Due to vacations that the team will be taking at various times during the summer (in the Northern hemisphere) we have made the slightly regrettable decision to suspend the release of weekly problems during July and August. We hope that you will appreciate how hard the team work to produce these problems that we all enjoy on a weekly basis and I think you will agree that a well earned rest is fully deserved.

But all is not bad news... incredible as it may sound, this Saturday, 28 June 2008, signifies the release of our 200th problem! In developing it we believe that it captures something for everyone: interest and challenge, as it is neither too hard nor too easy, and extra points for anyone able to spot the "200" connection. (c;

As an additional bonus you will be treated to TWO problems on 5 July before the break commences: one medium and one hard problem. Then we will return on 5/6 September with FIVE easy problems.

So enjoy the "200" problem and the following week's "double bill", and after that we trust you will have a restful summer.

Title: Re: Project Euler
Post by: 万精油 on 六月 26, 2008, 11:25:31 am
Quote
Have you seen this news item on PE? Now you have time to catch up.

This is indeed good news for me. I don't know how much I will catch up, since I myself have a busy summer schedule too (mostly fun and vacation stuff). At least, with PE break during the summer, I know I will not drag more behind. :)

Just solved 175. Got stuck with this seemingly "easy" problem for quite a while. :(

BTW, just saw PE's official language list, MATLAB is not one of them, too bad.
Title: Re: Project Euler
Post by: 万精油 on 六月 30, 2008, 03:40:27 pm
Really dissapointed. With such a big fuss, the No. 200 problem doesn't seem to be very interesting. I haven't solve that problem yet, but I think with a brute force search it should be doable. What I am dissapointed is that the problem lacks and "cleverness" or "educational" feature. It is more like a man-made problem not suitable for anything else. The only thing that it is special is there is a "200" in the problem (for the No. 200 problem). But, there are many other ways to connect 200 to a problem, such as find the 200th term of a sequence, etc.

After seeing this problem, my interest to PE took a big dive. I will still try to solve all the problems, but not as motivated as before.:(
Title: Re: Project Euler
Post by: 万精油 on 七月 21, 2008, 09:33:20 am
Finally solved Problem 167 (Ulam sequence) last weekend. I had the basic idea correct the first time around, but didn't expect the last period to be that big. Since my approach of generating Ulam sequence was slow. It is almost impossible to compute to 2 million terms in short time. Last weekend, I devised a faster way to compute Ulam sequence (not as fast as the ones I found after reading other people's solution), but my approach is universal, not bound to (2,2n+1) form.  I am glad this problem is gone. :(
Title: Re: Project Euler
Post by: fzy on 七月 22, 2008, 10:10:12 am
Finally solved Problem 167 (Ulam sequence) last weekend.

That is a nice problem though.
Title: Re: Project Euler
Post by: 万精油 on 九月 29, 2008, 03:32:57 pm
I finally had some time to get rid the last two problems on my waiting list. Problem 181 and problem 198. I think the hardest problem is 198 so far. I had the right idea of using continued fractions, but missed the trivial ones (those in the form of 1/(2*x); It costed me many days. Problem 181 is another matter. It is precision problem again (because the answer is more than 16 digits).

I haven't got the time to do the new problem yet (problem 210). I think the key is to figure out how many integer grid points in a given circle of a LARGE radius.
Title: Re: Project Euler
Post by: 万精油 on 十月 04, 2008, 10:54:05 am
Problem 210 is not hard, it is easy to figure out what to compute and how to compute it. However, since the answer is more 18 digits long, and many computations require precision in both end (sqrt need to know digits after decimal and square numbers need to know the 18th digits). Ordinary computation will not work. This seems to be the trend of Project of Euler now. You get the idea quickly but spend a lot of time to deal with the small nuance. Not worth it. I used to tell myself once I solved all problems before 200, I will quit. Now, I have solved more than that, finished all problems except the last two. It's time to quit.

I have learnt a lot in PE, a really interesting project.

Other people are still encouraged to discuss PE problem in this thread.
Title: Re: Project Euler
Post by: haha2000 on 十一月 12, 2008, 12:07:45 pm
According to http://projecteuler.net/:

Who are the problems aimed at?

The intended audience include students for whom the basic curriculum is not feeding their hunger to learn, adults whose background was not primarily mathematics but had an interest in things mathematical, and professionals who want to keep their problem solving and mathematics on the edge.

I think many guys here may be not qualified, since you are well trained mathematicians + some computer scientists (such as Prof. Wan, FZY, IDIOT94)...

LOL...