Euler Problem 234 Help - SPOILER ALERT

O

Oneos

Gawd
Joined
Sep 14, 2004
Messages
596
Alright, I'm working on Project Euler Problem 234. I read it over, thought - well that's easy, and set to it.

My code works for the two test cases (n <= 15 and n <= 1000) however upon trying to do the full, large number, its seemingly just sitting there. Now, is my code just incredibly inefficient, or am I running into an issue with data sizes somewhere along the way that I hadn't thought of? It was running for atleast 10 minutes on an 800mhz machine without spitting out an answer.

Thanks for any help in advance.

http://pastebin.com/m7f92f352
Code: 
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<long> vPrimes;

void sieve(long max);
long lps(long long n);
long ups(long long n);

int main()
{
    sieve(2000000);
    long long sum = 0;
       
    for (long long n = 4; n <= 999966663333LL; n++)
        if (n % lps(n) == 0 && n % ups(n) != 0 || n % lps(n) != 0 && n % ups(n) == 0)
           sum += n;
    
    cout << sum << endl;
    system("pause");
}

long lps(long long n)
{
     double nDbl = sqrt(double(n));
     
     for (long i = 0; i < vPrimes.size(); i++)
         if (vPrimes[i] == nDbl)
            return vPrimes[i];
         else if (i > 0 && nDbl > vPrimes[i - 1] && nDbl < vPrimes[i])
              return vPrimes[i - 1];
         else if (i > 0 && nDbl > vPrimes[i] && nDbl < vPrimes[i + 1])
              return vPrimes[i];
}

long ups(long long n)
{
     double nDbl = sqrt(double(n));
     
     for (long i = 0; i < vPrimes.size(); i++)
         if (vPrimes[i] == nDbl)
            return vPrimes[i];
         else if (i > 0 && nDbl > vPrimes[i - 1] && nDbl < vPrimes[i])
              return vPrimes[i];
         else if (i > 0 && nDbl > vPrimes[i] && nDbl < vPrimes[i + 1])
              return vPrimes[i + 1];
}

void sieve(long max)
{
     vector<bool> vNotPrime;
     vNotPrime.resize(max);
     
     for (long i = 2; i < max; i++)
         if (!vNotPrime[i])
         {
            vPrimes.push_back(i);
            for (long a = i + i; a < max; a += i)
                vNotPrime[a] = true;
         }
}
 
Your code has some very obvious inefficiencies, and some rather subtle ones. And I think it has at least one logic error. How much detail do you want in your answer?
 
Well, I've done some modifications which I think would speed it up at least a bit, but still nowhere near where it should be. I'm confident this would eventually give me the right answer. So, with that in mind, be as detailed as you'd like. I'm obviously not the most experienced out there, but I do what I can.

http://pastebin.com/m585fc170
Code: 
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<long> vPrimes;
long lasti = 0;

void sieve(long max);
long lps(long long n);
long ups(long long n);

int main()
{
    sieve(2000000);
    long long sum = 0;
       
    for (long long n = 4; n <= 999966663333LL; n++)
    {
        int modl = n % lps(n);
        int modu = n % ups(n);
        if (modl == 0 && modu != 0 || modl != 0 && modu == 0)
           sum += n;
    }
    
    cout << sum << endl;
    system("pause");
}

long lps(long long n)
{
     double nDbl = sqrt(double(n));
     
     for (long i = lasti; i < vPrimes.size(); i++)
         if (vPrimes[i] == nDbl)
         {
            lasti = i;
            return vPrimes[i];
         }
         else if (i > 0 && nDbl > vPrimes[i - 1] && nDbl < vPrimes[i])
         {
              lasti = i;
              return vPrimes[i - 1];
         }
         else if (i > 0 && nDbl > vPrimes[i] && nDbl < vPrimes[i + 1])
         {
              lasti = i;
              return vPrimes[i];
         }
}

long ups(long long n)
{
     double nDbl = sqrt(double(n));
     
     if (vPrimes[lasti] == nDbl)
        return vPrimes[lasti];
     else if (lasti > 0 && nDbl > vPrimes[lasti - 1] && nDbl < vPrimes[lasti])
          return vPrimes[lasti];
     else if (lasti > 0 && nDbl > vPrimes[lasti] && nDbl < vPrimes[lasti + 1])
          return vPrimes[lasti + 1];
}

