7 ms·

Project Euler's 500th problem

254 points by bhaumik 12y ago

jacquesm 12y ago
I absolutely love project Euler. The math on the harder problems is way over my head but it is still my go-to site whenever I want to learn a new language. By the time you've done a bunch of them you'll be more than underway in understanding the territory and in a much better position to understand tutorials (which inevitably are written by experts in the language and usually make a ton of assumptions). Alternating between project Euler, a book (or two), back to project Euler for a bit is a very fast school, and you determine how fast you can pace yourself.
- acadien 12y ago
  Yes, I do exactly the same thing! The first 20 problems in particular are excellent for learning a new language. It covers basic math, list operations, file IO, string parsing; in other words all the basics in learning a new language. Plus several of the problems are strung together and encourage you to build up a structured library of tools to help you solve any number of problems.
- ipsin 12y ago
  One of my favorite parts of Project Euler was getting something where the math seemed beyond me, but I could use a tool like Google to get further. Not to cheat using Google, but to discover the name of the branch of mathematics I had no clue about, and then to learn enough to keep going. I still remember the afternoon I spent doing chromatic polynomials by hand, each graph I drew having more mental exclamations on the end, because I was goddamn getting it. For me, the lift from earning a right answer is palpable.
  - jacquesm 12y ago
    Yes! I had that same feeling with this one: https://projecteuler.net/problem=307 https://projecteuler.net/problem=307 I couldn't solve it analytically for the life of me. So I wrote a small simulator, computed the answer to within 7 decimal places or so and then tried to figure out why that was the right answer. Then the lightbulb went on and I realized what the real answer should be and it worked. As I wrote above, I am not very good at math, but to be able to use the computer to make your math understanding better than what it was before you started solving a problem was a huge up for me.
    - jules 12y ago
      Can you solve that problem analytically? The straightforward answer is to set up a recurrence relation for p(k,n) and use dynamic programming, but even then it's far too laborious to compute p(20000,1000000) without a computer.
      - jacquesm 12y ago
        Now I can, but initially I had no idea. But the simulation can be coded up in 15 minutes or so and you'll have your first 3 decimal places in a few minutes after that. To get to 9 decimal places takes a while longer.
        jules 12y ago
        By analytically, do you mean by hand, or just getting the exact answer by computer? Can project euler problems often be solved by hand? For example this 500th problem doesn't seem very hard with a computer, but doing it by hand seems like it will take a long long time.
        jacquesm 12y ago
        No, it's still by computer. But some of them I can do by hand but that's only a few so far.
        hyperbovine 12y ago
        There is an elegant way to solve these types of problems analytically using a technique called Poissonization. The aspect that makes computing the correct answer difficult is the dependence among counts for the various chips. Instead imagine the the number of defects is now Poisson distributed with mean lambda. A convenient property of the Poisson distribution is its "binning" property whereby the number of defects hitting each chip as now Poisson(lambda/n) and, most important, the counts are mutually independent. From here you can compute the correct answer by a power series argument. I'll spare you the details but see http://bulletin.imstat.org/2014/02/student-puzzle-corner/ http://bulletin.imstat.org/2014/02/student-puzzle-corner/ for a worked example.
- trentmb 12y ago
  I'm hardly in the position to be telling you how you learn a language best, but I always felt programming type puzzles of the oj.leetcode.com variety were better for getting me to learn a programming language, where as projecteuler.net was better at developing mathematical/algorithmic reasoning skills. A non-trivial amount of the early puzzles are do-able by hand. Anyone else feel similarly?
  - jacquesm 12y ago
    I will check that out, thank you for the pointer.
  - a3n 12y ago
    Project Euler is like sex or diabetes (both of which I have or have had), what it means to you and how it fits into your life is very much an individual thing. Yes, a lot of the problems can be done by hand. You could treat the problems as "a math problem to solve", or as "an exercise in solving a problem with software." When you've solved a problem, you have either "obtained the correct answer," or you have "figured out how to obtain the correct answer with software." Or both. For me, even solving the early trivial ones, that could be done by hand, are more an exercise in software than in math. Most of the time, I try to write my solutions in a general way, so that I can change the parameters of the problem, run it through software I've already written, and get the right results. The challenge then is defining the boundaries and parameters, and imagining the possible and reasonable limits of those boundaries and parameters. Just like we do every day with the rest of our software challenges. The fact that these are math problems make it more fun for me, because I am not at all mathematically inclined. So I have to learn a little more math, and then decide if I've learned it sufficiently that my solution is reasonable. Reading other people's posted solutions is almost as fun as solving the puzzle. I've learned a lot, or at least been impressed, from the various languages and hand solutions. As for learning a new language, I think Euler is a reasonable tool in the total box. I find that I don't really know a new language until I've struggled with something "real" that matters, to me or my employer. And even then, if I come back to code a year or two later, I sometimes cringe, since I've likely learned more about using the language's strengths in that time, beyond just writing C in a new language.
