Talk:Project Euler

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated B-class, Low-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
B Class
Low Priority
 Field: General
This article has comments.


Too much for the example[edit]

The number of Scala user and Clojure user are only 119 and 53, and Groovy is not even listed in the statistics page.
I think they should be removed.
Python and C++ is enough.
Rinick (talk) 08:24, 17 January 2009 (UTC)

agree. It's putting undue weight on those examples. tedder (talk) 08:32, 17 January 2009 (UTC)

It's questionable if the recently added C# example adds much to the article. It's probably more about C# than about the solution to the problem. Hkleinnl (talk) 20:35, 24 October 2010 (UTC)

Actually, I think so, too. Feel free to remove it. --Daniel5Ko (talk) 20:08, 25 October 2010 (UTC)
I'd prefer only one example language, presumably pseudocode, for the two solutions (brute force and closed form). The article is not about showcasing programming languages. You can always check the PE forums for solutions in various languages. Daggerbox (talk) 18:42, 29 October 2010 (UTC)
In the meantime a Ruby example has been added. Rather than starting edit warring I think someone should take the responsibility to change the whole thing into pseudocode.

Hkleinnl (talk) 19:48, 1 November 2010 (UTC)

I did it. Let's see if someone disagrees. :) --Daniel5Ko (talk) 19:02, 2 November 2010 (UTC)
Thanks, I made minor edits (the text still referred to programming language examples) and attempted a cleaner set of formulas. Daggerbox (talk) 01:06, 3 November 2010 (UTC)

Big O Notation remark[edit]

Right before the "See Also" section the article mentions that,

In Big O notation, the brute-force algorithm is O(n) and the efficient algorithm is O(n), the constant of proportionality is much smaller for the second algorithm.

I think that the efficient algorithm is O(1) because it involves fixed number of calculations irrespective of value of N. I may be worng, but if not can someone correct it. Thank you. —Preceding unsigned comment added by 128.61.82.17 (talk) 05:06, 3 May 2009 (UTC)

You're right, it is O(1) if we assume the arithmetic operations are. Taking their complexity into account, it would be O((log n)α) (but I don't know what the optimal α is). Rupicapra (talk) 13:38, 4 May 2009 (UTC)

It seems to me that problems of the type on the Euler problem website present a deeper problem. I may be wrong and if I am right I am probably not the person to formulate the problem, nor is this article the place to raise it, but there may be someone out there who knows how to express the problem and where to put it.

Suppose we really want to know the sum of the numbers from 1 to 100 which are not divisible by 3 or 5. Suppose you are present at the meeting where the requirement comes up and suppose that you are delegated to work it out.

If you are new to the company you produce a list of the numbers from 1 to 1000, classified by divisibility by 3 or 5 or both, and convince the meeting that one of the columns on your list contains all the numbers we need to add, further that the sum is 266,332. This is less efficient than the brute-force method but it gets the job done.

If, on the other hand, you are the trusted expert, it is enough to say “It is 266,332.” How you prepare this speech is up to you. It is not the meeting’s business. They assume that your time is less important than theirs. This assumption lies behind any demand for an efficient program.

Suppose the meeting accepts this answer, one way or the other, but the boss has a poor memory. He wants you to fix it so that a message “The magic number is 266,332” pops up whenever he presses an icon on his desk-top. You can fix that for him and your program does not involve any calculations at all. All these O(1), O(n) and O((log(n))α) algorithms are a waste of time.

A more reasonable requirement is that a form pops up into which the boss can put a number. Call it n. The message is now the result of substituting n for m in the string “The sum of the numbers from 1 to m not divisible by 3 or 5 is Z”, where Z is such that the statement is true.

A reasonable boss will add a sentence which is the result of substituting a number B for b in the sentence “I will never type in a number larger than b.” Since your time is less important than his you loyally stay behind that evening to put all the Z values he will need behind the icon.

An unreasonable boss will maintain that he can type in any number he pleases. The suggested algorithms will crash for a large input. I do not know of a computer language which copes with this automatically. When I need unlimited numbers, for research in number theory, I treat them as strings. Even this treatment will break down if it runs into problems of size of memory etc. A program is better than a look-up table only in a finite range where we have enough space to store each question but do not have enough to store all the answers.

