mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Aliquot Sequences (https://www.mersenneforum.org/forumdisplay.php?f=90)

 10metreh 2009-07-10 17:22

Getting started

Welcome to the weird and wonderful world of Aliquot Sequences! This is an exciting project, because it is a mix of most factorization methods, when you have finished one number you get a new one, and (AFAIK) it is the only factorization project that can make your pulse rate increase by 50% (albeit only for a couple of minutes). :smile:

Aliquot sequences are formed by taking one number, adding up all its factors except the number itself, and repeating the process on the new number. So, if you start with 12, you work out 1+2+3+4+6, which comes to 16. Repeat and you get 15, 9, 4, 3, 1. When a sequence reaches 1 it terminates. It also terminates if it ends up in a perfect number or aliquot cycle. Sequences are generally referred to by their starting value. You can read more about aliquot sequences on some of the pages in the [URL="http://www.mersenneforum.org/showthread.php?t=11613"]useful links thread[/URL].

The smallest factors of a term in an aliquot sequence make up the [U]driver[/U] or [U]guide[/U], and these determine whether the sequence will go down (good) or up (bad). You can read about them [URL="http://web.archive.org/web/20110606154446/http://www.lafn.org/~ax810/analysis.htm"]here[/URL].

This project has three parts. The first part is the "main" project. We are working on sequences with starting values below 1000000, focusing on stable sequences that may acquire the downdriver (if you have read the above links (you should have done), you will know what those are). This part of the project is best if you want to break records for things like highest downdriver acquisition. Look in the [url=http://www.mersenneforum.org/showthread.php?t=11625]ranges and status[/url] and [url=http://www.mersenneforum.org/showthread.php?t=11588]reservations[/url] threads for information on which sequences are reservable.
The second part of the project is (are?) the subprojects and special projects. These are the aliquot sequence version of RPS and NPLB "drives". In the subprojects, we take a large range to a specific height or try to escape drivers.
The third part of the project is where we collaborate and work on one sequence, right now 4788 which is over 160 digits. This results in large team GNFS jobs. This is the best section if you don't want to work on a sequence of your own.

Now for the exciting bits: how to contribute!

Download aliqueit from [URL="http://mklasson.com/aliquot.php"]here[/URL]. There are Windows executables and source code included. Also download GMP-ECM, Msieve, Yafu and GGNFS from the "External factoring Programs" links. Put GMP-ECM, Msieve and Yafu in your aliqueit folder. Modify the paths in aliqueit.ini so they correspond with the paths of your binaries (note: yafu path must be kept as just "yafu", it seems to crash if you use the full path). "gnfs_cutoff" defines the cutoff between running Yafu and GGNFS, and the optimum value (the point at which GGNFS becomes faster than Yafu) depends on your system. 100 is a good starting value, but it is lower for 64-bit Linux due to faster sievers.

Create a folder for GGNFS. Now make all the adjustments to msieve (i.e. versions), factMsieve.pl etc. mentioned [URL="http://gilchrist.ca/jeff/factoring/nfs_beginners_guide_perl.html"]here[/URL]. You will need perl installed (latest version recommended). Modify the paths in aliqueit.ini so they point to your perl executable and factMsieve.pl. NOTE: factmsieve.py is not fully bug-free yet, so please use the .pl script.

If you want to participate in a subproject, have a look in one of the subproject threads, reserve the sequence in a post in that thread, and release it in another post when it reaches the subproject target size. If you want to run a sequence for the "main" project, find a sequence that you want to reserve, and reserve it in the [URL="http://www.mersenneforum.org/showthread.php?t=11588"]reservations thread[/URL].

Once you have chosen your sequence, go onto [URL="http://factordb.com/search.php?se=1"]factorDB[/URL], click on "Sequences" (at the top), enter the sequence number and click "Show". Then click on "Download .elf file" (just below "Show"). Save the file in your aliqueit folder and rename it from <the sequence>.elf to alq_<the sequence>.elf, where <the sequence> is the initial term of the sequence.

Now, run "aliqueit <the sequence>" from cmd/shell/whatever it is for your OS. Aliqueit will start! 100-digit composites should take a couple of hours to GNFS on a recent processor, 120-digit composites will take a couple of days. The time it takes for a sequence to reach a certain height is nowhere near certain - downdriver runs may mean that it takes ages. If you interrupt aliqueit while msieve, yafu or GGNFS is running, just restart with "aliqueit <the sequence> -e". If you want to run everything at low priority, run "aliqueit <the sequence> -p".

Alternatively, Yafu can run the ECM and GNFS steps if the -y switch is added. To prepare for this, remove all the "tune_info" lines from yafu.ini (Yafu's config file), and then run "yafu tune()". This computes the GNFS cutoff for your machine, and adds a new "tune_info" line to yafu.ini. Note that this overrides the "gnfs_cutoff" in aliqueit.ini. Using Yafu for ECM and GGNFS requires the paths to the GGNFS folder and ECM binary to be set in yafu.ini. This method allows efficient multithreading of one sequence - change the "threads" parameter in yafu.ini. However, restarting after interruptions is not as easy, especially as there is an unresolved bug in this process.

To submit all your work on a sequence to factorDB, run "aliqueit <the sequence> -s 0". Always do this when you release a sequence.

To release sequences, just post in the reservations thread.

Have fun! :smile:

P.S. Post here or send me or one of the other mods a PM if you feel I've left something out or if you have other questions about the project.

 em99010pepe 2009-07-10 18:11

worker.exe is the automated client for Aliquot Sequences?

 Andi_HB 2009-07-10 18:23

No the worker.exe does all incoming work on Syds Database - not only aliquot sequences. The aliqueit.exe is doing only aliquot sequences.

 mdettweiler 2009-07-10 18:35

[quote=em99010pepe;180504]worker.exe is the automated client for Aliquot Sequences?[/quote]
As Andi_HB said, aliqueit.exe is the client for Aliquot sequences. Note that it needs to be run manually; at this point we don't have an automated client.

 10metreh 2009-07-10 18:36

[quote=em99010pepe;180504]worker.exe is the automated client for Aliquot Sequences?[/quote]

Worker.exe will sometimes get a number from an aliquot sequence, but it gets loads of others too.

 em99010pepe 2009-07-20 18:37

[quote=10metreh;180508]Worker.exe will sometimes get a number from an aliquot sequence, but it gets loads of others too.[/quote]

It would be great for workers to decide what work to run. Can't the server have the ability to send a certain type of work per worker or per IP or per nickname used?

[COLOR=blue][B]10metreh:[/B] AFAIK that isn't supported yet. The database thread (in the main Factoring forum) is the place to ask for that to be supported. However, Syd seems to be taking a summer break.[/COLOR]

 fivemack 2009-07-23 16:45

Dumb driver question

I have an exceedingly stupid question.

For numbers 496k, k=10^10 .. 10^10+10^5, 55% have the sum of divisors not divisible by 496; and about the same proportion for 10^20 .. 10^20+10^5.

But once I have a number divisible by 2^4*31 in an aliquot sequence (246558), getting rid of the 31 seems very hard; I can turn it into 31^2 occasionally, but it always seems to go back to 31 at the next cycle

(ah. If I restrict to numbers which are divisible by 2^4*31 and not by 2^5 or 31^2, it always goes back to 2^4*31; if I have a factor 31^2 then there seems to be an about 0.4 chance of losing the 31 next time, I've just been unlucky twice. But the stake for this 5:2 bet is about 31 large factorisations ...)

 10metreh 2009-07-23 16:58

[quote=fivemack;182366]I have an exceedingly stupid question.

For numbers 496k, k=10^10 .. 10^10+10^5, 55% have the sum of divisors not divisible by 496; and about the same proportion for 10^20 .. 10^20+10^5.

But once I have a number divisible by 2^4*31 in an aliquot sequence (246558), getting rid of the 31 seems very hard; I can turn it into 31^2 occasionally, but it always seems to go back to 31 at the next cycle.[/quote]

Half of the multiples of 496 (i.e. 2^4*31) are divisible by a power of 2 higher than 2^4, making them 2^5*31 or something of that kind. To get rid of the 2^4*31 driver, the 31 must be squared [B]and[/B] the other factors have to be of a certain form (and there can't be too many, you can't escape with any more than 4 other prime factors).

Ah, seen the edit...

 firejuggler 2010-05-25 14:36

ok, i have some problem understanding how it does work...
for example, 128370

the 'first' factor are 2*3*5*11*389, wich is 128370, indeed.
but from what i have read, the next step would be
2+3+5+11+389+128370=128908
128908-128370=589 (why bother adding the first number?)
and it appear that the second 'seed' is 208590... how come?

nvm.. i understood... should have added 6,10,22,778,15,33,1167,4279,30,55,2334,88,3112,6224,330 ,11670 and various other multiplication i forgot

 10metreh 2010-05-25 17:25

[QUOTE=firejuggler;216083](why bother adding the first number?)[/QUOTE]

Because when aliquot sequences are actually calculated, it is actually the sum of all the factors that is calculated first (because there is a formula for it), and the number itself is subtracted. But if you're looking at the actual definition, yes, there is no point in adding the number and then subtracting it. Edited the post. I've also changed the example from 10 to 12 to make it clear that all factors, not just prime factors, are added together.

Also, there is only one subproject currently running, not two as the post claimed until about 30 seconds ago.

 Dubslow 2012-03-23 21:46

Alright, I'm trying not to bug anybody and read the already-posted questions, but the link above that's supposed to talk about drivers and guides etc. is down, and the wiki, while like Wikipedia is good for explaining if you already know it, it isn't much use to me. (Why would 6 being a factor of a term mean that the next term will be higher?) It appears that the lafn.org links in general are all down, however the domain's homepage works fine.

 schickel 2012-03-24 01:51

 Dubslow 2012-03-24 02:02

[QUOTE=schickel;293973]....in the meantime I redirected the Analysis link to The Wayback Machine, but I wonder if we should rehost the info he had posted.[/QUOTE]
That's a great idea, I can't believe I didn't think of that. And thanks for stooping to my math level; unfortunately, discrete math/number theory has never really appealed to me (still doesn't, to be honest), but GIMPS is such an awesome DC project. Now that I'm here though, it seems interesting, but I need to fill in the mathematics :razz: Thanks for helping.

(Among other deficiencies is a complete lack of knowledge of factoring methods besides ECM, of which I only have a basic idea that it's similar to P-1 and uses elliptic curves. I've gleaned that the first line of attack is ECM, but I'm not sure when to switch methods or what to use. You got any more links? :P)

 Bode Didymos 2016-01-16 23:33

About the starting value of an Aliquot Sequence

I have question about the starting value of a aliquot sequence. OP said that an Aliquot sequences are generally referred to by their starting value, is there some numbers that start an Aliquot Sequence but is never in the middle of another aliquot sequence? how do you call those numbers? these numbers would be those that are not in the image of the aliquot sum function. Another related question, if such "patriarch numbers" exist (or what ever you call them), does every branch of an aliquot family tree have a "patriarch" that initiate that branch or its goes on and on indefinitely?

Thank you for your time =D

 Happy5214 2016-01-17 10:45

I will answer the first part of your question and [I]try[/I] to come up with something for the second part. An [I]untouchable number[/I] is a number that does not occur as the aliquot sum of any other number. There are infinitely many untouchable numbers, it is conjectured that only one is odd (5), and it is also believed that all but 2 and 5 are composite. [URL="https://oeis.org/A005114"]This[/URL] is a list of untouchable numbers below 700.

The second part is a little trickier. I would imagine that every full sequence branches from an untouchable number. (Could someone more knowledgeable confirm that?) But don't confuse that untouchable number with the starting value we use. We basically refer to sequences by their lowest value. For example, 564 is used as a starting value, but it is [I]not[/I] an untouchable number as it is the aliquot sum of 563^2. Also, it is conjectured, but not yet proven, that all sequences terminate with a prime, perfect number, or aliquot cycle. There [I]could[/I] be infinitely long sequences that never terminate. So that answer to both parts of your second question could be "yes."

 henryzz 2016-01-18 13:58

[QUOTE=Happy5214;422779]I will answer the first part of your question and [I]try[/I] to come up with something for the second part. An [I]untouchable number[/I] is a number that does not occur as the aliquot sum of any other number. There are infinitely many untouchable numbers, it is conjectured that only one is odd (5), and it is also believed that all but 2 and 5 are composite. [URL="https://oeis.org/A005114"]This[/URL] is a list of untouchable numbers below 700.

The second part is a little trickier. I would imagine that every full sequence branches from an untouchable number. (Could someone more knowledgeable confirm that?) But don't confuse that untouchable number with the starting value we use. We basically refer to sequences by their lowest value. For example, 564 is used as a starting value, but it is [I]not[/I] an untouchable number as it is the aliquot sum of 563^2. Also, it is conjectured, but not yet proven, that all sequences terminate with a prime, perfect number, or aliquot cycle. There [I]could[/I] be infinitely long sequences that never terminate. So that answer to both parts of your second question could be "yes."[/QUOTE]
I think that stating that every sequence starts at an untouchable number might be similar to stating that all sequences terminate as you could just as easily have an infinite sequence backward as forwards.
I would guess that it would be much less likely to happen as numbers in general get bigger as you go upward in a sequence and smaller as you go down. Numbers are limited in how much they can go down so it is less likely to happen.
We do get long sequences reaching smaller numbers than their starting value(i.e. merging with a smaller sequence).
Need to get on with work now. Might think more later.

 bur 2021-07-23 07:14

I noticed that some open end sequences (e.g. 26236) aren't in the blue page reservation table. Are those sequences that merge with others? I couldn't find this number in the terminations/mergers thread though.

 Drdmitry 2021-07-23 08:46

[QUOTE=bur;583810]I noticed that some open end sequences (e.g. 26236) aren't in the blue page reservation table. Are those sequences that merge with others? I couldn't find this number in the terminations/mergers thread though.[/QUOTE]

You can check that 26236:i3 coincides with 4800:i7.Therefore the open sequence which started from 26236 is the same as 4800.

 bur 2021-07-23 10:29

Where did you check it? I used the forum search and it came up empty.

 Drdmitry 2021-07-27 09:47

[QUOTE=bur;583817]Where did you check it? I used the forum search and it came up empty.[/QUOTE]

I would start with looking at the last term of sequence 26236 on [URL="http://factordb.com/sequences.php?se=1&aq=26236&action=last20&fr=0&to=100"]factordb[/URL]. Then I would go to the [URL="https://www.rechenkraft.net/aliquot/AllSeq.html"]blue page[/URL] and look for the sequence which ends in the same factorisation. We know that it should start with something smaller than 26236, which simplifies the task.

 EdH 2021-07-27 12:51

[QUOTE=bur;583817]Where did you check it? I used the forum search and it came up empty.[/QUOTE]Check out [URL="https://www.mersenneforum.org/showthread.php?t=24423&page=3"]this thread[/URL]. The "margins" is really "merges."

Also, I thought you were already running my alimerge3 program.: [URL]https://www.mersenneforum.org/showpost.php?p=582143&postcount=1201[/URL][code]\$ ./alimerge3 26236 1 1
Running base 26236 from 1 through 1 . . .
26236^1:i3 merges with 4800:i7
Run took 15 seconds.[/code]

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