- platz 12y ago
  Exercism.io
  - morenoh149 12y ago
    looks dope
- Bsharp 12y ago
  I agree 100%! I first learned to program in Python using Project Euler and they taught me a ton. Now I've solved 111 of them! I'm currently trying to learn Rust, and since it's so new everything is geared towards people with experience. So I started Rust For Beginners: http://www.rustforbeginners.com http://www.rustforbeginners.com I'm trying to make it a guide to the language, and programming in general, for true beginners. The very first post of actual coding (after installing, command line basics, and compiling/running with cargo) is a walk through of the first PE problem. I know how you feel about most beginners guides not actually being suited for beginners. Since I'm a beginner, I'm hoping I'll be able to write one. Feel free to check it out, and constructive criticism is encouraged!
- deleted 12y ago
  [deleted]
- zura 12y ago
  Unless you're switching from e.g. Java to e.g. Prolog or Erlang (or Haskell...), is it really useful for learning a new language? I mean, when learning a new language, the basic syntax is the easiest part anyway, but the ecosystem/batteries/best_practices is where the main bottleneck is. And I have an impression that Project Euler problems will help you only with the very basics of the language.
- jschulenklopper 12y ago
  > it is still my go-to site whenever I want to learn a new language The great thing about Project Euler for this is that the correct answer isn't a piece of code or an algorithm in some language, but just a number. Project Euler does not really care how that number was derived. Using a mathematical formula, plain pencil and paper, a program in some language, or cheating via Google-fu? Euler doesn't care. Because of this, it is very inviting to code a solution in a different language: 1) to learn that language, 2) to use a concept of the language with a better fit with the problem, 3) to see which language yields the quickest answer, measured in development time or actual run time. The drawback of Project Euler is that it's quite addictive.
ipsin 12y ago
Happy 500th! If you've never tried Project Euler, it's a great way to learn new mathematical concepts, sequences, dynamic programming and other algorithms. https://projecteuler.net/problem=368 https://projecteuler.net/problem=368 was one of my favorites, because it involved turning an algorithm described in a paper into code. I don't consider this a spoiler for problem #500, but if you're counting the number of divisors, you'll need this function: http://oeis.org/wiki/Number_of_divisors_function#Formulae_for_the_number_of_divisors_function http://oeis.org/wiki/Number_of_divisors_function#Formulae_fo... As an example, 120 = 2^3 * 3^1 * 5^1 number of divisors of 120 => (3+1)(1+1)(1+1) Even if you don't solve it, exploring the problem is a fun afternoon for a person with a computer.
- sdenton4 12y ago
  I love the way the harmonic series seems to juuuuuuust baaaaarely diverge....
  - ipsin 12y ago
    One of the things that's freaky to me is that the harmonic series up to n terms is proportional to log(n)... but the sum of the reciprocals of the primes is roughly proportional to log(log(n)). That's a crazy slow divergence.
    - cperciva 12y ago
      For even more crazy, consider the following series: H(n) = 1/1 + 1/2 + ... + 1/n H_2(n) = 1 / (H(1)) + 1 / (2 H(2)) + 1 / (3 H(3)) + ... + 1 / (n H(n)) H_3(n) = 1 / (H(1) H_2(1)) + 1 / (2 H(2) H_2(2)) + 1 / (3 H(3) H_2(3)) + ... + 1 / (n H(n) H_2(n)) ... H_k(n) = 1 / (H(1) H_2(1) ... H_{k-1}(1)) + 1 / (2 H(2) H_2(2) ... H_{k-1}(2)) + ... + 1 / (n H(n) H_2(n) ... H_{k-1}(n)) The series H_k(n) diverges roughly proportional to log(log(... k logs ... (log(n)) ...)).
    - gjm11 12y ago
      The n'th prime looks a bit like n log n. (This is basically the same fact as the "prime number theorem": the number of primes up to n is roughly n/log(n).) We have: sum (up to n) of 1/x ~= log n [harmonic series] sum (up to n) of 1/(x log x) ~= log log n [reciprocals of primes, roughly] sum (up to n) of 1/(x log x log log x) ~= log log log n and so on. All these series diverge, but slower and slower and slower. And clearly these series "only just" diverge. In fact, iIf you take, e.g., sum of 1/(x log x log log x (log log log x)^1.1) then it converges. If you have just the right kind of warped mind, the question that will immediately occur to you on contemplating this is: what if you define L(x) := x log x log log x log log log x ... continuing the product up to, but excluding, the first factor that's < 1, and ask about the sum of 1/L(x)? Answer: The series diverges really slowly. The points at which L(x) starts to use one extra logarithm are e, e^e, e^e^e, e^e^e^e, etc. The sums between each adjacent pair of these are comparable in size. So the sum up to n is roughly the number of times you need to take logs, starting with n, before you get down to 1. [EDITED to add: The first bit of the above is closely related to cperciva's comment that's a sibling of this one.]