void sieve(long max)
{
     vector<bool> vNotPrime;
     vNotPrime.resize(max);
     
     for (long i = 2; i < max; i++)
         if (!vNotPrime[i])
         {
            vPrimes.push_back(i);
            for (long a = i + i; a < max; a += i)
                vNotPrime[a] = true;
         }
}
 
Spreading out that if statement helps. But I think it still has a logic error. Did you test your program against the smaller examples that are given in the problem?

Analyzing the code shows that you're doing a ton of work. The loop in main will call the lps() and ups() functions 999,966,663,329 times. That's almost a trillion calls.

ups is pretty simple; it shouldn't take long to execute, though executing anything a trillion times is going to take a while.

How many times does the loop in lps() execute? Is there a way to speed up either of these functions?
 
Thanks for responding. Yes, the program returns the correct answer for both of the examples outlined in the problem.

I know by adding the "lasti" variable, I cut out the need for the loop in ups(), as it will always be found in the same position as it was in lps().

The actual loop in lps(), would never run its entire course, it'd most often jump in steps of staying on "lasti" for a good while, then moving to the next position in "vPrimes[]" which I believe would always be the correct position. I don't need to break the loop, since I'm returning for the function, (yes?).

For how I began my implementation, I can't really see a better way to do with what I have. Maybe there's some crazy mathematical algorithm (as I like to call them) that would be doing it much faster, as these problems should be able to be computed in under a minute.
 
Hey there,

ive been trying to solve this one myself. I think the real trick here will be finding some pattern or property of semi divisible numbers, because brute forcing close to a trillion doesnt seem like the proper way of solving this.

We should look for a way of determing the answer without having to iterate a trillion times :)
 
marathonman said:
We should look for a way of determing the answer without having to iterate a trillion times :)
Click to expand...

Blasphemy!

But, to appease. Here's a printout of the semidivisible numbers <= 1000.

Lets see, common differences: 2, 2, 6, 2, 3, 1, 3 -> nope
Multiples? 8... no 16, that fails

I'm out of ideas, but yes you're right, there must be some way to reduce the amount of iterations we need to do, 999 966 663 329 times does seem a little excessive.

Code: 
                   8                  10                  12                  18
                  20                  21                  24                  28
                  30                  40                  42                  45
                  55                  56                  63                  66
                  70                  84                  88                  91
                  98                  99                 105                 110
                 112                 119                 130                 132
                 154                 156                 165                 170
                 182                 187                 195                 204
                 208                 234                 238                 247
                 255                 260                 272                 273
                 286                 304                 306                 340
                 342                 357                 368                 380
                 391                 399                 414                 418
                 456                 460                 475                 483
                 494                 506                 513                 551
                 552                 575                 580                 598
                 609                 621                 638                 644
                 690                 696                 713                 725
                 736                 754                 759                 782
                 783                 805                 812                 828
                 868                 870                 928                 930
                 957                 962                 992                 999
 
I printed out the semi divisible number , along with the lps and ups. Im starting to see a pattern here .... maybe if we can group the lps and ups, can heavily reduce the iterations

8 2 3
10 3 5
12 3 5
18 3 5
20 3 5
21 3 5
24 3 5
28 5 7
30 5 7
40 5 7
42 5 7
45 5 7
55 7 11
56 7 11
63 7 11
66 7 11
70 7 11
84 7 11
88 7 11
91 7 11
98 7 11
99 7 11
105 7 11
110 7 11
112 7 11
119 7 11
130 11 13
132 11 13
154 11 13
156 11 13
165 11 13
170 13 17
182 13 17
187 13 17
195 13 17
204 13 17
208 13 17
234 13 17
238 13 17
247 13 17
255 13 17
260 13 17
272 13 17
273 13 17
286 13 17
304 17 19
306 17 19
340 17 19
342 17 19
357 17 19
368 19 23
380 19 23
391 19 23
399 19 23
414 19 23
418 19 23
456 19 23
460 19 23
475 19 23
483 19 23
494 19 23
506 19 23
513 19 23
551 23 29
552 23 29
575 23 29
580 23 29
598 23 29
609 23 29
621 23 29
638 23 29
644 23 29
690 23 29
696 23 29
713 23 29
725 23 29
736 23 29
754 23 29
759 23 29
782 23 29
783 23 29
805 23 29
812 23 29
828 23 29
868 29 31
870 29 31
928 29 31
930 29 31
957 29 31
962 31 37
992 31 37
999 31 37
Click to expand...
 
