factorization of 2^n - 1

[mdreus]

Hello, how to find the factorization of 2^n - 1? I want to find it in the format n x p x q, where n is a smaller number and the others are large and almost identical. For example the number 2^38 - 1 = 3 x 524287 × 174763. The largest number n I found was n = 122. I did it in Python but it is taking a long time to provide the values. I want larger numbers like n > 330 bits. How can I resolve this?

 

[KlausST]

Hi,

I guess there is no simple mathematical solution.
Just do a search on standard prime factor algorithms.

you are looking for (2^n)-1 prime factorisations
... not 2^(n-1)? just to be sure...

* n should be limited. for n = 64 the result exceeds a 64 bit integer variable range. I´m not sure whether there is a bigger standard variable.
* the prime factors search needs to be done up to 2^(n/2) only, if I´m not mistaken.

If this is an iterative pocess .. to speed up ... I´d first find all the prime number up to the expected range, and put them into an array.
Then run the (2^n)-1 search only on the array members.

Klaus

 

[albbg]

You could be interested in this article:

GIMPS - The Math - PrimeNet

A look at the math behind trial factoring, Lucas-Lehmer tests, P-1 factoring, and why each number is double-checked. Also links for further reading.

www.mersenne.org

 

[D.A.(Tony)Stewart]

paste Factor [2^38 - 1] on Wolfram Alpha yields 3 x 524287 × 174763 instantly !

for n=100 to 200; Factor[2^n - 1];next n - Wolfram|Alpha

Wolfram|Alpha brings expert-level knowledge and capabilities to the broadest possible range of people—spanning all professions and education levels.

www.wolframalpha.com

Is there any reason this larger N should exist with 3 prime divisors?

They seem to have a larger qty. of prime factors and none have the 2 largest digits nearly the same.

e.g. Factor [2^343 - 1]
127×6073159×1428389887×62228099977×4432676798593×58961804474844164724814095915114338093146118248375213688557057
(6 distinct prime factors)