joshstrange 12y ago
I was only recently introduced to Project Euler but already I'm addicted. I've got a folder where I've named each solution as pXXX.ext and try solving the problems in multiple different languages. I refuse to move on to a new problem until I've solved the previous one (I don't solve every problem in multiple languages. Instead I've been using it to learn/play with languages here and there I don't really know). Congrats to Project Euler on their 500th problem!
- jacquesm 12y ago
  How far along are you?
  - joshstrange 12y ago
    Solved up to problem 25 so far, https://projecteuler.net/progress=joshstrange https://projecteuler.net/progress=joshstrange
    - KhalilK 12y ago
      Only friends' progress can be viewed, sharing this picture[0] would do the job ;) 0.https://projecteuler.net/profile/joshstrange.png https://projecteuler.net/profile/joshstrange.png
      - jacquesm 12y ago
        Oh, I believed him. I'm actually at 24 (in Erlang).
        KhalilK 12y ago
        I was just pointing it out :) I solved 50 of them, I usually use Java, or Mathematica which feels...cheaty but sometimes all it takes is a paper and a pencil.
        jacquesm 12y ago
goalieca 12y ago
Every couple of years I get addicted for a few weeks. Love the effort these guys put into the problems.
- deleted 12y ago
  [deleted]
- RobertKing 12y ago
  Same here - each time I learn a new programming language I like to solve a bunch.
kyberias 12y ago
For Project Euler enthusiasts: here's a similar site focused on bioinformatics that I've found very very good: http://rosalind.info/ http://rosalind.info/ Also suitable for learning new languages (and bioinformatics). The implementation of the site is awesome.
- dhbradshaw 12y ago
  Rosalind is a great way to pick up some bio along with your algorithms. The instructors also created a course on Coursera called "Bioinformatics Algorithms" that I highly recommend. It's basically an ordered set of rosalind problems but accompanied by a textbook and lectures. It was one of the most interesting things I did last year.
  - bhrgunatha 12y ago
    Agreed - it's one of the most enjoyable Coursera courses I've taken. Part Two starts February 16th. [1] To expand a bit, what I liked about the course was the textbook, algorithms and their practical application in a non-CS field with a good set of programming problems that are automatically assessed. [1] https://www.coursera.org/course/bioinformatics2 https://www.coursera.org/course/bioinformatics2
