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

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

Offset: 1

Author

Michel Marcus, Mar 12 2013

Keywords

• nonn

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.

Examples

			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.
Some further values: a(100) = 33, a(500) = 167, a(1000) = 333.
Further values: a(10^4) = 3282, a(10^5) = 32739, a(10^6) = 327165, a(10^7) = 3272134. - _M. F. Hasler_, Nov 19 2019
		

Links

• M. F. Hasler, Table of n, a(n) for n = 1..10000
• G. L. Cohen and H. J. J. te Riele, Iterating the sum-of-divisors function, Experimental Mathematics, 5 (1996), pp. 93-100.

Crossrefs

Cf. A000203.

Cf. A257669, A257670: size and smallest number of subtree rooted at n.

Programs

PARI

A216200_vec(N)={my(C=Map(), s, c); vector(N, n, mapisdefined(C,n)&& c+=mapget(C,n) + mapdelete(C,n); mapput(C, s=sigma(n), if(mapisdefined(C,s), mapget(C,s))+1); n-c)} \\ Use allocatemem() for N >= 10^6.
A216200(n)={my(C=Map(), s); n-sum(n=2,n, mapput(C, s=sigma(n), if(mapisdefined(C,s), mapget(C,s))+1); if(mapisdefined(C,n), mapget(C,n) + mapdelete(C,n)))} \\ (slightly faster to compute a single value)
tree(n)=[n,if(n>1,apply(self,invsigma(n)),"fixed point")] \\ to create the tree rooted in n. (End)

Formula

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

It appears that a(n)/n = 0.32721... + O(1/sqrt(n)). - M. F. Hasler, Nov 19 2019