I was looking at the same kind of thing, was going to post it too. Here's what I'm looking at:

Unfortunately, with this data, I still don't see any sort of pattern that would allow us to determine semidivisible numbers without going through every number to check.
Code: 
n : lps(n) : ups(n) : ups(n) - lps(n) [difference]
lps of 0 occured 0 times.
8 : 2 : 3 : 1
lps of 2 occured 1 times.
10 : 3 : 5 : 2
12 : 3 : 5 : 2
18 : 3 : 5 : 2
20 : 3 : 5 : 2
21 : 3 : 5 : 2
24 : 3 : 5 : 2
lps of 3 occured 6 times.
28 : 5 : 7 : 2
30 : 5 : 7 : 2
40 : 5 : 7 : 2
42 : 5 : 7 : 2
45 : 5 : 7 : 2
lps of 5 occured 5 times.
55 : 7 : 11 : 4
56 : 7 : 11 : 4
63 : 7 : 11 : 4
66 : 7 : 11 : 4
70 : 7 : 11 : 4
84 : 7 : 11 : 4
88 : 7 : 11 : 4
91 : 7 : 11 : 4
98 : 7 : 11 : 4
99 : 7 : 11 : 4
105 : 7 : 11 : 4
110 : 7 : 11 : 4
112 : 7 : 11 : 4
119 : 7 : 11 : 4
lps of 7 occured 14 times.
130 : 11 : 13 : 2
132 : 11 : 13 : 2
154 : 11 : 13 : 2
156 : 11 : 13 : 2
165 : 11 : 13 : 2
lps of 11 occured 5 times.
170 : 13 : 17 : 4
182 : 13 : 17 : 4
187 : 13 : 17 : 4
195 : 13 : 17 : 4
204 : 13 : 17 : 4
208 : 13 : 17 : 4
234 : 13 : 17 : 4
238 : 13 : 17 : 4
247 : 13 : 17 : 4
255 : 13 : 17 : 4
260 : 13 : 17 : 4
272 : 13 : 17 : 4
273 : 13 : 17 : 4
286 : 13 : 17 : 4
lps of 13 occured 14 times.
304 : 17 : 19 : 2
306 : 17 : 19 : 2
340 : 17 : 19 : 2
342 : 17 : 19 : 2
357 : 17 : 19 : 2
lps of 17 occured 5 times.
368 : 19 : 23 : 4
380 : 19 : 23 : 4
391 : 19 : 23 : 4
399 : 19 : 23 : 4
414 : 19 : 23 : 4
418 : 19 : 23 : 4
456 : 19 : 23 : 4
460 : 19 : 23 : 4
475 : 19 : 23 : 4
483 : 19 : 23 : 4
494 : 19 : 23 : 4
506 : 19 : 23 : 4
513 : 19 : 23 : 4
lps of 19 occured 13 times.
551 : 23 : 29 : 6
552 : 23 : 29 : 6
575 : 23 : 29 : 6
580 : 23 : 29 : 6
598 : 23 : 29 : 6
609 : 23 : 29 : 6
621 : 23 : 29 : 6
638 : 23 : 29 : 6
644 : 23 : 29 : 6
690 : 23 : 29 : 6
696 : 23 : 29 : 6
713 : 23 : 29 : 6
725 : 23 : 29 : 6
736 : 23 : 29 : 6
754 : 23 : 29 : 6
759 : 23 : 29 : 6
782 : 23 : 29 : 6
783 : 23 : 29 : 6
805 : 23 : 29 : 6
812 : 23 : 29 : 6
828 : 23 : 29 : 6
lps of 23 occured 21 times.
868 : 29 : 31 : 2
870 : 29 : 31 : 2
928 : 29 : 31 : 2
930 : 29 : 31 : 2
957 : 29 : 31 : 2
lps of 29 occured 5 times.
962 : 31 : 37 : 6
992 : 31 : 37 : 6
999 : 31 : 37 : 6

