mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Aliquot Sequences

Reply
 
Thread Tools
Old 2016-09-30, 07:43   #34
arbooker
 
arbooker's Avatar
 
"Andrew Booker"
Mar 2013

1258 Posts
Default

Quote:
Originally Posted by Dubslow View Post
Do you mean a cycle whose (iterated) antecedents are all not in the image of \(s\) (i.e. untouchable)? I would call this a (finite) isolated subgraph.
Yep, that's right. It includes, and generalizes, the isolated cycles that Garambois has studied.
arbooker is offline   Reply With Quote
Old 2016-10-01, 18:21   #35
garambois
 
garambois's Avatar
 
Oct 2011

48410 Posts
Default

Quote:
Originally Posted by arbooker View Post
Yep, that's right. It includes, and generalizes, the isolated cycles that Garambois has studied.
Congratulations !
That's very interesting for my own work.

Do you have the number of aliquot antecedents for each even numbers from 2 to 934755337069676 ?

garambois is online now   Reply With Quote
Old 2016-10-02, 23:19   #36
arbooker
 
arbooker's Avatar
 
"Andrew Booker"
Mar 2013

8510 Posts
Default

Quote:
Originally Posted by garambois View Post
Do you have the number of aliquot antecedents for each even numbers from 2 to 934755337069676 ?
No. It might be possible to determine \(s(n)\) for all even \(n\) up to that size with a large-scale computation, but (as I'm sure you're aware) not to store them. Instead I found an algorithm to compute \(s^{-1}(\{n\})\) for a given \(n\) quickly (after initially saying that I didn't believe that was possible ). My implementation is limited to \(n<2^{63}\), but it works reasonably well even at that high end of that range.

I've extended my earlier computations to include all sociable cycles below 1018 and all amicable pairs below 1014, except for one that overflowed the 263 limit. Some interesting graphs emerged, such as the attached one with 58 nodes.
Attached Thumbnails
Click image for larger version

Name:	29215166389256.png
Views:	171
Size:	239.9 KB
ID:	14977  

Last fiddled with by arbooker on 2016-10-02 at 23:59
arbooker is offline   Reply With Quote
Old 2016-10-03, 16:27   #37
garambois
 
garambois's Avatar
 
Oct 2011

22·112 Posts
Default

Arbooker,

I am trying to calculate the numbers of aliquots antecedents for all even numbers between 10^11 and 10^11+10^7. It will take me 4 months.

If I understand, with your algorithm, you could do this in a few days ?

Your work really interest me.

I would like to see your algorithm !
garambois is online now   Reply With Quote
Old 2016-10-03, 17:34   #38
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·2,909 Posts
Default

It should be possible to compress this sort of data quite well I imagine. Otherwise it would take petabytes. Maybe it isn't possible to get it down to nearer a terabyte.

How common is it for a 14 digit number to be part of a finite isolated subgraph? Do most numbers balloon into having a subgraph which is too large to calculate? To me this sort of thing could be as interesting as cycles.

Last fiddled with by henryzz on 2016-10-03 at 17:34
henryzz is online now   Reply With Quote
Old 2016-10-04, 23:45   #39
arbooker
 
arbooker's Avatar
 
"Andrew Booker"
Mar 2013

5·17 Posts
Default

Quote:
Originally Posted by garambois View Post
I am trying to calculate the numbers of aliquots antecedents for all even numbers between 10^11 and 10^11+10^7. It will take me 4 months.

If I understand, with your algorithm, you could do this in a few days ?
Perhaps, but for working out the antecedents of so many numbers I think it would be better to compute s(n) for all possible n. With a windowed sieve you can factor all the numbers up to 2(1011+107) in a matter of hours. I can give you some generic code for this if it would help.
arbooker is offline   Reply With Quote
Old 2016-10-05, 14:00   #40
garambois
 
garambois's Avatar
 
Oct 2011

22×112 Posts
Default

Quote:
Originally Posted by arbooker View Post
Perhaps, but for working out the antecedents of so many numbers I think it would be better to compute s(n) for all possible n. With a windowed sieve you can factor all the numbers up to 2(1011+107) in a matter of hours. I can give you some generic code for this if it would help.
I'm interested by your code !

I want to see if it is faster than mine...
garambois is online now   Reply With Quote
Old 2016-10-21, 12:00   #41
arbooker
 
arbooker's Avatar
 
"Andrew Booker"
Mar 2013

5·17 Posts
Default

Quote:
Originally Posted by arbooker View Post
I'm changing my tune on this a bit. After thinking about it for a while, I found a sublinear algorithm. I'm not sure of the exact complexity, but it's no worse than \(O(n/L[1/2])\), and numerically it appears to be \(O(n^{2/3})\).
It has taken me a while, but I've finally managed a proper analysis of the algorithm, and it's even better than I thought--essentially square root time. A draft of my paper on the algorithm and the computations related to finite connected components is available here.
arbooker is offline   Reply With Quote
Old 2016-10-21, 13:36   #42
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by arbooker View Post
It has taken me a while, but I've finally managed a proper analysis of the algorithm, and it's even better than I thought--essentially square root time. A draft of my paper on the algorithm and the computations related to finite connected components is available here.
d not equal to n could be changed to d less than or equal to n\2 or something similar ( I also thought maybe d=1 below d=n\2 above and d|n to the side but I'm not sure this is the right format) but that's about all I can figure in my small head right now. edit: and if d divides n then it's s(n) that defines the proper divisors sum.

Last fiddled with by science_man_88 on 2016-10-21 at 14:23
science_man_88 is offline   Reply With Quote
Old 2016-10-21, 20:26   #43
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·2,909 Posts
Default

Quote:
Originally Posted by arbooker View Post
It has taken me a while, but I've finally managed a proper analysis of the algorithm, and it's even better than I thought--essentially square root time. A draft of my paper on the algorithm and the computations related to finite connected components is available here.
I have spent a couple of hours reading it yesterday evening. Most of it is fairly easily understandable with a bit of thought.
However, I don't understand how the probability of the k-th iterate of s^-1 containing an odd number >> 1/k.
My first thought is that the probability of the 2nd iterate is something like the probability of the 1st iterate squared. Maybe I am on the wrong track. I suppose that this doesn't take into account that if the first iterate has an odd number the second iterate won't be empty and will definitely have an odd number.
I need to think on this further when it is not evening.

It does now seem to be laid out a bit better than yesterday. The figures/algorithms aren't in the middle of paragraphs anymore.
henryzz is online now   Reply With Quote
Old 2016-10-22, 08:14   #44
arbooker
 
arbooker's Avatar
 
"Andrew Booker"
Mar 2013

5·17 Posts
Default

Quote:
Originally Posted by henryzz View Post
I have spent a couple of hours reading it yesterday evening. Most of it is fairly easily understandable with a bit of thought.
However, I don't understand how the probability of the k-th iterate of s^-1 containing an odd number >> 1/k.
Thanks for your careful reading. What I really mean there is that the chance of getting a p+1 is >> 1/k. That's based simply on the fact that the numbers grow at most like 2kn, and primes occur with density 1/log.

Last fiddled with by arbooker on 2016-10-22 at 08:15
arbooker is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Yet another number sequence... mart_r Miscellaneous Math 5 2011-06-09 22:13
Euclid's proof of the infinite number of primes troels munkner Miscellaneous Math 43 2010-09-06 01:36
What's the next number in this sequence? grandpascorpion Puzzles 15 2006-09-29 20:15
Infinite Composite Sequence? clowns789 Miscellaneous Math 3 2005-11-11 01:02
YANS: Yet another number sequence Uncwilly Puzzles 2 2004-01-28 01:20

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

Thu Mar 4 20:09:36 UTC 2021 up 91 days, 16:20, 0 users, load averages: 1.44, 1.88, 1.77

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