본문 바로가기
Programming/Project Euler

508. Project Euler #508 : integers in base i-1

by 작은별하나 2015. 5. 2.

This problem's solvers are under 100.  This is very hard problem, so I can't describe detail solving method in this blog.


This problem is.


Consider the Gaussian integer i-1. A base i-1 representation of a Gaussian integer a+bi is a finite sequence of digits dn-1dn-2...d1d0 such that:

  • a+bi = dn-1(i-1)n-1 + dn-2(i-1)n-2 + ... + d1(i-1) + d0
  • Each dk is in {0,1}
  • There are no leading zeroes, i.e. dn-1 ≠ 0, unless a+bi is itself 0

Here are base i-1 representations of a few Gaussian integers:

11+24i → 111010110001101
24-11i → 110010110011
8+0i → 111000000
-5+0i → 11001101
0+0i → 0

Remarkably, every Gaussian integer has a unique base i-1 representation!

Define f(a+bi) as the number of 1s in the unique base i-1 representation of a+bi. For example, f(11+24i) = 9 and f(24-11i) = 7.

Define B(L) as the sum of f(a+bi) for all integers ab such that |a| ≤ L and |b| ≤ L. For example, B(500) = 10795060.

Find B(1015) mod 1 000 000 007.


Shortly describing, If specified range's complex number convert to base i-1, how many digit 1 are appeard.


Gaussian prime number is the complex number which has integer parameters and cannot be devided by other Gaussian primes. Gaussian primes can be acquired by prime numbers.


i) prime numbers are Gaussian primes.  For example 3, 7, 11, 19, ...

ii) Other prime numbers will be complex number Gaussian primes.  Other primes are can be  for integers a and b.  Gaussian primes from prime number 2 are .  5 are .


I think that in order to solve this problem, above theory is not important.


This problem's order is very big, 10's 15 power.  If solve this problem with brute force method,  i-1 base conversions are needed.  


Conversion function GetGaussianInteger(r, i) can be listed as C++.

uint64_t GetGaussianInteger(int64_t r, int64_t i)
{
    uint64_t count = 0;

    while(r || i)
    {
        if( (r^i)&1 ) { r--; count++; }
        int64_t x = (i-r)/2;
        i = -(i+r)/2;
        r = x;
    }

    return count;
}

In order to is 1, rear part and imagenary part are (odd, even) or (even, odd).  Otherwise  wiill be 0.  If is 1, real part number decrease by one.  Then divide a+bi by i-1.  This function will be run till real part and imagenary part are all zero.


B(10000) can be get with brute force method, but If N is larger, the execution time is square order.  I think that brute force method order is .


My approach is reduce size by mathematical method.  If N is 10000, I reduce N to 5000.  My approach's order is .


To solve this problem, in my case, elapsed time is about 18ms.


Refer to this value.  If you want to know more values, add your comment, I'll reply.



댓글