NOTE: Even going through an empty loop ~a trillion times takes quite a bit of time
 
a little more googling and I have come across this pattern http://mukeshiiitm.wordpress.com/. The guy discusses the pattern in his blog, but I cant make any sense of it.

I tried the trillion count as a test as well and it took a while and I gave up.

im trying other ideas, multiplying the lps*ups and see if there is a pattern etc
 
In the code you've written, what's the most expensive operation? Is there a way to do it less frequently?
 
the most expensive even in my python code it is the lps function. you can reduce it to a certain degree based on the pattern, but still it is a trillion iterations
 
I'm thinking at a lower level.

In the C++ code shown here, sqrt() is the most expensive operation. The repeated conversions from double to int and back are next, and the modulo operators are third.

Hoisting sqrt() out of the loop is the start of an optimization that will cut the number of iterations.
 
Why not instead of doing sqrt (which is very expensive as mikeblas has pointed out), you refactor lps to find the largest prime which when multiplied by itself is smaller than the target number. ups is the smallest prime which when multiplied by itself is larger than the target number.

Keeping an index to "pivot" around into your sieve combined with this optimization should speed it up quite a bit.
 
I was thinking the exact same thing there mikeblas, except implementing the removal differently than you suggested generelz. It may be a better or worse idea, I haven't totally thought it through, just doing it in my head while watching a movie.

I'll try and explain my thinking as best I can:
The first whole sqrt we deal with is sqrt(4) = 2.
The next time we'll have a whole sqrt is sqrt(9) = 3.
After that, the next time is at sqrt(16) = 4.
And then sqrt(25) = 5.

The difference between these numbers is 5,7,9.
We can say we need to check for lps(n) a maximum of every 5 + 2x times.
However, we also know ups(n), and therefore the difference (d) between lps(n) and ups(n).
So now we only need a new lps(n) every 5d + 2d times.
This new lps(n) is also automatically the next prime number in the list, meaning we don't need a loop or searches.

EDIT: (I realize the 5 + 2x and 5d + 2d aren't exactly right)

How to rid ourselves of modulus division though, couldn't tell ya.
 
you should be able to cut down on the modulus division by keeping an intermediate result as the lps and ups numbers will not change as often - so just find the lps and ups once, calculate the modulus result then and then iterate all values by one. then you only have to do an equality check (lpsModulus == lps or upsModulus == ups). When it does you reset it to 0.

this will yield especially better optimization in the case of large numbers because as the numbers grow, you actually end up doing fewer and fewer modulus operations because the gaps between the next lps/ups grow as your sequence shows above.
 
Well, I successfully eliminated the lps() and ups() functions using the sequence I mentioned above (for the most part), so that should reduce the amount of work needed during each iteration.

Next, I'll try and reduce the amount of modulus operations used, and then look into the amount of total iterations.
 
I haven't had a chance to even get the answer with the brute force approach due to power outages EVERY night :).

To answer the question, no progress on my end in terms of actually predicting semi-divisible numbers or anything like that. I brought it to the math head at my school the other day, I'll be checking back with him on Monday.
 
0.25 seconds to sum the big guy... :D

Code: 
euler234# g++ -DMAX=1000 solver.cc && time ./a.out

n<=1000  sum=34825
0.00user 0.00system 0:00.00elapsed ?%CPU

euler234# g++ -DMAX=999966663333 solver.cc && time ./a.out

n<=999966663333  sum=12................1
0.25user 0.00system 0:00.25elapsed 99%CPU

euler234# g++ -v

Target: x86_64-manbo-linux-gnu
gcc version 4.3.2 (GCC)

euler234#
code redacted
 
Last edited:
You must log in or register to reply here.
Back
Top