Why is isHodder() not working. What am I Missing?

CollinsLainzo (24)
I have this problem,
A hodder number is one that is prime and is equal to 2j-1 for some j. For example, 31
is a hodder number because 31 is prime and is equal to 25-1 (in this case j = 5). The first 4
hodder numbers are 3, 7, 31, 127
Write a function with signature int isHodder(int n) that returns 1 if n is a hodder
number, otherwise it returns 0.
Recall that a prime number is a whole number greater than 1 that has only two whole
number factors, itself and 1.

And I coded a solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
#include <iostream>
using namespace std;
int isPrime(int a);
int isHodder(int n);
int main()
{
	int num;
	cout<<"Enter number: ";
	cin>>num;
	cout<<isHodder(num);
	return 0;
}
int isPrime(int a)
{	
	if (a==2)
		return 1;
	for(int i=1; i<a; i++)
	{
		if(a%i==0)
			return 0;
	}
	return 1;
}
int isHodder(int n)
{
	int k;
	for(int i=2;i<n && k<n; i++)
	{
		k=(2^i)-1;
	}
		if(k==n && isPrime(n))
		{
			return 1;
		}
	return 0;
}



However, this solution is not working, what am I doing wrong?
dutch (2548)
what am I doing wrong?

Pretty much everything.

Your isPrime is not right. You should test it separately. You definitely don't want to test for divisibility by 1!!! And you only want to test up to and including the sqrt of a.

As for the isHodder function, ^ is not an exponentiation operator in C++. It's the bitwise exclusive-or operator. To calculate a power of 2, you can use the left bitshift operator <<, like (1 << i), which means 1 shifted left i times. Also, your braces seem to be misplaced, too.

Last edited on
doug4 (1538)
Also, k has no value the first time through line 27, so the check k<n is meaningless.
lastchance (6980)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
#include <iostream>
#include <valarray>
#include <cmath>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;

int main()
{
   const int N = 1000000;
   vector<int> PRIMES, TRIALS, HODDER;

   // Sieve of Eratosthenes to get primes
   valarray<bool> A( true, 1+N );
   for ( int i = 2; i < sqrt( N + 0.5 ); i++ ) if ( A[i] ) A[ slice( i+i, N/i-1, i ) ] = false;
   for ( int i = 2; i <= N; i++ ) if ( A[i] ) PRIMES.push_back( i );

   // Collection of (one less than) powers of 2
   for ( int i = 0; i < 31; i++ ) TRIALS.push_back( ( 1 << i ) - 1 );

   // Intersect to get Hodder numbers
   set_intersection( PRIMES.begin(), PRIMES.end(), TRIALS.begin(), TRIALS.end(), back_inserter( HODDER ) );

   for ( int i : HODDER ) cout << i << ' ';
}


3 7 31 127 8191 131071 524287

dutch (2548)
May as well just be a hardcoded table, then.
All 32 bit hodder numbers: 3, 7, 31, 127, 8191, 131071, 524287, 2147483647
Extending to 64 bits only adds one more: 2305843009213693951

Nifty way to check if n is a power of 2:

1
2
3
4
 
bool isPow2(unsigned long n)
{
    return n != 0 && (n & (n - 1)) == 0;
}

lastchance (6980)
How did you manage to get to 64 bits?

Oh rats! It times out in cpp.sh.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
#include <iostream>
#include <cmath>
using namespace std;

bool isPrime( unsigned long long n )
{
        if ( n     <  2 ) return false;
   else if ( n     == 2 ) return true;
   else if ( n % 2 == 0 ) return false;

   unsigned long long maxTest = sqrt( n + 0.5 );
   for ( unsigned long long test = 3; test <= maxTest; test += 2 ) if ( n % test == 0 ) return false;
   return true;
}

int main()
{
   for ( int i = 0; i < 64; i++ )
   {
      unsigned long long trial = ( 1ULL << i ) - 1;
      if ( isPrime( trial ) ) cout << trial << ' ';
   }
}


3 7 31 127 8191 131071 524287 2147483647 2305843009213693951



