Problem 606

[Eventhorizon]

I know this is quite soon after the problem was posted, but I am finding myself in recent problems coming up against issues to do with the sheer size of the numbers involved. Trying very hard not to give anything away, here's what I mean regarding this problem:

I have found an approach that gives me the answers correctly for 10^6 and 10^12. I am using an R script with a pre-built list of primes up to 10^8, and I believe I know the correct forms to calculate the numbers, k. Using vectorized calculations takes sub 1 second, so my approach seems promising. Let's say that some of the numbers, k, I am looking for have the form (they don't - I am trying not to spoil the problem): p(1)^3.p(2)^3.p(3)^4 where p(i) are distinct primes.

The largest prime I need is going to be of the order (10^36 / 2^4 / 3^3)^(1/3) which is around 10^12. According to Wikipedia there are ~37bn primes less than 10^12. I know I only need the last 9 digits of each for the problem, but I would still need to arrive at a list with around 37bn members.

Can someone take pity on an autodidact, math-wannabe and point me to an appropriate resource that will show me why I don't need to deal with such a long list, or shows me some way of dealing with such a long list without killing my computer. Or is the problem that R is simply the wrong tool for this job? Perhaps C or Python would have no problem ploughing through 37bn calculations in short order!

[MuthuVeerappanR]

Hi Eventhorizon, As you've already solved about 200 problems, I assume you've solved the first 10 problems. How about reviewing the posts of those 10 problems?

[v6ph1]

The limit of operations is around 10^11 to 10^12 per minute - depending on clock and the usage of parallelism.
I doubt, my own code will be fast enough too. But it should run in 1-2 hours.

3.7*10^10 operations in a minute is possible - but not that easy.

Interpreted code like R are not as fast as compiled code.

But you should think of your code - not every list needs to be stored in separate values.

[yourmaths]

I am in a similar position with this problem.
I've worked out the formula for the answer, and even a semi-smart way of calculating it without generating massive amounts of primes, but my estimate for the calculation time needed is still ~1000 hrs.

My rule of thumb is that if I find myself needing to generate a list of primes above 10^8, or have a for-loop with more than 10^8 or 10^9 iterations, then there's almost certainly a better way of looking at the problem.

[Eventhorizon]

Thanks MuthuVeerappanR, V6ph1, and yourmaths. I appreciate your feedback!

My guess is I need to better understand how to take advantage of the modular arithmetic part of problems such as this one. "Last 9 digits ..." essentially means answer mod 10^9. So I think I need try to do the S(10^12) example differently (less loops, shorter lists) as if I needed the answer mod 10^4. For example I could count the number of primes less than 10^6 whose last 4 digits are between 1001 and 9999, rather than figure out all the primes less than 10^6.

Anyone know of a good internet primer on modular arithmetic (assuming this is the area I need to understand better)? I suspect I also need better ways of implementing inclusion / exclusion.

This is why I love ProjectEuler - I love to learn!

[v6ph1]

One more hint: It is not necessary to generate all the primes as single numbers. You may can pack some of them together.
Have a look at the problem threads of the first 10 problems - there are sublinear algorithms for this.

You all need the primes (or some result of them)!
Modular calculation has the only the advantage to simplify the input of the result.

My current state:
Solutions for 10^6 and 10^12 are correct; 10^30 calculated in 13s.
10^36:
First try: 100mins - with compiler optimization: 72mins.
Using openmp: 18mins.

But: My solution is not accepted.

-> I'll work on more optimizations and I need to fix the overflow-error.

EDIT: Solved - but my code is a little bit slow

[Schu-ism]

I'm facing the same problem here. I know what I should be looking for but simply cannot think of a fundamentally superior algorithm.

My initial attempt took two and a half minutes to arrive at an answer for the case of 10^30. I was able to bring the run-time down to 90 seconds and eventually to around 60 seconds after drastically revising my code. However, the major issue I'm having is that my 60-second code gives a different result for 10^30 from my previous codes, and I suspect that numbers in the 10^30-case are already too large for a brute-force verification, so can anyone confirm whether the result (last 9 digits) for 10^30 contains at least one "9"?

[MuthuVeerappanR]

Yes... the last 9 digits for the 10^30 case contains exactly one 9..

[Schu-ism]

Thank you MuthuVeerappanR. I was able to locate two separate errors in my code, and now my program is giving me the correct answer for 10^30 in 69 seconds. (I'm not liking the silent overflow part of Java )