# massive non-Mersenne prime

Sam Benry

Ranch Hand

Posts: 89

posted 8 years ago

I want to solve this problem

I tried using BigInteger to compute the prime it self, I think it would take years to compute it, so I need another way around it. Can anyone suggest any method?

thanks

The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form 2^6972593−1; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2^p−1, have been found which contain more digits.

However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 28433�2^7830457+1.

Find the last ten digits of this prime number.

I tried using BigInteger to compute the prime it self, I think it would take years to compute it, so I need another way around it. Can anyone suggest any method?

thanks

posted 8 years ago

hmmm... couldn't you just calculate the bottom 10 digits? What i mean is you don't care about most of them so just ignore them. If i only wanted the last 2 digits of 2^10 + 1, i could do this:

then add the one, giving me 25.

[ May 15, 2008: Message edited by: fred rosenberger ]

then add the one, giving me 25.

[ May 15, 2008: Message edited by: fred rosenberger ]

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

Sam Benry

Ranch Hand

Posts: 89

Campbell Ritchie

Marshal

Posts: 52507

118

posted 8 years ago
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

i was not calculating the value. every time it rolled over 100 (in my case), i dropped whatever was in the hundreds place. i'm only ever dealing with 2 digits.

Heck, I think i could even get clever and when the 10's digit is greater than 4, i can pretty much ignore it and just double the 1's digit... i THINK.

this may not give me a performance boost (i think it would actually slow things down), but it is interesting...

[edit]nevermind... that's not correct.[/edit]

in your case, you'd have to account for the 10 digits, but that's going to process much faster than the hundreds or thousands of digits.

[ May 15, 2008: Message edited by: fred rosenberger ]

Heck, I think i could even get clever and when the 10's digit is greater than 4, i can pretty much ignore it and just double the 1's digit... i THINK.

this may not give me a performance boost (i think it would actually slow things down), but it is interesting...

[edit]nevermind... that's not correct.[/edit]

in your case, you'd have to account for the 10 digits, but that's going to process much faster than the hundreds or thousands of digits.

[ May 15, 2008: Message edited by: fred rosenberger ]

Sam Benry

Ranch Hand

Posts: 89

posted 8 years ago
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

could you give us a hint? does it compile? does it die when you run it? does it not give you the answer you are expecting? WHY do you think it's not right?

help us help you.

ok... i played with it a little. i made your for loop only go 5 times. and, i did this:

see if you can figure out the problem from here...

[ May 15, 2008: Message edited by: fred rosenberger ]

help us help you.

ok... i played with it a little. i made your for loop only go 5 times. and, i did this:

see if you can figure out the problem from here...

[ May 15, 2008: Message edited by: fred rosenberger ]

Sam Benry

Ranch Hand

Posts: 89

posted 8 years ago
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

My guess is that it will just take a LONG time. You have a logic error in there, that is ending up doing some MASSIVE computations.

another note... you really don't even need BigInteger for this. I think i have a solution that is 22 lines, uses only longs and ints. My answer is

8739992577

and my program runs in under a second.

[ May 15, 2008: Message edited by: fred rosenberger ]

another note... you really don't even need BigInteger for this. I think i have a solution that is 22 lines, uses only longs and ints. My answer is

8739992577

and my program runs in under a second.

[ May 15, 2008: Message edited by: fred rosenberger ]

Sam Benry

Ranch Hand

Posts: 89

posted 8 years ago

@fred rosenberger

please could you explain where I have logical errors? I can't figure out how to improve my program

I change BigInteger to Long (should it be double instead?)

please could you explain where I have logical errors? I can't figure out how to improve my program

I change BigInteger to Long (should it be double instead?)

posted 8 years ago
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

I changed your code to loop 5 times, and print out n each time. i get this:

java -cp . Problem97

n is 2

n.pow is 1

n is 4

n.pow is 2

n is 16

n.pow is 3

n is 256

n.pow is 4

n is 65536

n.pow is 5

n is 4294967296

n.pow is 6

n is 13709551614

n.pow is 7

n is 13709551614

n.pow is 8

9223372036854775807

What you are doing here each time is raising N to the power of 2. So, first you take 2, and raise it to the power of 2, giving 4.

you then take 4, and raise IT to the power of 2, giving you 16. you then raise 16 to the power of 2, giving 256, etc.

you don't want to raise it by the power of 2 each iteration through the loop... you want to MULTIPLY it by 2 each time through the loop.

Also, there is a much simpler way to chop of extra digits, using a basic operator. do you know what 'modulus' means? It basically means "give me the remainder after i divide". so, '23 mod 5' would be 3. '15 mod 7' would be 1.

so, '217 mod 100' is 17. there is an operator that will do this for you.

[ May 16, 2008: Message edited by: fred rosenberger ]

java -cp . Problem97

n is 2

n.pow is 1

n is 4

n.pow is 2

n is 16

n.pow is 3

n is 256

n.pow is 4

n is 65536

n.pow is 5

n is 4294967296

n.pow is 6

n is 13709551614

n.pow is 7

n is 13709551614

n.pow is 8

9223372036854775807

What you are doing here each time is raising N to the power of 2. So, first you take 2, and raise it to the power of 2, giving 4.

you then take 4, and raise IT to the power of 2, giving you 16. you then raise 16 to the power of 2, giving 256, etc.

you don't want to raise it by the power of 2 each iteration through the loop... you want to MULTIPLY it by 2 each time through the loop.

Also, there is a much simpler way to chop of extra digits, using a basic operator. do you know what 'modulus' means? It basically means "give me the remainder after i divide". so, '23 mod 5' would be 3. '15 mod 7' would be 1.

so, '217 mod 100' is 17. there is an operator that will do this for you.

[ May 16, 2008: Message edited by: fred rosenberger ]