dhbradshaw 12y ago
After you solve a problem Project Euler lets you browse through a giant list of solutions by those who have gone before. It's really fun to see and compare all the different approaches. If I could do one thing to augment the project I would make it possible to filter previous solutions by language and/or author. For example, if I'm learning rust, I would love to see all the rust solutions right there together.
bhaumik 12y ago
"Saturday 31st of January Project Euler will reach a major milestone with the publication of our 500th problem. To celebrate this the team has composed a special problem in which the number 500 occurs repeatedly. In addition we're going to publish an ordinary problem simultaneously as problem 501. Both problems are published at 13:00 London time. We invite all members to participate in our problem solving party. As celebrator of this jubilee we're allowed to ask the participants for a present. Well, here's our wish: please don't share any information about our party and the dishes we're serving you outside the fora dedicated to our dishes after your meal. This to allow those that are late to the party to consume our dishes undisturbed by premature revelations about what we are serving." https://projecteuler.net/news https://projecteuler.net/news
bhaumik 12y ago
If you're interesting in the birth, inspiration and pedagogy behind Project Euler, I recommend this article [1]. And it's an effective teacher because those problems are arranged like the programs in the ORIC-1's manual, in what Hughes calls an "inductive chain": The problems range in difficulty and for many the experience is inductive chain learning. That is, by solving one problem it will expose you to a new concept that allows you to undertake a previously inaccessible problem. So the determined participant will slowly but surely work his/her way through every problem. [1]http://www.theatlantic.com/technology/print/2011/06/how-i-failed-failed-and-finally-succeeded-at-learning-how-to-code/239855/ http://www.theatlantic.com/technology/print/2011/06/how-i-fa...
imslavko 12y ago
This is a nice little problem, I had fun solving it. For those of us who are familiar with TopCoder, CodeForces or, perhaps, ACM ICPC, this should be daily bread and butter on prime numbers and data structures :) Here is my solution if you are curious: https://gist.github.com/Slava/74276f5b7889a1d68a71 https://gist.github.com/Slava/74276f5b7889a1d68a71 - computes the result in 400ms Edit: hah, looking at the problems discussion board I took a very bruteforce approach, other people solved utilizing math, I used priority_queue for no particular reason :)
sargun 12y ago
I was asked this question at an interview at $COMPANY last week. Heh. I failed pretty miserably.
fishtastic 12y ago
Screamed at JavaScript for failing at big integer multiplications. Got it after rewriting in python. Here is my poorly written explanation. --------- MAJOR SPOILERS --------- Let's multiply unique prime numbers and count their factors. n Number of factors 2 2 (1, 2) 2x3 4 (1, 2, 3, 6) 2x3x5 8 2x3x5x7 16 Notice that each time you add a new prime number, the factor count doubles i.e. 2x3x5x...x500500th prime will have 2^500500 factors The 500500th prime is 7376507 (thanks to wolframalpha), and it's not very big. We can easily get the product of the above with 500500 multiplications while modding result of each step by 500500507 to get an answer. Except that the product of first 500500 primes isn't the smallest number containing 2^500500 factors. This can be made smaller. Observe that (2x3x5x...x500499th prime)x2 has 2^500499 + 2^500498 factors. This is because with the extra 2 we added, it produces additional factors with existing factors that are a multiples of 2. Continuing with this, we see that (2x3x5x...x500499th prime) x (2 x 2) has 2^500499 + 2^500498 + 2^500498 = 2^500500 factors. This is a better solution, since 2x2 is smaller than the 500500th prime. If we want continue doubling factor count by multiplying 2s, we will need to multiply by 2x2x2x2 next, and 2^8 after, which becomes inefficient quickly. Instead, why not use 3? Multiplying (2x3x5x...x500499th prime) by (3 x 3) also doubles the factor count. So at this point, we think about doubling factor count and the ways we can do it. Out options are <1>. Multiply by a prime that we have never used so far <2>. Multiply by an existing prime k + 1 times, where k is the number of times it has been used We repeat this 500500 times, using rule <1> and <2> (which can be generalized to one rule) and the result is the final answer. factor count n 2 2 4 2*3 <1> 8 2*3*2*2 <2> 16 2*3*2*2*5 <1> 32 2*3*2*2*5*7 <1> 64 2*3*2*2*5*7*3*3 <2> 128 2*3*2*2*5*7*3*3*11 <1> For 16 factors the number works out to be 120 (just like the example!). For numbers shown in the questions, sieving the prime takes some time, I also found it helpful to use a binary heap for speeding up finding the next smallest factors.
- thaumasiotes 12y ago
  This relies heavily on requiring that the number of factors be exactly 2^500500. Can we find the smallest number with at least 2^500500 divisors?
florianletsch 12y ago
I love Project Euler. In this thread I've found references for similar projects but focussed more on actual coding (http:(http://oj.leetcode.com http://oj.leetcode.com) or on BioInformatics (http://rosalind.info/problems/locations/ http://rosalind.info/problems/locations/). Any chance you guys know of a similar project for Computer Vision or general AI topics?
- fela 12y ago
  https://www.hackerrank.com/ https://www.hackerrank.com/ has a AI/Machine Learning section
