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

22·2,239 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 offline   Reply With Quote
Old 2012-11-09, 20:37   #2004
RobertS
 
RobertS's Avatar
 
Aug 2009
somewhere

197 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

2·1,061 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

22FC16 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 offline   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

3×29×83 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

93816 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

10010011112 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

22·2,239 Posts
Default

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

2·109 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 432 2020-10-29 00:57
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 22:47.

Wed Dec 2 22:47:33 UTC 2020 up 83 days, 19:58, 2 users, load averages: 0.99, 1.34, 1.77

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.