Why does this code work that way?

[gameprogrammer]

I want to find a code that would search for a natural number n>1 such that satisfies

n | 2^{n-1} + 3

or i.e. 2^{n-1}+3 is divisible by n. So I've written this code that brings me an answer 2, which is clearly wrong. What's wrong with my code? Thanks.

And I guess I should've put this question in the 'beginners' subforum. This code seems extremely simple yet for some reason I can't find the error.

#include <iostream>

using namespace std;

int main()
{
    long int i;
    for (i=2;i<10^11;i++)
        if ((2^(i-1)+3)%i==0) {
            cout << i;
            return 0; }
}

[keskiverto]

Please use code tags when posting code.
http://www.cplusplus.com/articles/jEywvCM9/

The first error is that operator^ is bitwise exclusive OR (XOR).
That is quite different from http://www.cplusplus.com/reference/cmath/pow/

[gameprogrammer]

I've edited the post.

I don't quite understand your second paragraph, though. I'm a beginner and the

bitwise exclusive OR (XOR)

part of your answer is unclear to me, so some further explanation would be appreciated. Thanks.

[wildblue]

i<10^11

Do you mean this to be 10 to the 11th power? The ^ in C++ does not mean power like it does in some math programs.


Edit: There's a pow function in C++ in <cmath>. (Link in post above)

[AbstractionAnon]

I don't quite understand your second paragraph

C and C++ do not have an exponentiation operator. You must use the pow() function as keskiverto explained.

In C/C++, ^ is the exclusive or (XOR) operator.
http://www.cplusplus.com/doc/boolean/
10 = 01010
11 = 01011
result= 00001

[gameprogrammer]

So how would you actually go about changing this line

if ((2^(i-1)+3)%i==0) {

of the code?

I can see that the 'pow' function takes 'double' values. So I guess I would have to rename the type of my variable 'i' to 'double'. I've also changed '2' to '2.0'.

However, the operator % seems to find a problem there now; the compiler shows me the following error:

error: invalid operands of types 'double' and 'double' to binary 'operator%'

[Smac89]

Cast the value returned by pow to int:

if ((int)(3 + pow(2, i - 1)) % i == 0) { ... }


To avoid having to use the pow function, you can take advantage of the fact that 2^n-1 is a power of 2, then you can use bit shifts to do the powers:

#include <iostream>

using namespace std;

int main()
{
    long int i;
    long max = 1 << 37; // close to 1e11
    for (i = 2; i < max; i++)
        if ( ((1 << (i - 1)) + 3) % i == 0) {
            cout << i << ' ';
            return 0;
        }
    return 1;
}

[gameprogrammer]

Here's my new code and the output I get by running the program:

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    double i;
    for (i=2;i<(int)(pow(10,20));i++)
        if ((int)(pow(2, i - 1) + 3) % (int)i == 0) {
            cout << i;
            return 0; }
}

But there's solution in the range of 1 < i < 10^20 + 1 as far as I know.

[keskiverto]

1. pow() has overloads, but they all are floating point variations. You can call pow() with integer types; there will be implicit conversion to some floating type. If there are ambiguous cases -- equally "easy" conversion will match two different overloads, then explicit types (or conversions) are needed to resolve the overload. This is least of the problems.

2. Floating point types are strange and weird. Do not expect to do mathematics with them. They don't have enough precision for that. Most definitely you don't want your loop counter i to be a floating point type. Ever.

3. Yes, you could force conversion from float type into integer type with a cast. However, the syntax (unsigned long long)foo is a C-style cast. You should prefer the C++-syntax, so here static_cast<unsigned long long>(foo). However,

4. There is a bitshift left operator for (unsigned) integers. Moving bits left by X steps is equivalent to multiplying the number by 2^X. Therefore, you could write (3 + (1 << (i-1)) ) % i. All integer operation. However,

5. 1 << 99999999998 requires 99999999999 bits. The C++ standard guarantees that unsigned long long can hold at least 64 bits. I find it highly unlikely that any compiler and platform would reserve 99999999999 for single integer, when standard demands only 64 and special hardware, like Xeon Phi, has mere 512 bit registers.

That is one big problem. You do need custom "big ints". Some websearch hits:
https://mattmccutchen.net/bigint/
http://stackoverflow.com/questions/269268/how-to-implement-big-int-in-c


Note: you can write an integer version of pow(). It's just a *= in a for loop that iterates exponent times.

[Cubbi]

1. pow() has overloads, but they all are floating point variations.

C++11 added overloads for all integer types

[keskiverto]

You do refer to the template version, which is a wrapper that casts parameters to double or long double.
http://en.cppreference.com/w/cpp/numeric/math/pow
(Unless the documentation is incomplete.)

[Cubbi]

yes, the required integer overloads may be packaged as function templates. (cppref does say "A set of overloads or a function template")