mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Aliquot Sequences

Reply
 
Thread Tools
Old 2012-11-09, 20:00   #2003
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

25×3×7×13 Posts
Default

what are you talking there? Almost any multiple of 31 would do it (look to the 3rd column after zero)

Code:
(02:56:07) gp > forstep(i=1,1000,2, a=2^4*31*i;s=sigma(a)-a;v=factorint(s); if(v[1,2]!=4, print(i", "i%31", "i\31",\t"a"
, "s", "v)))
31, 0, 1,       15376, 15407, [7, 1; 31, 1; 71, 1]
93, 0, 3,       46128, 77004, [2, 2; 3, 3; 23, 1; 31, 1]
155, 0, 5,      76880, 107818, [2, 1; 31, 1; 37, 1; 47, 1]
217, 0, 7,      107632, 138632, [2, 3; 13, 1; 31, 1; 43, 1]
279, 0, 9,      138384, 261795, [3, 1; 5, 1; 31, 1; 563, 1]
341, 0, 11,     169136, 200260, [2, 2; 5, 1; 17, 1; 19, 1; 31, 1]
403, 0, 13,     199888, 231074, [2, 1; 31, 1; 3727, 1]
465, 0, 15,     230640, 508152, [2, 3; 3, 1; 31, 1; 683, 1]
527, 0, 17,     261392, 292702, [2, 1; 31, 1; 4721, 1]
589, 0, 19,     292144, 323516, [2, 2; 31, 1; 2609, 1]
713, 0, 23,     353648, 385144, [2, 3; 31, 1; 1553, 1]
775, 0, 25,     384400, 569873, [31, 2; 593, 1]
837, 0, 27,     415152, 816168, [2, 3; 3, 1; 31, 1; 1097, 1]
899, 0, 29,     445904, 477586, [2, 1; 31, 1; 7703, 1]
(in fact i said "the easiest way" as a joke, there is no other way, and I was expected the question "what is the harder way?" from some nitpicker and I could reply "raising 31 at 4th power", hehe)

Last fiddled with by LaurV on 2012-11-09 at 20:07
LaurV is online now   Reply With Quote
Old 2012-11-09, 20:37   #2004
RobertS
 
RobertS's Avatar
 
Aug 2009
somewhere

3058 Posts
Default

Quote:
Originally Posted by BigBrother View Post
Now at line 5078, I'm already sieving the c133.
found by ECM:
prp44 = 23684003947956653714782183866686101195981013 (curve 1 stg2 B1=46000000 sigma=3481469303)
RobertS is offline   Reply With Quote
Old 2012-11-09, 21:34   #2005
BigBrother
 
Feb 2005
The Netherlands

2×109 Posts
Default

Quote:
Originally Posted by RobertS View Post
found by ECM:
prp44 = 23684003947956653714782183866686101195981013 (curve 1 stg2 B1=46000000 sigma=3481469303)
Meh, I did 1000 curves @ 11M...
BigBrother is offline   Reply With Quote
Old 2012-11-09, 22:17   #2006
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts
Default

Quote:
Originally Posted by Dubslow View Post
Or any even power. Then the sequence is effectively class 4, which means it needs to the rest (besides 2^4*31^(2n)) needs to be a product of 4 primes or less, but that's not sufficient. (There are some restrictions on what each prime has to be mod 4 or mod 8 etc. Also, and an other prime raised to an even power doesn't count against that 4.)
Quote:
Originally Posted by LaurV View Post
what are you talking there? Almost any multiple of 31 would do it (look to the 3rd column after zero)

Code:
(02:56:07) gp > forstep(i=1,1000,2, a=2^4*31*i;s=sigma(a)-a;v=factorint(s); if(v[1,2]!=4, print(i", "i%31", "i\31",\t"a"
, "s", "v)))
31, 0, 1,       15376, 15407, [7, 1; 31, 1; 71, 1]
93, 0, 3,       46128, 77004, [2, 2; 3, 3; 23, 1; 31, 1]
155, 0, 5,      76880, 107818, [2, 1; 31, 1; 37, 1; 47, 1]
217, 0, 7,      107632, 138632, [2, 3; 13, 1; 31, 1; 43, 1]
279, 0, 9,      138384, 261795, [3, 1; 5, 1; 31, 1; 563, 1]
341, 0, 11,     169136, 200260, [2, 2; 5, 1; 17, 1; 19, 1; 31, 1]
403, 0, 13,     199888, 231074, [2, 1; 31, 1; 3727, 1]
465, 0, 15,     230640, 508152, [2, 3; 3, 1; 31, 1; 683, 1]
527, 0, 17,     261392, 292702, [2, 1; 31, 1; 4721, 1]
589, 0, 19,     292144, 323516, [2, 2; 31, 1; 2609, 1]
713, 0, 23,     353648, 385144, [2, 3; 31, 1; 1553, 1]
775, 0, 25,     384400, 569873, [31, 2; 593, 1]
837, 0, 27,     415152, 816168, [2, 3; 3, 1; 31, 1; 1097, 1]
899, 0, 29,     445904, 477586, [2, 1; 31, 1; 7703, 1]
(in fact i said "the easiest way" as a joke, there is no other way, and I was expected the question "what is the harder way?" from some nitpicker and I could reply "raising 31 at 4th power", hehe)
As far as I can tell, every example there has 31^2, which does not contradict what I said. (None of these small multipliers has more than four odd-powered prime factors.)
Code:
>>> for i in range(1,1000,2):
...     n = 2**4*31*i
...     s = a.aliquot(n)
...     v = a.factor(s)
...     if v[2] != 4:
...             print("{}, {}, {}, \t{}={}, \t{}, {}".format(i, i%31, i//31, n, a.factor(n), s, v))
... 
31, 0, 1, 	15376=2^4 * 31^2, 	15407, 7 * 31 * 71
93, 0, 3, 	46128=2^4 * 3 * 31^2, 	77004, 2^2 * 3^3 * 23 * 31
155, 0, 5, 	76880=2^4 * 5 * 31^2, 	107818, 2 * 31 * 37 * 47
217, 0, 7, 	107632=2^4 * 7 * 31^2, 	138632, 2^3 * 13 * 31 * 43
279, 0, 9, 	138384=2^4 * 3^2 * 31^2, 	261795, 3 * 5 * 31 * 563
341, 0, 11, 	169136=2^4 * 11 * 31^2, 	200260, 2^2 * 5 * 17 * 19 * 31
403, 0, 13, 	199888=2^4 * 13 * 31^2, 	231074, 2 * 31 * 3727
465, 0, 15, 	230640=2^4 * 3 * 5 * 31^2, 	508152, 2^3 * 3 * 31 * 683
527, 0, 17, 	261392=2^4 * 17 * 31^2, 	292702, 2 * 31 * 4721
589, 0, 19, 	292144=2^4 * 19 * 31^2, 	323516, 2^2 * 31 * 2609
713, 0, 23, 	353648=2^4 * 23 * 31^2, 	385144, 2^3 * 31 * 1553
775, 0, 25, 	384400=2^4 * 5^2 * 31^2, 	569873, 31^2 * 593
837, 0, 27, 	415152=2^4 * 3^3 * 31^2, 	816168, 2^3 * 3 * 31 * 1097
899, 0, 29, 	445904=2^4 * 29 * 31^2, 	477586, 2 * 31 * 7703
Dubslow is offline   Reply With Quote
Old 2012-11-12, 04:54   #2007
schickel
 
schickel's Avatar
 
"Frank <^>"
Dec 2004
CDP Janesville

1000010010102 Posts
Default

Quote:
Originally Posted by richs View Post
How does a 2^4 * 31 driver break?
Quote:
Originally Posted by Batalov View Post
Because of my avatar, I will reserve 804588.
Most elegant is this way....... (from 804588):
Code:
 1947 .  c114 = 2^4 * 31^2 * 9218757242216532814830455218507779571072152947622474831189587924445638638177013241155356122322458800614403093
 1948 .  c114 = 2 * 31 * 1217 * 4679
(2^4 * 31 ran from i1643:c64...)

It's good to see that there is still some life in a lot of these sequences!
schickel is offline   Reply With Quote
Old 2012-11-12, 05:51   #2008
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

25·3·7·13 Posts
Default

Quote:
Originally Posted by Dubslow View Post
(None of these small multipliers has more than four odd-powered prime factors.)
Hmmm... That is what I missed in your first post, or at least, sounded very complicate as you said it... So, you say that having 5 or more primes different of 2 or 31 in the list, all at odd powers, will make impossible to kill a 2, or breed a new 2. Now, I did not know this, and after a couple of unsuccessful attempts to get a counterexample with pari/gp, I swore I would take the pencil (but not yet). I took gp and did "select 5 random primes, do their product, times 2^4, times an even random power of 31, factor its sigma minus itself, and if the power of 2 is not 4, then print it; repeat forever". When I use 4 primes, it murders few drivers every second (i.e. printing lines), but with 5 or more primes, it prints nothing after 15 minutes. Now I must take the pencil to understand why... And thanks for teaching me something new.

Last fiddled with by LaurV on 2012-11-12 at 05:53 Reason: forgot the "repeat forever" part
LaurV is online now   Reply With Quote
Old 2012-11-12, 07:21   #2009
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

11100001101012 Posts
Default

Quote:
Originally Posted by LaurV View Post
Hmmm... That is what I missed in your first post, or at least, sounded very complicate as you said it... So, you say that having 5 or more primes different of 2 or 31 in the list, all at odd powers, will make impossible to kill a 2, or breed a new 2. Now, I did not know this, and after a couple of unsuccessful attempts to get a counterexample with pari/gp, I swore I would take the pencil (but not yet). I took gp and did "select 5 random primes, do their product, times 2^4, times an even random power of 31, factor its sigma minus itself, and if the power of 2 is not 4, then print it; repeat forever". When I use 4 primes, it murders few drivers every second (i.e. printing lines), but with 5 or more primes, it prints nothing after 15 minutes. Now I must take the pencil to understand why... And thanks for teaching me something new.
Don't think I'm any sort of genius. If you figure out why, please tell me.

I was guessing/extrapolating from what Clifford wrote.
Quote:
Originally Posted by Mr. Stern
Let a change in the exponent a be termed a mutation. This occurs only when the 2s count of t is equal to or less than the class of 2^a*v. In the former case, the exponent a increases and in the latter, a is reduced to the 2s count of t. The stability of a guide depends upon its class: the smaller the class, the more stable the guide. For example, a class 2 guide will mutate if t is the product of two primes of the form 4n+1 or is a prime of the form 8n+3 or 4n+1. But a class 1 guide mutates only when t is a prime of the form 4n+1.
Simply extrapolate that a class n driver might be broken if it factors into n or less odd-powered primes.

(From another part of what he said, and some numerology on my part, I'm fairly sure that when v in a perfect-driver is raised to an odd power, the overall class is raised to the power of 2. That is, 2^1 * 3^2 is class 1, 2^2 * 7^2 is class 2, and 2^4 * 31^2 is class 4, and class 4 means what it does as above. (Edit: This can easily be proven. For a perfect driver, v=2^p-1, v prime. Thus 2s_count(v) = pow_of_2(sigma(v)) = pow_of_2(2^p) = p. Thus p + (-1) = p-1 = power of two in the driver, as in the example below. (The only part I don't understand is how you can just add the two separate 2s counts to get the class.))
Quote:
Originally Posted by Stern, Clifford
When the class of a driver is zero or -1, a small 2s count of t is not sufficient in itself to effect a change in the exponent a because the 2s count of t is always greater than zero. Help is required from one of the components of v by having its exponent aquire an even power in order to temporarily raise the driver's class above zero. For example, when the 2^2 · 7 driver takes the form 2^2 · 7^2, its class of -1 temporarily increases by 3 (the 2s count of 7) so a mutation will occur when the 2s count of t is 2 or 1.

Last fiddled with by Dubslow on 2012-11-12 at 07:27 Reason: forgot link
Dubslow is offline   Reply With Quote
Old 2012-11-12, 20:42   #2010
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

2×32×131 Posts
Default

Quote:
Originally Posted by LaurV View Post
So, you say that having 5 or more primes different of 2 or 31 in the list, all at odd powers, will make impossible to kill a 2, or breed a new 2. Now, I did not know this, and after a couple of unsuccessful attempts to get a counterexample with pari/gp, I swore I would take the pencil (but not yet) ... I must take the pencil to understand why... And thanks for teaching me something new.
The next aliquot value is σ(N)-N.

σ(p^a*q^b*s^c)=σ(p^a)*σ(q^b)*σ(s^c)

σ(p)=p+1, so 2|σ(p)

With 5 or more distinct primes at odd powers,

2^4||N and 2^5|σ(N), so 2^4||σ(N)-N

Of course sometime 4|p+1, so you can get to 2^5 with fewer than five distinct primes

Last fiddled with by wblipp on 2012-11-12 at 20:47 Reason: Fix "five or six" errors
wblipp is offline   Reply With Quote
Old 2012-11-14, 11:52   #2011
yoyo
 
yoyo's Avatar
 
Oct 2006
Berlin, Germany

22·3·72 Posts
Default

BTW: Is somebody working on the remaining C137?
yoyo is offline   Reply With Quote
Old 2012-11-14, 12:00   #2012
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

210408 Posts
Default

not me
LaurV is online now   Reply With Quote
Old 2012-11-15, 17:27   #2013
BigBrother
 
Feb 2005
The Netherlands

3328 Posts
Default

Quote:
Originally Posted by yoyo View Post
BTW: Is somebody working on the remaining C137?
I have, there's now a c157...I've done 4500 curves @ 11M.
BigBrother is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Reserved for MF - Sequence 3366 RichD Aliquot Sequences 406 2020-06-10 03:10
Primes in n-fibonacci sequence and n-step fibonacci sequence sweety439 And now for something completely different 17 2017-06-13 03:49
ECM for c166 from 4788:2661 frmky Aliquot Sequences 36 2011-04-28 06:27
ECM work on 4788:2549.c170 schickel Aliquot Sequences 51 2011-01-05 02:32
80M to 64 bits ... but not really reserved petrw1 Lone Mersenne Hunters 82 2010-01-11 01:57

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

Tue Sep 22 12:06:27 UTC 2020 up 12 days, 9:17, 0 users, load averages: 1.47, 1.37, 1.30

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.