Project Euler - Problem 272 in C#

Question

I am have difficulties solving problem 272 of Project Euler, which has the following statement.

For a positive number n, define C(n) as the number of the integers x, for which 1 < x < n and x^3 = 1 mod n.

When n=91, there are 8 possible values for x, namely : 9, 16, 22, 29, 53, 74, 79, 81. Thus, C(91)=8.

Find the sum of the positive numbers n <= 10^11 for which C(n) = 242.

My Code:

double intCount2 = 91;
double intHolder = 0;

for (int i = 0; i <= intCount2; i++)
{
    if ((Math.Pow(i, 3) - 1) % intCount2 == 0)
    {
        if ((Math.Pow(i, 3) - 1) != 0)
        {
            Console.WriteLine(i);
            intHolder += i;
        }
    }
}
Console.WriteLine("Answer = " + intHolder);
Console.ReadLine();

This works for 91 but when I put in any large number with a lot of 0's, it gives me a lot of answers I know are false. I think this is because it is so close to 0 that it just rounds to 0. Is there any way to see if something is precisely 0? Or is my logic wrong?

I know I need some optimization to get this to provide a timely answer but I am just trying to get it to produce correct answers.

(If you are correcting my document please try to use correct spelling.)

Answer 1

Wikipedia has an article on Modular exponentiation that you may find informative. IIRC, Python has it built in. C# does not, so you'll need to implement it yourself.

Answer 2

Don't compute powers modulo n using Math.Pow; you are likely to experience overflow issues among other possible issues. Instead, you should compute them from first principles. Thus, to compute the cube of an integer i modulo n first reduce i modulo n to some integer j so that i is congruent to j modulo n and 0 <= j < n. Then iteratively multiply by j and reduce modulo n after each multiplication; to compute a cube you would perform this step twice. Of course, that's the native approach but you can make this more efficient by following the classic algorithm for exponentiation by using exponentiation by squaring.

Also, as far as efficiency, I note that you are unnecessarily computing Math.Pow(i, 3) - 1 twice. Thus, at a minimum, replace

if ((Math.Pow(i, 3) - 1) % intCount2 == 0) {
    if ((Math.Pow(i, 3) - 1) != 0) {
        Console.WriteLine(i);
        intHolder += i;
    }
}

with

int cubed = Math.Pow(i, 3) - 1;
if((cubed % intCount2 == 0) && (cubed != 0)) {
    Console.WriteLine(i); 
    intHolder += i;
}

Answer 3

Well, there's something missing or a typo...

"intHolder1" should presumably be "intHolder" and for intCount2=91 to result in 8 the increment line should be:-

intHolder ++;

Answer 4

Let me generalize your questions to two questions:

1) What specifically is wrong with this program?

2) How do I figure out where a problem is in a program?

Others have already answered the first part, but to sum up:

Problem #1: Math.Pow uses double-precision floating point numbers, which are only accurate to about 15 decimal places. They are unsuitable for doing problems that require perfect accuracy involving large integers. If you try to compute, say, 1000000000000000000 - 1, in doubles, you'll get 1000000000000000000, which is an accurate answer to 15 decimal places; that's all we guarantee. If you need a perfectly accurate answer for working on large numbers, use longs for results less than about 10 billion billion, or the large integer mathematics class in System.Numerics that will ship with the next version of the framework.

Problem #2: There are far more efficient ways to compute modular exponents that do not involve generating huge numbers; use them.

However, what we've got here is a "give a man a fish" situation. What would be better is to teach you how to fish; learn how to debug a program using the debugger.

If I had to debug this program the first thing I would do is rewrite it so that every step along the way was stored in a local variable:

double intCount2 = 91; 
double intHolder = 0; 

for (int i = 0; i <= intCount2; i++) 
{ 
    double cube = Math.Pow(i, 3) - 1;
    double remainder = cube % intCount2;
    if (remainder == 0) 
    { 
        if (cube != 0) 
        { 
            Console.WriteLine(i); 
            intHolder += i; 
        } 
    } 
} 

Now step through it in the debugger with an example where you know the answer is wrong, and look for places where your assumptions are violated. If you do so, you'll quickly discover that 1000000 cubed minus 1 is not 99999999999999999, but rather 1000000000000000000.

So that's advice #1: write the code so that it is easy to step through in the debugger, and examine every step looking for the one that seems wrong.

Advice #2: Pay attention to quiet nagging doubts. When something looks dodgy or there's a bit you don't understand, investigate it until you do understand it.

Answer 5

I don't have a solution to your problem, but here's just a piece of advice :

• Don't use floating point numbers for calculations that only involve integers... Type int (Int32) is clearly not big enough for your needs, but long (Int64) should be enough : the biggest number you will have to manipulate will be (10 ^ 11 - 1) ^ 3, which is less than 10 ^ 14, which is definitely less than Int64.MaxValue. Benefits :

  • you do all your calculations with 64-bit integers, which should be pretty efficient on a 64-bit processor
  • all the results of your calculations are exact, since there are no approximations due the internal representation of doubles

• Don't use Math.Pow to calculate the cube of an integer... x*x*x is just as simple, and more efficient since it doesn't need a conversion to/from double. Anyway, I'm not very good at math, but you probably don't need to calculate x^3... check the links about modular exponentiation in other answers