Modular Cubes in C#

Question

I am have difficulties solving this problem:

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.

Answer 1

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.