Strictly though, the demand for an efficient program is meaningless. If we have finitely many problems to solve no program is as efficient as knowing the answers and if we have infinitely many no program will work at all.

Bukovets (talk) 14:45, 2 September 2009 (UTC)

I'm not sure I get your point. In talking about algorithmic complexity, as in the Project Euler problems, I think if it's not explicitly mentioned, it's always implicitly understood that you have one or more input parameters with respect to which the complexity is assessed. In the example, it's taken to be the limit up to which you add the multiples. Although one could also take the numbers whose multiples are to be summed and their count into consideration. In full, one would solve the problem "sum all multiples of any of the k numbers a1, a2, ..., ak below n". Finding the complexity of that isn't so easy, so let's keep it at k = 2, a1 = 3, a2 = 5 for the moment, thus the only input is the limit n. If you often need the answer to that question for different possibly large values of n, an efficient programme is important and the time you spent thinking about the algorithm and coding it will be saved many times over later on. Storing the answers is only reasonable if n is restricted to some small range.

FYI, regarding "The suggested algorithms will crash for a large input. I do not know of a computer language which copes with this automatically.", e.g. Haskell and Python have built-in arbitrary precision integers (where arbitrary precision means 232 bits - probably 264 on 64-bit platforms - or what your memory can handle). They take up much less memory, are faster and easier to handle than string representations. I'd say Haskell and Python cope automatically (within memory limits).

Rupicapra (talk) 20:55, 7 September 2009 (UTC)

"A program is better than a look-up table only in a finite range where we have enough space to store each question but do not have enough to store all the answers."

But if you think about it, the whole universe actually is finite. However efficient computers may be, we are still bounded by certain universal constants such as the number of particles in the universe. And certain problems cannot be solved using lookup with this limitation, since there really isn't enough memory to store all answers. For example, if we have a program that inputs a graph and outputs a number, there really isn't enough memory to store all answers for all graphs, even if we restrict the number of vertices to such a small number, say, 1000, since there are at least 2100000 of them.

The notion of complexity, is therefore relevant in this universe. The problem is that our mathematics is not yet fully developed to quantify this relevance in theory; instead we settle with things such as O(log n) which have hidden constants in them.

"Strictly though, the demand for an efficient program is meaningless."

The demand for efficient algorithms is just meaningless within our current mathematics, because we have yet to find a way to accurately model efficiency aside from using Big O Notation. Theoretically, any finite problem, say chess, is solvable with lookup, but this fact has no other value aside from being theoretically interesting (ALL of the problems that we can solve with a computer is finite). However, to model efficiency of programs more accurately is also cool if we want more theory and more exercises.

124.6.181.35 (talk) 01:28, 4 September 2010 (UTC)

Proposed deletion[edit]

Recently, someone thought that PE may be not notable. What can we do to establish its notability according to the guidelines? (A Google search is cluttered with gazillions of blog posts, any of which is officially unusable :/)

The closest thing I found, being somewhat useful was [1], which sadly isn't much more than a copy of some parts of the WP article. Also, somewhat interesting, but probably not good enough is an interview with Don Syme of F# fame [2]. --Daniel5Ko (talk) 23:10, 20 September 2010 (UTC)

