Finding the square root of a large mersenne number

[Fusion_power]

Maybeso,

Actually, I want the first square LESS than the mersenne number. The method I am trying to prove in is significantly different from Fermat's factorization. The big question to be answered is whether or not it can be made to run in a reasonable time frame.

Wackerbarth,

Thanks for the math. I'm trialing it with small numbers now.

Fusion

[ewmayer]

Originally Posted by Wackerbarth

Since I hit "Submit" only once, I don't know why there are 3 copies posted. Perhaps the forum moderator will delete the extra copies for us.

Done. Sorry, I didn't get around to perusing the forum until rather late in my workday today.

[Uncwilly]

Ok, sorry to dig up a necro-thread, but this seamed the best spot to start with.

There are several of the lower exponents (less than 3000) that have not had a factor found. They have had a considerable amount of TF and ECM done on them. There have been some wild suggestions (not serious, AFAIK) of doing TF top down.

So, my questions:

1. Does Prime95 (or has PrimeNet) done a search to see if the number is a square?
2. Is there any checking to see if it is a cube, 5th or 7th power, etc.?
3. If 'no', has anyone put any effort into doing this or writing the code?
4. Would this be well adapted to a GPU?
5. Would it be vaugely worth the effort? (From the sense of accomplishment or interesting data perspective.)

[CRGreathouse]

Originally Posted by Uncwilly

There are several of the lower exponents (less than 3000) that have not had a factor found. They have had a considerable amount of TF and ECM done on them. There have been some wild suggestions (not serious, AFAIK) of doing TF top down.

So, my questions:

1. Does Prime95 (or has PrimeNet) done a search to see if the number is a square?
2. Is there any checking to see if it is a cube, 5th or 7th power, etc.?

Mihăilescu's theorem says that none will be powers.

[Uncwilly]

Originally Posted by CRGreathouse

Mihăilescu's theorem says that none will be powers.

Ok, thanks. It is good to have that stated somewhere on the boards. Is it on the wiki?

[xilman]

Originally Posted by Uncwilly

Ok, sorry to dig up a necro-thread, but this seamed the best spot to start with.

There are several of the lower exponents (less than 3000) that have not had a factor found. They have had a considerable amount of TF and ECM done on them. There have been some wild suggestions (not serious, AFAIK) of doing TF top down.

So, my questions:

1. Does Prime95 (or has PrimeNet) done a search to see if the number is a square?
2. Is there any checking to see if it is a cube, 5th or 7th power, etc.?
3. If 'no', has anyone put any effort into doing this or writing the code?
4. Would this be well adapted to a GPU?
5. Would it be vaugely worth the effort? (From the sense of accomplishment or interesting data perspective.)

I doubt that the first three questions have an affirmative answer, but I could well be wrong.

For the fourth question, I can't see any reason why a GPU should not prove effective. Each core will be slower than a typical CPU core, but as some GPUs have several hundred cores the overall throughput should be better.

As for the last: the likelihood of finding a factor is somewhere between nil and negligible, but I infer that you already realise that. However, IMO it would make a good project for someone who wishes to teach themselves GPU programming and optimization. Once you have a good grounding in the subject you will be well placed to code something with a greater chance of producing results of interest to others. (Actually, if you are thinking of applying for a job which requires GPGPU skills, the results of the proposed exercise are already of interest to others --- you prospective employers.)


Paul

[CRGreathouse]

Originally Posted by Uncwilly

Ok, thanks. It is good to have that stated somewhere on the boards. Is it on the wiki?

I don't know, but it's simple enough to state: if n > 8, then at most one of {n, n+1} is a power.

[cheesehead]

In particular, for any n > 1, 2ⁿ-1 cannot be a power.