- dman 12y ago
  Thanks for posting this.

254 points by bhaumik 12y ago

I absolutely love project Euler. The math on the harder problems is way over my head but it is still my go-to site whenever I want to learn a new language. By the time you've done a bunch of them you'll be more than underway in understanding the territory and in a much better position to understand tutorials (which inevitably are written by experts in the language and usually make a ton of assumptions). Alternating between project Euler, a book (or two), back to project Euler for a bit is a very fast school, and you determine how fast you can pace yourself.

acadien 12y ago
Yes, I do exactly the same thing! The first 20 problems in particular are excellent for learning a new language. It covers basic math, list operations, file IO, string parsing; in other words all the basics in learning a new language. Plus several of the problems are strung together and encourage you to build up a structured library of tools to help you solve any number of problems.
ipsin 12y ago
One of my favorite parts of Project Euler was getting something where the math seemed beyond me, but I could use a tool like Google to get further. Not to cheat using Google, but to discover the name of the branch of mathematics I had no clue about, and then to learn enough to keep going. I still remember the afternoon I spent doing chromatic polynomials by hand, each graph I drew having more mental exclamations on the end, because I was goddamn getting it. For me, the lift from earning a right answer is palpable.
- jacquesm 12y ago
  Yes! I had that same feeling with this one: https://projecteuler.net/problem=307 https://projecteuler.net/problem=307 I couldn't solve it analytically for the life of me. So I wrote a small simulator, computed the answer to within 7 decimal places or so and then tried to figure out why that was the right answer. Then the lightbulb went on and I realized what the real answer should be and it worked. As I wrote above, I am not very good at math, but to be able to use the computer to make your math understanding better than what it was before you started solving a problem was a huge up for me.
  - jules 12y ago
    Can you solve that problem analytically? The straightforward answer is to set up a recurrence relation for p(k,n) and use dynamic programming, but even then it's far too laborious to compute p(20000,1000000) without a computer.
    - jacquesm 12y ago
      Now I can, but initially I had no idea. But the simulation can be coded up in 15 minutes or so and you'll have your first 3 decimal places in a few minutes after that. To get to 9 decimal places takes a while longer.
      - jules 12y ago
        By analytically, do you mean by hand, or just getting the exact answer by computer? Can project euler problems often be solved by hand? For example this 500th problem doesn't seem very hard with a computer, but doing it by hand seems like it will take a long long time.
        jacquesm 12y ago
        No, it's still by computer. But some of them I can do by hand but that's only a few so far.
        hyperbovine 12y ago
        There is an elegant way to solve these types of problems analytically using a technique called Poissonization. The aspect that makes computing the correct answer difficult is the dependence among counts for the various chips. Instead imagine the the number of defects is now Poisson distributed with mean lambda. A convenient property of the Poisson distribution is its "binning" property whereby the number of defects hitting each chip as now Poisson(lambda/n) and, most important, the counts are mutually independent. From here you can compute the correct answer by a power series argument. I'll spare you the details but see http://bulletin.imstat.org/2014/02/student-puzzle-corner/ http://bulletin.imstat.org/2014/02/student-puzzle-corner/ for a worked example.
trentmb 12y ago
I'm hardly in the position to be telling you how you learn a language best, but I always felt programming type puzzles of the oj.leetcode.com variety were better for getting me to learn a programming language, where as projecteuler.net was better at developing mathematical/algorithmic reasoning skills. A non-trivial amount of the early puzzles are do-able by hand. Anyone else feel similarly?
- jacquesm 12y ago
  I will check that out, thank you for the pointer.
- a3n 12y ago
  Project Euler is like sex or diabetes (both of which I have or have had), what it means to you and how it fits into your life is very much an individual thing. Yes, a lot of the problems can be done by hand. You could treat the problems as "a math problem to solve", or as "an exercise in solving a problem with software." When you've solved a problem, you have either "obtained the correct answer," or you have "figured out how to obtain the correct answer with software." Or both. For me, even solving the early trivial ones, that could be done by hand, are more an exercise in software than in math. Most of the time, I try to write my solutions in a general way, so that I can change the parameters of the problem, run it through software I've already written, and get the right results. The challenge then is defining the boundaries and parameters, and imagining the possible and reasonable limits of those boundaries and parameters. Just like we do every day with the rest of our software challenges. The fact that these are math problems make it more fun for me, because I am not at all mathematically inclined. So I have to learn a little more math, and then decide if I've learned it sufficiently that my solution is reasonable. Reading other people's posted solutions is almost as fun as solving the puzzle. I've learned a lot, or at least been impressed, from the various languages and hand solutions. As for learning a new language, I think Euler is a reasonable tool in the total box. I find that I don't really know a new language until I've struggled with something "real" that matters, to me or my employer. And even then, if I come back to code a year or two later, I sometimes cringe, since I've likely learned more about using the language's strengths in that time, beyond just writing C in a new language.
