mersenneforum.org theory on Mersenne primes ?
 Register FAQ Search Today's Posts Mark Forums Read

2011-09-04, 13:51   #265
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by science_man_88 Another line I've thought about is the fact that when I return D: Code: [P + 1, P^2 + 2*P - 1, P^4 + 4*P^3 + 2*P^2 - 4*P - 1, P^8 + 8*P^7 + 20*P^6 + 8*P^5 - 30*P^4 - 24*P^3 + 12*P^2 + 8*P - 1, All the highlighted endings are off by 2^x from the one that we check with it. Where x is the index into the sequence starting at x=0. P+1 is 1 over P, (2*p+1)-(2*p-1) =2, (4*p+3)-(4*p-1) = 4 and (8*P+7)-(8*P-1) = 8, so these can be turned into 1 term together.
I actually see an extension of this second line of thought:

Quote:
 P^8 + 8*P^7 + 20*P^6 + 8*P^5 - 30*P^4 - 24*P^3 + 12*P^2 + 8*P - 1
8*p-1 = 8 off ( under in this case); (24*P^3 + 12*P^2)/P^2 = 24*P+12 24/8=3 and 3*7 =21-12 =9 so it's -9*P^2 off ; repeat with other:

(8*P^5-30*P^4)/P^4 = 8*P-30 which is below by 37 so -37*(P^4);
and the last group of 2 terms gives: 13*P^6;

turning it into P^8+13*P^6-37*P^4-9*P^2-8 nearly halving the terms needed to be figured out.

2011-09-04, 14:09   #266
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by science_man_88 I actually see an extension of this second line of thought: 8*p-1 = 8 off ( under in this case); (24*P^3 + 12*P^2)/P^2 = 24*P+12 24/8=3 and 3*7 =21-12 =9 so it's -9*P^2 off ; repeat with other: (8*P^5-30*P^4)/P^4 = 8*P-30 which is below by 37 so -37*(P^4); and the last group of 2 terms gives: 13*P^6; turning it into P^8+13*P^6-37*P^4-9*P^2-8 nearly halving the terms needed to be figured out.
I must have messed up somewhere when I plug it into pari I got that the answer mod 31 was 5^2.

 2011-09-10, 14:04 #267 science_man_88     "Forget I exist" Jul 2009 Dumbassville 20C016 Posts Code: (11:00)>((A)^2-2)^2-2 %78 = A^4 - 4*A^2 + 2 (11:00)>((p+2)^2-2) %79 = p^2 + 4*p + 2 I thought about this last night it kinda interest me, just because the absolute ( without sign) values of the coefficients are the same if you let A=P+1, we can say for P=3 = 2^p-1 and p=2 that if the previous one is x mod (p+2) the next one is x mod (P+1) now I know we'd have to factor in that they go up by different amounts. (p=p+1 and P=2*P+1). if only I could make more sense of how to figure out some of these. Last fiddled with by science_man_88 on 2011-09-10 at 14:26 Reason: (p=p+2 and P=4*P+3) would have to jump by 2 making it pointless to help ?
2011-10-31, 19:50   #268
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 p=Mod 24 2*k*p+1= mod 24 k= mod 12 1 1 0 7 3 17 8 23 11 19 1 0 7 9 17 8 23 5 13 1 0 7 3 17 8 23 11 7 1 0 7 9 17 8 23 5 17 1 0 7 3 17 4 23 7 11 1 0 7 9 17 4 23 1 5 1 0 7 3 17 4 23 7 23 1 0 7 9 17 4 23 1
using this is my next idea the reason I kinda see this as useful ( though further thought makes it sound less useful to me) is because, 0 and 2 mod 3 = 8 values mod 12 I only need 4, but they depend on a check of mod 24 for p. I came to the second column from the fact that 1 or 5 mod 6 and 1 or 7 mod 8 give them. the first column came about from looking for primes that 1,3,5,7 mod 8 and once I found examples I knew I couldn't exclude them, taking them with 1 or 5 mod 6 gave the values mod 24. the third column is k mod 12 mostly because the conditions I saw to get the mod 8 and mod 6 remainders were all mod 3 or mod 4 giving rise to the mod 12 values.

2011-11-17, 00:39   #269
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

sigma(2^p)-sigma(2^p-1)==2^p-1

I get that these are Mersenne exponents from talk in the OEIS:

Quote:
 Originally Posted by http://oeis.org/A000668 Mersenne primes are solutions to sigma(n+1)-sigma(n)=n as perfect numbers (A000396(n)) are solutions to sigma(n)=2n - Benoit Cloitre (benoit7848c(AT)orange.fr), Feb 07 2002 Appears to give all n such that sigma(n+1)-sigma(n)=n - Benoit Cloitre (benoit7848c(AT)orange.fr), Aug 27 2002 If n is in the sequence then sigma(sigma(n))=2n+1. Is it true that this sequence gives all numbers n such that sigma(sigma(n))=2n+1? - Farideh Firoozbakht (mymontain(AT)yahoo.com), Aug 19 2005