Take a look at WP:NOTABILITY. Basically what we need is "significant coverage in reliable sources that are independent of the subject". — DroEsperanto (talk) 23:15, 20 September 2010 (UTC)
I know that page. Thank you. Feel free to be more helpful. --Daniel5Ko (talk) 23:28, 20 September 2010 (UTC)
Well, if independent, significant coverage is all that's needed, then these gazillions of blog posts are good enough, provided they are reliable. Does it count as reliable, when, e.g., the bloggers are MS employees revealing their real names :D ? --Daniel5Ko (talk) 23:45, 20 September 2010 (UTC)
Blogs are, except in rare cases, unreliable as sources, since then anyone could just go start a blog and then call something notable. See WP:RS and WP:SPS for blogs specifically. — DroEsperanto (talk) 23:48, 20 September 2010 (UTC)
Oh, it just occured to me that the reliability is of no concern because the blog posts wouldn't serve as sources for a claim, but as a proof of the claim of their own existence (which anyone can check easily). And the latter claim is the one somewhat supporting notability — because there are quite some (looks like thousands of posts from at least a few dozens of unrelated blogs), not just one. What do you think? I think it's remarkable, given that the topic is very unpopular. Nevertheless, I'll further try to find good mentionings in more traditional media... --Daniel5Ko (talk) 18:22, 21 September 2010 (UTC)
On the contrary, the reliability of the sources used to justify notability is of concern -- the guideline is pretty clear about that requirement. Remember, being popular is not the same as being notable. I welcome the addition of quality sources, but if none can be found the article might not withstand an AFD. — DroEsperanto (talk) 19:13, 21 September 2010 (UTC)
To be more clear: When I try to establish notability by saying there's lots of resonance in the blogosphere, this can be proven by giving some (more exactly: lots of) examples. Blog posts cannot exist unreliably ;). Shouldn't be too hard to understand. /me goes back to search... --Daniel5Ko (talk) 19:54, 21 September 2010 (UTC)

(unindent) I understand what you're saying, and what I'm saying is that a resonance in the blogosphere is never, on its own, sufficient proof of notability. Your time would best be spent finding non-blog sources reporting on Project Euler rather than collecting blog references. — DroEsperanto (talk) 20:46, 21 September 2010 (UTC)

I don't spend time collecting blog-references. That would be, of course, much too easy. --Daniel5Ko (talk) 21:09, 21 September 2010 (UTC)

Some (admittedly not too good) references that might be used to somehow construct notability matching the guidelines; estimated usefulness for really establishing notability in parentheses:

  1. [3] — an article in the online presence of a popular German print magazine on computer technology. (38%)
  2. [4] — a nice find showcasing funny laziness. (10%)
  3. [5] — PE problems have lead to at least one interesting TMR article. (Trivial mention there, though; but maybe the fact itself is perhaps interesting) (11.2%)
  4. French WP article openly admits that it is a translation of the English one and uses it as reference, the Swedish one uses it as reference. — not a direct argument for notability, but at least all the other language's WPs don't doubt the notability at the moment... (1%)
  5. [6] — along with #2, this can perhaps serve to prove that sometimes (and increasingly? -- okay that one would be hard), PE is used as inspiration for (maybe graded) exercises in education. (10%)
  6. All the (looks more like tens of thousands now) blog articles — in general, the same: they use PE problems to either say PE is interesting or to showcase the expressiveness of programming languages. (20%)

Ideas on which one should be elaborated?

Some arguments for keeping the article anyways:

  • Above all, PE is an entry point to personal research into mathematical/algorithmical knowledge. Especially because it doesn't care about the user's current interests, but poses arbitrary problems. It is not web content, but a tool / web service to encourage learning. Works for anyone who is encouraged by competing with others. Everyone who thinks that education is good, should want to tell people about PE. Conversely, banning PE is an example of anti-intellectualism at its best.
  • And: somewhat meta: the existence of the PE article probably leads to (a little bit) more PE users, which, in turn, probably leads to improvements to WP in general (at least its maths, algorithms and programming languages articles), because more users look up things in that areas and spot errors or other opportunities for improvement.

--Daniel5Ko (talk) 22:20, 21 September 2010 (UTC)

For me it's rather simple: more than 120 000 people from all over the world are member of Project Euler. If that's not enough, those "notability references" don't add much to the article but serve only to keep it on this WP. Well if WP does not understand that references that are by themselves not interesting but serve only to keep the article only distract from the real thing: go ahead and delete it. Project Euler gets enough attention from all over the world anyhow. c.f. the article about Twitter. --Hkleinl —Preceding undated comment added 13:58, 23 September 2010 (UTC).

Well said. :) --Daniel5Ko (talk) 16:43, 23 September 2010 (UTC)

Another possible notability source: PE problems were used for an APL programming contest. Daggerbox (talk) 18:50, 29 October 2010 (UTC)

Notability tag[edit]

As a further notability source I added a link to the 50 OEIS sequences referencing Project Euler problems. As the OEIS has an editorial board I think that notability has now been established. Can that note at the top of the page now be deleted?Hkleinnl (talk) 21:11, 15 April 2011 (UTC)