platz 12y ago
Exercism.io
- morenoh149 12y ago
  looks dope
Bsharp 12y ago
I agree 100%! I first learned to program in Python using Project Euler and they taught me a ton. Now I've solved 111 of them! I'm currently trying to learn Rust, and since it's so new everything is geared towards people with experience. So I started Rust For Beginners: http://www.rustforbeginners.com http://www.rustforbeginners.com I'm trying to make it a guide to the language, and programming in general, for true beginners. The very first post of actual coding (after installing, command line basics, and compiling/running with cargo) is a walk through of the first PE problem. I know how you feel about most beginners guides not actually being suited for beginners. Since I'm a beginner, I'm hoping I'll be able to write one. Feel free to check it out, and constructive criticism is encouraged!
deleted 12y ago
[deleted]
zura 12y ago
Unless you're switching from e.g. Java to e.g. Prolog or Erlang (or Haskell...), is it really useful for learning a new language? I mean, when learning a new language, the basic syntax is the easiest part anyway, but the ecosystem/batteries/best_practices is where the main bottleneck is. And I have an impression that Project Euler problems will help you only with the very basics of the language.
jschulenklopper 12y ago
> it is still my go-to site whenever I want to learn a new language The great thing about Project Euler for this is that the correct answer isn't a piece of code or an algorithm in some language, but just a number. Project Euler does not really care how that number was derived. Using a mathematical formula, plain pencil and paper, a program in some language, or cheating via Google-fu? Euler doesn't care. Because of this, it is very inviting to code a solution in a different language: 1) to learn that language, 2) to use a concept of the language with a better fit with the problem, 3) to see which language yields the quickest answer, measured in development time or actual run time. The drawback of Project Euler is that it's quite addictive.

ipsin 12y ago

Happy 500th! If you've never tried Project Euler, it's a great way to learn new mathematical concepts, sequences, dynamic programming and other algorithms. https://projecteuler.net/problem=368 https://projecteuler.net/problem=368 was one of my favorites, because it involved turning an algorithm described in a paper into code. I don't consider this a spoiler for problem #500, but if you're counting the number of divisors, you'll need this function: http://oeis.org/wiki/Number_of_divisors_function#Formulae_for_the_number_of_divisors_function http://oeis.org/wiki/Number_of_divisors_function#Formulae_fo... As an example, 120 = 2^3 * 3^1 * 5^1 number of divisors of 120 => (3+1)(1+1)(1+1) Even if you don't solve it, exploring the problem is a fun afternoon for a person with a computer.

sdenton4 12y ago
I love the way the harmonic series seems to juuuuuuust baaaaarely diverge....
- ipsin 12y ago
  One of the things that's freaky to me is that the harmonic series up to n terms is proportional to log(n)... but the sum of the reciprocals of the primes is roughly proportional to log(log(n)). That's a crazy slow divergence.
  - cperciva 12y ago
    For even more crazy, consider the following series: H(n) = 1/1 + 1/2 + ... + 1/n H_2(n) = 1 / (H(1)) + 1 / (2 H(2)) + 1 / (3 H(3)) + ... + 1 / (n H(n)) H_3(n) = 1 / (H(1) H_2(1)) + 1 / (2 H(2) H_2(2)) + 1 / (3 H(3) H_2(3)) + ... + 1 / (n H(n) H_2(n)) ... H_k(n) = 1 / (H(1) H_2(1) ... H_{k-1}(1)) + 1 / (2 H(2) H_2(2) ... H_{k-1}(2)) + ... + 1 / (n H(n) H_2(n) ... H_{k-1}(n)) The series H_k(n) diverges roughly proportional to log(log(... k logs ... (log(n)) ...)).
  - gjm11 12y ago
    The n'th prime looks a bit like n log n. (This is basically the same fact as the "prime number theorem": the number of primes up to n is roughly n/log(n).) We have: sum (up to n) of 1/x ~= log n [harmonic series] sum (up to n) of 1/(x log x) ~= log log n [reciprocals of primes, roughly] sum (up to n) of 1/(x log x log log x) ~= log log log n and so on. All these series diverge, but slower and slower and slower. And clearly these series "only just" diverge. In fact, iIf you take, e.g., sum of 1/(x log x log log x (log log log x)^1.1) then it converges. If you have just the right kind of warped mind, the question that will immediately occur to you on contemplating this is: what if you define L(x) := x log x log log x log log log x ... continuing the product up to, but excluding, the first factor that's < 1, and ask about the sum of 1/L(x)? Answer: The series diverges really slowly. The points at which L(x) starts to use one extra logarithm are e, e^e, e^e^e, e^e^e^e, etc. The sums between each adjacent pair of these are comparable in size. So the sum up to n is roughly the number of times you need to take logs, starting with n, before you get down to 1. [EDITED to add: The first bit of the above is closely related to cperciva's comment that's a sibling of this one.]