I'm just wondering if there's a speedup. using this as a test I made a pari code to find the Mersenne prime exponents it took ~430 milliseconds with a forprime loop to find all exponents under 130. mind you I'm more thinking a check of p for some property or such.

Last fiddled with by science_man_88 on 2011-11-17 at 00:47 Reason: changed out n for p in the top equation.

2011-11-17, 03:05   #270
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

268D16 Posts

The sigma function is factoring the number first. There is no other way to compute it. It would take a longer amount of time to compute sigma(x) than it would take to factor x, especially if x has a lot of factors. Computing sigma means factoring x, then combining all its prime factors to make its divisors list, then add them up. There is no speedup. Try it for higher prime exponent and you could see. Try it for 1061. To find sigma(2^1061-1), pari has to factor it first. Try it for sigma(2^1060-1), for which you know all the factors, they are on factorDB, but they are 26 in number, so to make "divisors list" of them you have to combine the factors in 2^26 ways (less, because 5 is doubled), which is in itself very time-consumming.

Computing sigma is semantically equivalent with "factorint(x)" then do "divisors(x)" then sum them.

Try in pari "divisors(2^5*3^5*7^5*11^5*13^5)", you have the smallest primes and you have all the factors known immediately, and about the same amount of factors as above, but to make divisors you will be aging before finishing.

Then you have to sum them up to get sigma.

edit:
Quote:
 Originally Posted by science_man_88 using this as a test I made a pari code to find the Mersenne prime exponents it took ~430 milliseconds with a forprime loop to find all exponents under 130
try 227 or 251, etc (something more difficult to get its sigma, below 300). Unless you did something totally different from the next oneliner (which is the fastest, as it computes the powering by shift and computes b only once, and has already all the primes precomputed), you will need to wait ages....

Code:
forprime(n=2,1000, a=1<<n; b=a-1; printf("...%d...%c",n,13); if(sigma(a)-sigma(b)==b, print(n"        ")))
Then think about how much time a LL test takes for 227 or 251, etc.

Last fiddled with by LaurV on 2011-11-17 at 03:28 Reason: added example

2011-11-17, 05:04   #271
axn

Jun 2003

527210 Posts

Quote:
 Originally Posted by LaurV It would take a longer amount of time to compute sigma(x) than it would take to factor x, especially if x has a lot of factors. Computing sigma means factoring x, then combining all its prime factors to make its divisors list, then add them up. so to make "divisors list" of them you have to combine the factors in 2^26 ways (less, because 5 is doubled), which is in itself very time-consumming.
you don't actually make a "divisors" list to compute sigma. there is a much faster way. computing the sigma, given the factorization, is trivial.

http://en.wikipedia.org/wiki/Divisor_function

2011-11-17, 05:45   #272
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

71×139 Posts

Quote:
 Originally Posted by axn you don't actually make a "divisors" list to compute sigma.
Yarrr! I didn't know that! Now after reading, it sounds logical. However the "factoring the number" part stays, and what I said is common sense: if we could compute sigma without factoring the number, then it would make no sense to waste all the time factoring aliquot sequences...

2011-11-17, 06:12   #273
axn

Jun 2003

149816 Posts

Quote:
 Originally Posted by LaurV However the "factoring the number" part stays, and what I said is common sense: if we could compute sigma without factoring the number, then it would make no sense to waste all the time factoring aliquot sequences...
Agreed

2011-11-17, 11:16   #274
Random Poster

Dec 2008

179 Posts

Quote:
 Originally Posted by LaurV if we could compute sigma without factoring the number
...then we would be breaking RSA...

2011-11-17, 18:59   #275
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by LaurV Yarrr! I didn't know that! Now after reading, it sounds logical. However the "factoring the number" part stays, and what I said is common sense: if we could compute sigma without factoring the number, then it would make no sense to waste all the time factoring aliquot sequences...
Code:
forprime(n=2,200,if(n%4==3 && isprime(2*n+1),next(),if(sigma(2^n)-sigma(2^n-1)==2^n-1,print1(n","))))
this is what I have so far.

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 3 2017-08-10 13:47 emily Math 34 2017-07-16 18:44 Nick Math 4 2017-04-01 16:26 Nick Number Theory Discussion Group 0 2016-12-03 11:42 optim PrimeNet 13 2004-07-09 13:51

All times are UTC. The time now is 09:05.

Sat Jan 22 09:05:42 UTC 2022 up 183 days, 3:34, 0 users, load averages: 1.14, 1.36, 1.33