I initiated the above paragraph because of this: [7]. Because the notability tag is much less "dangerous" and as this tag itself is now under discussion, I now added another headline "Notability tag" above your continuation.
Anyway, to answer the question: I don't think we really hit any criterion mentioned in [8]. Yet, the question remains whether this guideline is the appropriate one here at all (I doubt that PE is mere "web content").
I think we are facing a similar problem here as the article NLab, that even was threatened by speedy deletion once. And although for the latter it is probably even harder to really establish notability according to any WP guidelines, it isn't burdened by a notability tag.
Probably we should just remove the tag and see what happens next. :) --Daniel5Ko (talk) 22:31, 15 April 2011 (UTC)
Perhaps we should wait a little and see what happens now. Placing an "is it notable tag" should make it an obligation to return from time to time. My opinion is that simply littering WP with all kinds of tags and then let it be there for extended periods doesn't make much sense.
On another note PE has been one of the first of this kind of websites if not the first and many others have followed and have been copying the idea. E.g. http://www.cstutoringcenter.com/ and http://www.mathalon.in/. This might be another argument whenever it comes to a full flight notability discussion.
Let's be patient and see what happens now.
Hkleinnl (talk) 13:06, 16 April 2011 (UTC)
Well, I've now asked the user who placed the tag to share his oppinion. --Daniel5Ko (talk) 21:16, 18 April 2011 (UTC)
The increase in popularity and the sources provided, however weak, have convinced me of the notability of the topic. I am removing the template. --M4gnum0n (talk) 12:19, 23 April 2011 (UTC)
Does this count as source for establishing notability? http://nymag.com/arts/all/approvalmatrix/approval-matrix-2011-6-27/

Hkleinnl (talk) 14:26, 3 September 2011 (UTC)

Project Euler Solutions[edit]

I am a full time teacher and I have been for a long time. I think that learning to program and find algorithms does not only come by searching but also by reading other's works. As for any education. If there exists solutions in any other languages, I think they are welcome too. For me students should be exposed to problems, advised to look for solutions by themselves but also offered as many solutions as possible. --npettiaux (talk) 11:02, 26 December 2012 (UTC)