joshstrange 12y ago

I was only recently introduced to Project Euler but already I'm addicted. I've got a folder where I've named each solution as pXXX.ext and try solving the problems in multiple different languages. I refuse to move on to a new problem until I've solved the previous one (I don't solve every problem in multiple languages. Instead I've been using it to learn/play with languages here and there I don't really know). Congrats to Project Euler on their 500th problem!

jacquesm 12y ago
How far along are you?
- joshstrange 12y ago
  Solved up to problem 25 so far, https://projecteuler.net/progress=joshstrange https://projecteuler.net/progress=joshstrange
  - KhalilK 12y ago
    Only friends' progress can be viewed, sharing this picture[0] would do the job ;) 0.https://projecteuler.net/profile/joshstrange.png https://projecteuler.net/profile/joshstrange.png
    - jacquesm 12y ago
      Oh, I believed him. I'm actually at 24 (in Erlang).
      - KhalilK 12y ago
        I was just pointing it out :) I solved 50 of them, I usually use Java, or Mathematica which feels...cheaty but sometimes all it takes is a paper and a pencil.
        jacquesm 12y ago

goalieca 12y ago

Every couple of years I get addicted for a few weeks. Love the effort these guys put into the problems.

deleted 12y ago
[deleted]
RobertKing 12y ago
Same here - each time I learn a new programming language I like to solve a bunch.

kyberias 12y ago

For Project Euler enthusiasts: here's a similar site focused on bioinformatics that I've found very very good: http://rosalind.info/ http://rosalind.info/ Also suitable for learning new languages (and bioinformatics). The implementation of the site is awesome.

dhbradshaw 12y ago
Rosalind is a great way to pick up some bio along with your algorithms. The instructors also created a course on Coursera called "Bioinformatics Algorithms" that I highly recommend. It's basically an ordered set of rosalind problems but accompanied by a textbook and lectures. It was one of the most interesting things I did last year.
- bhrgunatha 12y ago
  Agreed - it's one of the most enjoyable Coursera courses I've taken. Part Two starts February 16th. [1] To expand a bit, what I liked about the course was the textbook, algorithms and their practical application in a non-CS field with a good set of programming problems that are automatically assessed. [1] https://www.coursera.org/course/bioinformatics2 https://www.coursera.org/course/bioinformatics2

dhbradshaw 12y ago

After you solve a problem Project Euler lets you browse through a giant list of solutions by those who have gone before. It's really fun to see and compare all the different approaches. If I could do one thing to augment the project I would make it possible to filter previous solutions by language and/or author. For example, if I'm learning rust, I would love to see all the rust solutions right there together.

bhaumik 12y ago

"Saturday 31st of January Project Euler will reach a major milestone with the publication of our 500th problem. To celebrate this the team has composed a special problem in which the number 500 occurs repeatedly. In addition we're going to publish an ordinary problem simultaneously as problem 501. Both problems are published at 13:00 London time. We invite all members to participate in our problem solving party. As celebrator of this jubilee we're allowed to ask the participants for a present. Well, here's our wish: please don't share any information about our party and the dishes we're serving you outside the fora dedicated to our dishes after your meal. This to allow those that are late to the party to consume our dishes undisturbed by premature revelations about what we are serving." https://projecteuler.net/news https://projecteuler.net/news

