mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > science_man_88

Closed Thread
 
Thread Tools
Old 2011-09-04, 13:51   #265
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
science_man_88 is offline  
Old 2011-09-04, 14:09   #266
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
science_man_88 is offline  
Old 2011-09-10, 14:04   #267
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts
Default

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 ?
science_man_88 is offline  
Old 2011-10-31, 19:50   #268
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

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.
science_man_88 is offline  
Old 2011-11-17, 00:39   #269
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

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.
science_man_88 is offline  
Old 2011-11-17, 03:05   #270
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

268D16 Posts
Default

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 View Post
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
LaurV is online now  
Old 2011-11-17, 05:04   #271
axn
 
axn's Avatar
 
Jun 2003

527210 Posts
Default

Quote:
Originally Posted by LaurV View Post
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. <snip>
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
axn is offline  
Old 2011-11-17, 05:45   #272
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

71×139 Posts
Default

Quote:
Originally Posted by axn View Post
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...
LaurV is online now  
Old 2011-11-17, 06:12   #273
axn
 
axn's Avatar
 
Jun 2003

149816 Posts
Default

Quote:
Originally Posted by LaurV View Post
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
axn is offline  
Old 2011-11-17, 11:16   #274
Random Poster
 
Random Poster's Avatar
 
Dec 2008

179 Posts
Default

Quote:
Originally Posted by LaurV View Post
if we could compute sigma without factoring the number
...then we would be breaking RSA...
Random Poster is offline  
Old 2011-11-17, 18:59   #275
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
science_man_88 is offline  
Closed Thread

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Mersenne Primes p which are in a set of twin primes is finite? carpetpool Miscellaneous Math 3 2017-08-10 13:47
Distribution of Mersenne primes before and after couples of primes found emily Math 34 2017-07-16 18:44
Mersenne primes and class field theory Nick Math 4 2017-04-01 16:26
Basic Number Theory 11: Gaussian primes Nick Number Theory Discussion Group 0 2016-12-03 11:42
Mersenne Wiki: Improving the mersenne primes web site by FOSS methods 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