Those solutions you want the students to be confronted with are offered in the fora on Project Euler dedicated to each problem and that are accessible once the problems are solved. As a teacher you should be aware that you shouldn't offer full solutions to students before they have tried to solve a problem themselves. Moreover if you look at the solution of the first problem in the solutions you provided a link to and compare it with what has been written on this page it's the dumb solution for which a better algoritm exists and thus even contradicts what has been written on this Wikipedia page about Project Euler.--Hkleinnl (talk) 12:33, 26 December 2012 (UTC)
As I have indicated Project Euler provides the opportunity to look into other's work by means of the problem's fora and (for some problems) carefully composed PDF's. In my opninion it's not the task of Wikipedia to provide answers to problems before they are solved if Project Euler doesn't do that for good reasons. Please consult Project Euler's policy about publishing answers/solutions outside Project Euler on the about page: http://projecteuler.net/about. The Project Euler page on Wikipedia is about Project Euler and should not by means of links to solution sites thwart the intentions of Project Euler. One can have different opinions about the way Project euler tries to achieve its goal, but one should not frustrate the means by which Project Euler tries to achieve its goals. That's having another agenda than the website this Wikipedia page is about. For the reasons given the added link should be removed.--Hkleinnl (talk) 20:56, 27 December 2012 (UTC)
We are not a teacher giving these problems to our students. It's not our job to decide whether a reader ought or ought not to see the solutions; Wikipedia is about giving relevant information. We are not thwarting PE's goals at all--the problems are self-driven and it is made clear that solutions are available should one choose to search for them. Moreover, the link in question is not just answers but solutions, which can be very informative. And it's perfectly alright to have "another agenda" than Euler. In my opinion, if the link adds to the article (as an encyclopedic article, not an extension of PE), it should be kept. So that's what we need to decide. In any case we shouldn't just go around reverting each other's edits. etothei (talk) 21:56, 27 December 2012 (UTC)
I'm not very impressed by the argument that Wikipedia should make clear that if one wishes one can find solutions to Project Euler problems on the web by pointing to such a solution site. Let me explain why: It's widely known that if one doesn't want to pay for a software package one can search for <package name> crack. However I looked up http://en.wikipedia.org/wiki/Mathematica and there isn't such a link to a crack. That's not astonishing though, the seller would strongly object. The same holds for CD's and movies: loads of "free downloads". About the link in question: as I pointed out already: the solutions offered are at best suboptimal and sometimes will produce wrong answers for other parameters. So I'm doubting the informative value of the offered solutions. If one has to link to a solutions site Wikipedia should be able to guarantee that the solutions offered are optimal and will produce correct answers for other parameters too. I must confess that I looked up many of those "Project Euler solutions in language xxx" sites and am very sad about the low level of the offered solutions. Do we really have to open the door for a tsunami of those sites?--Hkleinnl (talk) 20:14, 28 December 2012 (UTC)
Before I begin, let’s remind everyone that this is a very trivial detail, a single link at the bottom of a fairly obscure article. I don’t want to fight a war over this. Maybe a third (fourth, really) opinion would help immensely. Now, then:
It seems you have two main arguments: First, that offering solutions (not just answers) somehow rips off PE and practically ought to be illegal; second, that the solutions aren’t very good anyway. For the first point: let’s please try not to focus on Project Euler’s interests here. You seem to be pretty high-up in PE (go ahead, look me up too) and we need to be careful of conflict of interest. Mind you, I’m also a big fan of PE, and of course I’m not trying to hurt its goals in any way. PE is an educational, self-guided resource, and I’d say that having solutions available adds to that. PE is really not a competition to see who can get all the answers, as much as I admire you for having done so.
Second, just because the solutions are not perfect does not mean they are not informative. I agree that we don’t want a flood of amateur sites, but one or two pages (in English) in my opinion makes a good addition to this article.
Above all, we need to remember where we are. “While editing Wikipedia, an editor's primary role is to be a Wikipedian. Any external relationship may undermine that primary role” (WP:COI). Although we’re all probably Eulerians here, Wikipedia should not promote PE or act as a math tutor. But I think the link should stay. Does someone else have thoughts on this? etothei (talk) 22:51, 28 December 2012 (UTC)
I agree with Hkleinnl. I don't think this article should link to solutions at all, but it certainly should not link to some obscure page containing a handful of mediocre solutions. Honestly, I can't see why anyone other than the person who wrote them would support their inclusion here, because it helps nobody else, and definitely does not add to this article (in fact, I feel it takes away from it). The only way I can see anybody benefiting (indirectly) from them is to copy-and-paste the answer to gain access to the infinitely better solutions in Project Euler's forums and (unfortunately small number of) PDFs. (Of course, this 'benefit' is far less than would be gained thinking about it themselves first, but that is less relevant as to whether it should be on Wikipedia or not...)
Like you said, it's a trivial detail, and if somebody really wants to find solutions outside of projecteuler.net, it is sadly all too easy. I just see no reason for Wikipedia to catalyse this process (particularly via the site it currently links to). 94.171.224.122 (talk) 07:00, 29 December 2012 (UTC)
Sounds reasonable to me. I'm not too attached to the link...does anyone else think it should be kept? etothei (talk) 23:31, 29 December 2012 (UTC)
A week seems enough to me for someone to tell that he wants to keep the link. Going to delete the link.--Hkleinnl (talk) 11:49, 7 January 2013 (UTC)

Recently a link to a site was added where PE answers could be checked without logging in. In itself it looked harmless, albeit superrfluous as PE anwers can be checked on the site itself. However, a button was added that reveals the answer. In line with the previous discussion it seems that Wikipedia shouldn't catalyse the process of finding PE solutions without any effort. So I removed that link.--Hkleinnl (talk) 13:25, 20 July 2013 (UTC)

Note/article contradiction[edit]

The note says "inclusive or, not exclusive or", but then why do we subtract the number of 15 multiples in the mathematical explanation for the efficient solution? 47.16.142.4 (talk) 21:39, 21 February 2015 (UTC) --Because that's how it should be solved. Wikipedia isn't the place to discuss solving methods for PE problems.Hkleinnl (talk) 21:40, 22 February 2015 (UTC)