Seems a bit unfair to write a function to check arbitrary numbers one by one!
Last edited on
dutch (2548)
That's exactly how I did it. Takes a little while to finish, though. Interesting how the 32 extra values past 32-bits only yield one more prime. I would've expected a few.
CollinsLainzo (24)
Great work guys and I am so grateful to you all for your guide. I was able to review my earlier submission after looking into the numerous errors in my code. I then came up with a solution that works!. This problem expected a solution implemented using basic c++ structures that is without the use of vectors, etc...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
#include <iostream>
#include <cmath>
using namespace std;

int isPrime(int a);
int isHodder(int n);
int main()
{
	int num;
	cout<<"Enter number: ";
	cin>>num;
	cout<<isHodder(num);
	return 0;
}
int powerOfTwo(int base, int exp)
{
	if(exp==0)
		return 1;
	if(exp==1)
		return 2;
		return 2*powerOfTwo(2,exp-1);
}
int isPrime(int a)
{	
	if (a==2)
		return 1;
	for(int i=2; i<=sqrt(a); i++)
	{
		if(a%i==0)
			return 0;
	}
	return 1;
}
int isHodder(int n)
{
	int k=0;
	for(int i=2;i<n && k<n; i++)
	{
		k=powerOfTwo(2, i)-1;
	}
		if(k==n && isPrime(n))
		{
			return 1;
		}
	return 0;
}
lastchance (6980)
I think the rest of the world knows these as Mersenne primes. I don't know who christened them Hodder numbers. (Mr Hodder?)

https://en.wikipedia.org/wiki/Mersenne_prime
https://oeis.org/A000668
As of December 2018, 51 are now known. The largest known prime number 282,589,933 − 1 is a Mersenne prime.

@Dutch, we've got a long way to go!


If n is a composite number then so is 2n − 1. (2ab − 1 is divisible by both 2a − 1 and 2b − 1.) This definition is therefore equivalent to a definition as a prime number of the form Mp = 2p − 1 for some prime p.

Hmmm, that would have saved some searching.

doug4 (1538)
@OP,

Your indentation leaves a lot to be desired.

Line 21 should align with line 19. A quick reading makes it looks like it is a second return statement inside line 19's if block. I initially thought this was unreachable code until I realized only line 20 was in the if block.

Lines 41 - 44 should be outdented one level. A quick reading makes it look like this block of code is supposed to be executed within the for statement, and that the closing brace in line 40 is erroneous.

Also, do you really need to use a recursive function to calculate powerOfTwo? @dutch showed you how to do it with a single statement.
CollinsLainzo (24)
@doug,

Thanks for the feedback, I have take note of this and will effect in my program file.

Best regards.
CollinsLainzo (24)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
#include <iostream>
using namespace std;
int isMartian(int a[], int len);
int main()
{
	int numarr[50];
	int n;
	cout<<"Enter Array size:";
	cin>>n;
	cout<<"Enter array elements: ";
	for(int i=0; i<n; i++)
	{
		cin>>numarr[i];
	}
	cout<<isMartian(numarr,n);
}
int isMartian(int a[], int len)
{   
    int ones = 0, twos = 0;
    for (int i = 0; i < len; i++)
    {
        if (a[i] == a[i + 1]) 
			return 0;
    	if(a[i] == 1) 
			ones++;
            	else if (a[i] == 2) 
					twos++;
    }	
    if (ones <= twos) 
		return 0;
            return 1;
}
doug4 (1538)
I'm not sure if you have a question here. So, I'll just comment on the code you threw up here.

You never check to make sure that the n entered in line 9 is <= 50. For toy programs where you are in control of the input, this is not a problem, but when working in the real world you need to make lots of defensive checks against this.

When i == len - 1, line 22 will access memory out of range of populated array elements. This is an error.

Lines 29 - 30 can be reduced to return (ones > twos);. It would make even more sense if you changed the return type of isMartion to bool.

Typically, else statements are aligned with their associated if statements. You should outdent lines 26 and 27.
Topic archived. No new replies allowed.