bhaumik 12y ago

If you're interesting in the birth, inspiration and pedagogy behind Project Euler, I recommend this article [1]. And it's an effective teacher because those problems are arranged like the programs in the ORIC-1's manual, in what Hughes calls an "inductive chain": The problems range in difficulty and for many the experience is inductive chain learning. That is, by solving one problem it will expose you to a new concept that allows you to undertake a previously inaccessible problem. So the determined participant will slowly but surely work his/her way through every problem. [1]http://www.theatlantic.com/technology/print/2011/06/how-i-failed-failed-and-finally-succeeded-at-learning-how-to-code/239855/ http://www.theatlantic.com/technology/print/2011/06/how-i-fa...

imslavko 12y ago

This is a nice little problem, I had fun solving it. For those of us who are familiar with TopCoder, CodeForces or, perhaps, ACM ICPC, this should be daily bread and butter on prime numbers and data structures :) Here is my solution if you are curious: https://gist.github.com/Slava/74276f5b7889a1d68a71 https://gist.github.com/Slava/74276f5b7889a1d68a71 - computes the result in 400ms Edit: hah, looking at the problems discussion board I took a very bruteforce approach, other people solved utilizing math, I used priority_queue for no particular reason :)

sargun 12y ago

I was asked this question at an interview at $COMPANY last week. Heh. I failed pretty miserably.

fishtastic 12y ago

Screamed at JavaScript for failing at big integer multiplications. Got it after rewriting in python. Here is my poorly written explanation. --------- MAJOR SPOILERS --------- Let's multiply unique prime numbers and count their factors. n Number of factors 2 2 (1, 2) 2x3 4 (1, 2, 3, 6) 2x3x5 8 2x3x5x7 16 Notice that each time you add a new prime number, the factor count doubles i.e. 2x3x5x...x500500th prime will have 2^500500 factors The 500500th prime is 7376507 (thanks to wolframalpha), and it's not very big. We can easily get the product of the above with 500500 multiplications while modding result of each step by 500500507 to get an answer. Except that the product of first 500500 primes isn't the smallest number containing 2^500500 factors. This can be made smaller. Observe that (2x3x5x...x500499th prime)x2 has 2^500499 + 2^500498 factors. This is because with the extra 2 we added, it produces additional factors with existing factors that are a multiples of 2. Continuing with this, we see that (2x3x5x...x500499th prime) x (2 x 2) has 2^500499 + 2^500498 + 2^500498 = 2^500500 factors. This is a better solution, since 2x2 is smaller than the 500500th prime. If we want continue doubling factor count by multiplying 2s, we will need to multiply by 2x2x2x2 next, and 2^8 after, which becomes inefficient quickly. Instead, why not use 3? Multiplying (2x3x5x...x500499th prime) by (3 x 3) also doubles the factor count. So at this point, we think about doubling factor count and the ways we can do it. Out options are <1>. Multiply by a prime that we have never used so far <2>. Multiply by an existing prime k + 1 times, where k is the number of times it has been used We repeat this 500500 times, using rule <1> and <2> (which can be generalized to one rule) and the result is the final answer. factor count n 2 2 4 2*3 <1> 8 2*3*2*2 <2> 16 2*3*2*2*5 <1> 32 2*3*2*2*5*7 <1> 64 2*3*2*2*5*7*3*3 <2> 128 2*3*2*2*5*7*3*3*11 <1> For 16 factors the number works out to be 120 (just like the example!). For numbers shown in the questions, sieving the prime takes some time, I also found it helpful to use a binary heap for speeding up finding the next smallest factors.

thaumasiotes 12y ago
This relies heavily on requiring that the number of factors be exactly 2^500500. Can we find the smallest number with at least 2^500500 divisors?

florianletsch 12y ago

I love Project Euler. In this thread I've found references for similar projects but focussed more on actual coding (http:(http://oj.leetcode.com http://oj.leetcode.com) or on BioInformatics (http://rosalind.info/problems/locations/ http://rosalind.info/problems/locations/). Any chance you guys know of a similar project for Computer Vision or general AI topics?

fela 12y ago
https://www.hackerrank.com/ https://www.hackerrank.com/ has a AI/Machine Learning section
dman 12y ago
Thanks for posting this.