Project Euler 78: Counting Partitions

Project Euler problem 78:


Let \$p(n)\$ represent the number of different ways in which \$n\$ coins can be separated into piles. For example, five coins can be separated into piles in exactly seven different ways, so \$p(5)=7\$.


Find the least value of \$n\$ for which \$p(n)\$ is divisible by one million.

I used Euler's recurrence relation for the partition of \$n\$, together with the fact that modular addition is distributive: $$(a + b) \bmod n = ((a \bmod n) + (b \bmod n)) \bmod n.$$

#include 
#include 
using namespace std;

int main()
{
  // generalized pentagonal numbers
  vector g = vector({1, 2}); // g_1 = 1, g_-1 = 2 
  // integer partitions
  vector p = vector({1}); // p_0 = 1
  for (int n = 1; n ; n++) {
    if (g.back() ::iterator g_k = g.begin(); *g_k <= n; ++g_k) {
      if ((g_k - g.begin())/2 % 2 == 0) {
        p_n += p[n - *g_k];
      } else {
        p_n -= p[n - *g_k];
      }
    }
    p.push_back(p_n % 1000000); 
    if (p.back() < 0) p.back() += 1000000;
    if (p.back() == 0) {
      cout << n << endl;
      break;
    }
  }
  return 0;
}

My i7 handles this in ~25ms, but my circa 2008 32-bit centrino needs 600ms. Is there any way that I can squeeze more performance out of the above code? Also, with the exception of removing using namespace std;, is there anything I can do to make the code cleaner/more readable/more presentable?

I'll just comment on the cleanliness/readability aspect:

-
In spite of the given comments, you should give g and p better names. It'll also allow you to remove those comments, which is good because they shouldn't need to be used as such.

-
This kind of initialization isn't really necessary:

vector g = vector({1, 2});

It could just be this:

vector g = { 1, 2 };

If you're using C++11, you can also omit the =.

-
This loop statement may be a little hard to read:

for (int n = 1; n ; n++)

It's understood that having n alone means the loop will continue as long as it's nonzero, but you can still make that clear here anyway. It's otherwise hard to read this statement at a glance.

-
This calculation is unclear as written:

g.push_back(k*(3*k - 1)/2);

You also reuse it, so consider making it a constant in terms of k.

-
Try to add more blank lines between code sections, such as the loops. Having everything together like this can make it harder for the brain to parse out different sections easily.

-
The number 1000000 here is a "magic number" (ambiguous hard-coded number). As such, it should be assigned to a constant with a relevant name. This will also allow you to change this number in just one place.

StackExchange Code Review Q#85837, answer score: 5