

A216200


Number of disjoint trees that appear while iterating the sum of divisors function up to n.


6



1, 2, 2, 2, 3, 3, 3, 3, 4, 5, 6, 5, 5, 5, 5, 6, 7, 6, 7, 7, 8, 9, 10, 8, 9, 10, 11, 11, 12, 12, 11, 10, 11, 12, 13, 13, 14, 14, 14, 14, 15, 13, 14, 14, 15, 16, 17, 15, 16, 17, 18, 19, 20, 19, 20, 19, 19, 20, 21, 19, 20, 20, 20, 21, 22, 23, 24, 24, 25, 26, 27
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

A tree like (2, 3, 4, 7, 8) contains all numbers below 8 such that iterating the sum of divisors function to any of them, while staying below 8, will lead to 8.
Inspired by the article in link, where a (p1, p2, p3)tree is defined with p1 the smallest number in the tree, and p2, p3, such that all sequences {sigma^i(n)} (iterations of sigma), with p1<=n<=p2 and sigma^i(n)<p3 have nonempty intersection with {sigma^i(p1)}. For instance, 21 (p1, 200, 10^10)trees and 64 (p1, 1000, 10^100)trees were found.


LINKS

Table of n, a(n) for n=1..71.
G. L. Cohen and H. J. J. te Riele, Iterating the sumofdivisors function, Experimental Mathematics, 5 (1996), pp. 93100.


FORMULA

For n>1 a(n) = a(n1) + 1  A054973(n), a(1) = 1.  Michel Marcus, Oct 22 2013


EXAMPLE

For n=23, there are 10 disjoint trees: (1), (2, 3, 4, 7, 8, 15), (5, 6, 11, 12), (9, 13, 14), (10, 17, 18), (16), (19, 20), (21), (22), (23). With the arrival of 24, 3 trees are united, that is those that contain 15, 14 and 23, so that there are now 8 trees. Here are some further values : a(100)=33, a(500)=167, a(1000)=333.


PROG

(PARI) lista(n) = {vecb = readvec("b000203.log"); tree = vector(n, x, []); for (i=1, n, tree[i] = concat(tree[i], i); for (j=1, i, for (k=1, length(tree[j]), if (vecb[tree[j][k]] == i, tree[j] = concat(tree[j], i)); ); ); myset = Set(); for (j=1, i, lenj = length(tree[j]); if (lenj > 0, myset = setunion (myset, Set(tree[j][lenj]))); ); print1(length(myset), ", "); ); } \\ with b000203.log being the second column of b000203.txt. Michel Marcus, Mar 12 2013


CROSSREFS

Cf. A000203.
Sequence in context: A216503 A216672 A104055 * A157873 A022870 A237050
Adjacent sequences: A216197 A216198 A216199 * A216201 A216202 A216203


KEYWORD

nonn


AUTHOR

Michel Marcus, Mar 12 2013


STATUS

approved



