mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2010-03-06, 08:26   #34
10metreh
 
10metreh's Avatar
 
Nov 2008

2·33·43 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
I wasn't implying it was, I was simply asking if it was and if so we know it's factors are the possible factors of 2^(y)-1 hence we only would have to check until sqrt(2^(y)-1) into the factors of 2^(2*y)-1 ( which since there are likely many factors below that point ( or I think)) it would explain why there are infinitely many exceptions to 2^p-1 (where p = prime) is prime.
Any number of the form 22y-1 can be algebraically factored into 2y+1 and 2y-1, as Paul said. This means that, if we were to do trial division, then we would only have to check up to the square root of 2y+1 instead of the square root of the whole number. But this is totally trivial: did you ever learn "the difference of two squares is the sum of the bases times the difference of the bases"? This is what gives the algebraic factorisation.

And there are far better ways of factoring large numbers than trial division. Try factoring 2193-1 with trial division. Here it is:
Code:
12554203470773361527671578846415332832204710888928069025791
It can be done in under 5 seconds even on an ancient computer. But not with trial division.

Last fiddled with by 10metreh on 2010-03-06 at 08:28
10metreh is offline   Reply With Quote
Old 2010-03-06, 12:09   #35
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

I've never learned half of whats on here I barely have grade 12 math and I live 60 km from the nearest major community unless you count sidney crosby's birth community
science_man_88 is offline   Reply With Quote
Old 2010-03-06, 12:36   #36
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

37×281 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
I've never learned half of whats on here I barely have grade 12 math and I live 60 km from the nearest major community unless you count sidney crosby's birth community
With respect, you have only yourself to blame.

There are any number of on-line resources which you can use, directly or indirectly, to educate yourself. In that, you are more fortunate than the great majority of the present world population. You are also more fortunate than almost everyone who has ever lived.

(For an example of an indirect use of on-line resources, consider your ability to purchase traditional books, printed on paper, from sites such as Amazon.)

Paul
xilman is online now   Reply With Quote
Old 2010-03-06, 13:07   #37
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

xilman as I don't have a credit card or money most days ( Plus no job) I don't think amazon will help
science_man_88 is offline   Reply With Quote
Old 2010-03-06, 13:08   #38
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

plus the best book I've found on numbers is number freak and I got it within a year of now and it at most goes to 200
science_man_88 is offline   Reply With Quote
Old 2010-03-07, 00:04   #39
flouran
 
flouran's Avatar
 
Dec 2008

72×17 Posts
Thumbs up

Quote:
Originally Posted by Mini-Geek View Post
As long as it's kept to the Misc Math forum, I'm fine with it. Sometimes I even find these threads amusing (in a way).
Yes, many Friday nights I tend to warm up a cup of milk and just read the Misc. Math. posts until around 1 a.m. So I agree with you, they are rather interesting!
flouran is offline   Reply With Quote
Old 2010-03-07, 00:11   #40
flouran
 
flouran's Avatar
 
Dec 2008

11010000012 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
xilman as I don't have a credit card or money most days ( Plus no job) I don't think amazon will help
You don't necessarily need a book to read and understand higher level math. In fact, perseverance and patience are key.

Google is free (I know, a pretty crazy concept). I suggest you educate yourself with that first rather than wasting your time on the internet posting questions that can easily be answered with a certain level of research and determination.

To be successful, you need to not only accept failure (and learn from it), but also you should actually enjoy NOT being able to solve a problem (and spend hours thinking about it) because you would be able to appreciate the endeavor.
flouran is offline   Reply With Quote
Old 2010-03-07, 00:53   #41
Orgasmic Troll
Cranksta Rap Ayatollah
 
Orgasmic Troll's Avatar
 
Jul 2003

641 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
I've never learned half of whats on here I barely have grade 12 math
grade 12? That's generous.
Orgasmic Troll is offline   Reply With Quote
Old 2010-03-07, 16:38   #42
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

and i wondered before why they called you a troll
science_man_88 is offline   Reply With Quote
Old 2010-03-07, 19:02   #43
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

37·281 Posts
Default

Quote:
Originally Posted by flouran View Post
You don't necessarily need a book to read and understand higher level math. In fact, perseverance and patience are key.

Google is free (I know, a pretty crazy concept). I suggest you educate yourself with that first rather than wasting your time on the internet posting questions that can easily be answered with a certain level of research and determination.

To be successful, you need to not only accept failure (and learn from it), but also you should actually enjoy NOT being able to solve a problem (and spend hours thinking about it) because you would be able to appreciate the endeavor.
Good advice. A number of people here should learn from it. Including myself on occasion.

Paul
xilman is online now   Reply With Quote
Old 2010-03-07, 19:39   #44
alexhiggins732
 
Mar 2010
Brick, NJ

6710 Posts
Default

Science man, I see where you are going but as pointed it may not be useful.

Let's step through your example.

1) If y is even, then 3 | 2^y-1
2) Let d = sqrt(2^y), then d-1 * d+1 | 2^y-1.

Example, 2^22-1 = 4194303
1) 4194303 = 3 * 1398101
2) sqrt(4194304)= 2048, so 1398101= 2047*2049

So either 3|2047 or 3|2049, in this case. We can discover which one by testing if 4194303 | 3*2047 or 4194303 | 3*2049.

We see that 4194303 | 3*2047 = 683, which means 2049=3*683

So our factorization of 4194303 now becomes 3 x 683 x 2047

This still leaves the problem of factoring 2047.
alexhiggins732 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Modifying the Lucas Lehmer Primality Test into a fast test of nothing Trilo Miscellaneous Math 25 2018-03-11 23:20
A second proof for the Lucas-Lehmer Test carpetpool Miscellaneous Math 2 2017-07-30 09:21
proof the lucas lehmer test kurtulmehtap Math 13 2009-10-02 12:12
Lucas-Lehmer Test storm5510 Math 22 2009-09-24 22:32
Lucas-Lehmer Test proof alpertron mersennewiki 16 2006-03-18 07:23

All times are UTC. The time now is 12:01.

Sat Dec 5 12:01:41 UTC 2020 up 2 days, 8:13, 0 users, load averages: 1.39, 1.81, 1.95

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.