mersenneforum.org Number of sequences that merge with any given sequence - infinite?
 Register FAQ Search Today's Posts Mark Forums Read

2016-09-30, 07:43   #34
arbooker

"Andrew Booker"
Mar 2013

1258 Posts

Quote:
 Originally Posted by Dubslow 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.

2016-10-01, 18:21   #35
garambois

Oct 2011

48410 Posts

Quote:
 Originally Posted by arbooker 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 ?

2016-10-02, 23:19   #36
arbooker

"Andrew Booker"
Mar 2013

8510 Posts

Quote:
 Originally Posted by garambois 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

Last fiddled with by arbooker on 2016-10-02 at 23:59

 2016-10-03, 16:27 #37 garambois     Oct 2011 22·112 Posts 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 !
 2016-10-03, 17:34 #38 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 2·2,909 Posts 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
2016-10-04, 23:45   #39
arbooker

"Andrew Booker"
Mar 2013

5·17 Posts

Quote:
 Originally Posted by garambois 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.

2016-10-05, 14:00   #40
garambois

Oct 2011

22×112 Posts

Quote:
 Originally Posted by arbooker 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...

2016-10-21, 12:00   #41
arbooker

"Andrew Booker"
Mar 2013

5·17 Posts

Quote:
 Originally Posted by arbooker 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.

2016-10-21, 13:36   #42
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by arbooker 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

2016-10-21, 20:26   #43
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

2·2,909 Posts

Quote:
 Originally Posted by arbooker 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.

2016-10-22, 08:14   #44
arbooker

"Andrew Booker"
Mar 2013

5·17 Posts

Quote:
 Originally Posted by henryzz 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

 Similar Threads Thread Thread Starter Forum Replies Last Post mart_r Miscellaneous Math 5 2011-06-09 22:13 troels munkner Miscellaneous Math 43 2010-09-06 01:36 grandpascorpion Puzzles 15 2006-09-29 20:15 clowns789 Miscellaneous Math 3 2005-11-11 01:02 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