A257670 -id:A257670 - cp's OEIS frontend

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

Michel Marcus, Mar 12 2013

nonn

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.

			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

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.

Cf. A000203.

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

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)

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

A257348 Repeatedly applying the map x -> sigma(x) partitions the natural numbers into a number of disjoint trees; sequence gives the (conjectural) list of minimal representatives of these trees.

Original entry on oeis.org

1, 2, 5, 16, 19, 27, 29, 33, 49, 50, 52, 66, 81, 85, 105, 146, 147, 163, 170, 189, 197, 199, 218, 226, 243, 262, 303, 315, 343, 424, 430, 438, 453, 461, 463, 469, 472, 484, 489, 513, 530, 550, 584, 677, 722, 746, 786, 787, 804, 813, 821, 831, 842, 859, 867, 876, 892, 903, 914, 916, 937, 977, 982, 988, 990, 1029

Offset: 1

N. J. A. Sloane, May 01 2015, following a suggestion from Kerry Mitchell

Very little is known for certain. Even the trajectories of 2 (A007497) and 5 (A051572) under repeated application of the map x -> sigma(x) (cf. A000203) are only conjectured to be disjoint.
The thousand-term b-file (up to 141441) has been checked to correspond to disjoint trees for 265 iterations of sigma on each term, and every non-term n < 141441 merges (in at most 21 iterations) with an earlier iteration sequence. - Hans Havermann, Nov 22 2019
Rather than trees we mean connected components of the graphs with edges x -> sigma(x). The number 1 is a fixed point, i.e., a cycle of length 1 under iterations of sigma, it is not part of a tree. But since sigma(n) > n for n > 1 there are no other cycles. - M. F. Hasler, Nov 21 2019

Kerry Mitchell, Posting to Math Fun Mailing List, Apr 30 2015

Hans Havermann, Table of n, a(n) for n = 1..1000
G. L. Cohen and H. J. J. te Riele, Iterating the sum-of-divisors function, Experimental Mathematics, 5 (1996), pp. 91-100. See Eq. (4.2).

Cf. A000203 (sigma), A007497 (trajectory of 2), A051572 (trajectory of 5), A257349 (trajectory of 16).

Cf. A216200 (number of disjoint trees up to n); A257669 and A257670: size and smallest number of subtree rooted in n.

More terms from Hans Havermann, May 02 2015

A257669 Number of terms in the sigma(x) -> x subtree whose root is n.

Original entry on oeis.org

1, 1, 2, 3, 1, 2, 4, 5, 1, 1, 1, 4, 2, 3, 6, 1, 1, 3, 1, 2, 1, 1, 1, 11, 1, 1, 1, 5, 1, 2, 3, 5, 1, 1, 1, 2, 1, 2, 4, 2, 1, 5, 1, 2, 1, 1, 1, 4, 1, 1, 1, 1, 1, 3, 1, 10, 2, 1, 1, 15, 1, 2, 6, 1, 1, 1, 1, 2, 1, 1, 1, 7, 1, 2, 1, 1, 1, 2, 1, 4, 1, 1, 1, 5, 1, 1

Offset: 1

Michel Marcus, May 03 2015

nonn

For terms m of A007369, numbers m such that sigma(x) = m has no solution, as well as for m = 1, a(m) = 1.
See A257670 for more information, examples, etc. - M. F. Hasler, Nov 19 2019
Records are: a(1) = 1 = a(2), a(3) = 2, a(4) = 3, a(7) = 4, a(8) = 5, a(15) = 6, a(24) = 11, a(60) = 15, a(120) = 16, a(168) = 22 = a(336), a(360) = 26, a(480) = 39, a(1344) = 43, a(1512) = 54, a(1920) = 57, a(2016) = 65, a(2880) = 70, a(4800) = 80, a(5040) = 88, a(6552) = 93, a(8064) = 125, ... - M. F. Hasler, Nov 20 2019

			For n = 2, a(2) = 1, since there is no x such that sigma(x) = 2, so the subtree with root 2 is reduced to a single node: 2.
For n = 3, since sigma(2) = 3, the tree with root 3 has 2 nodes: 2 and 3, hence a(3) = 2.

M. F. Hasler, Table of n, a(n) for n = 1..10000, Nov 20 2019
M. Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems: invsigma.gp, Oct. 2005
G. L. Cohen and H. J. J. te Riele, Iterating the sum-of-divisors function, Experimental Mathematics, 5 (1996), pp. 91-100.

Cf. A007369 (sigma(x) = n has no solution).
Cf. A216200 (number of disjoint trees), A257348 (minimal nodes of all trees).
Cf. A257670 (minimal representative of current tree).

A257669_vec(N)={my(C=Map(),s,c); vector(N,n,mapput(C,s=sigma(n), if(mapisdefined(C,s), mapget(C,s))+ c=if(mapisdefined(C,n), mapget(C,n) + mapdelete(C,n))+1);c)} \\ M. F. Hasler, Nov 20 2019

apply( A257669(n)=if(n>1,vecsum(apply(self,invsigma(n))))+1, [1..99]) \\ See Alekseyev-link for invsigma(). - M. F. Hasler, Nov 20 2019, replacing earlier code from Michel Marcus

a(A007369(n)) = 1.

A286011 a(1)=1, and for n>1, a(n) is the maximum number of iterations of sigma resulting in n, starting at some integer k; or 0 if n cannot be reached from any k.

Original entry on oeis.org

1, 0, 1, 2, 0, 1, 3, 4, 0, 0, 0, 2, 1, 2, 5, 0, 0, 1, 0, 1, 0, 0, 0, 6, 0, 0, 0, 3, 0, 1, 1, 2, 0, 0, 0, 1, 0, 1, 2, 1, 0, 2, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 4, 1, 0, 0, 7, 0, 1, 3, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 1, 0, 0, 0, 1, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0, 0, 2

Offset: 1

Michel Marcus, Apr 30 2017

nonn

a(n)=0 for n in A007369 and a(n)>0 for n in A002191.
Records are found at indices given by A007497.
The above would be correct for a(1) = 0 (in a weak sense) or rather a(1) = -1 (for infinity), but as the sequence is defined, 2 & 3 do not produce a record, so the indices of records are 1, (3), 4, 7, ... = {1} U A007497 \ {2, (3)}. - M. F. Hasler, Nov 20 2019

			a(4)=2 because 4=sigma(3), but also sigma(sigma(2)) with 2 iterations.
a(7)=3 because 7=sigma(4), but also sigma(sigma(3)), and sigma(sigma(sigma(2))), with 3 iterations.

Robert Israel, Table of n, a(n) for n = 1..10000
M. Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems: invsigma.gp, Oct. 2005

Cf. A000203, A002191, A007369, A007497, A257670.

N:= 100: # to get a(1)..a(N)
V:= Vector(N):
for n from 1 to N do
  s:= numtheory:-sigma(n);
  if s <= N then V[s]:= max(V[s],V[n]+1) fi
od:
convert(V,list); # Robert Israel, May 01 2017

a(n) = {if (n==1, return(1)); vn = vector(n-1, k, k+1); nb = 0; knb = 0; ok = 1; while(ok, nb++; vn = vector(#vn, k, sigma(vn[k])); svn = Set(vn); if (#select(x->x==n, svn), knb = nb); if (!#select(x->x<=n, svn), ok = 0);); knb;}

apply( A286011(n)=if(n<3,2-n, n=invsigma(n), vecmax(apply(self,n))+1), [1..99]) \\ See Alekseyev-link for invsigma(). - M. F. Hasler, Nov 20 2019

A309727 a(n) is the least integer k such that for some iteration of sigma applied to k, one gets the n-th term of A002191, the list of possible values for the function sum of divisors.

Original entry on oeis.org

1, 2, 2, 5, 2, 2, 5, 9, 9, 2, 10, 19, 2, 5, 29, 16, 16, 22, 37, 10, 27, 19, 43, 33, 34, 5, 49, 2, 61, 16, 67, 29, 73, 45, 49, 43, 27, 22, 50, 19, 52, 101, 16, 85, 109, 22, 73, 5, 81, 33, 67, 64, 50, 86, 81, 137, 76, 66, 149, 111, 99, 157, 81, 106, 163, 2, 52, 173, 129

Offset: 1

Michel Marcus, Oct 14 2019

nonn

The set union of this sequence is 1 U A007369.

			For n = 5, A002191(5) is 7, and 4 iterations of sigma applied to 2 give 7, and no integer less than 2 will give 7, so a(5)=2.

Michel Marcus, Table of n, a(n) for n = 1..2503

Cf. A000203, A002191, A007369, A007497, A051572, A257349.

A257670 is a better version for this sequence.

list(lim) = select(n->n<=lim, Set(vector(lim\=1, n, sigma(n))));
lista(nn) = {my(vs = list(nn), v = vector(#vs)); v[1] = 1; for (n=2, #vs, for (k=2, vs[n], my(kk=k); while (sigma(kk) <= vs[n], kk=sigma(kk)); if (kk == vs[n], v[n] = k; break););); v;}

a(n) = 2 when A002191(n) is in A007497.
a(n) = 5 when A002191(n) is in A051572.
a(n) = 16 when A002191(n) is in A257349.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A257348 Repeatedly applying the map x -> sigma(x) partitions the natural numbers into a number of disjoint trees; sequence gives the (conjectural) list of minimal representatives of these trees.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A257669 Number of terms in the sigma(x) -> x subtree whose root is n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

A286011 a(1)=1, and for n>1, a(n) is the maximum number of iterations of sigma resulting in n, starting at some integer k; or 0 if n cannot be reached from any k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

PARI

A309727 a(n) is the least integer k such that for some iteration of sigma applied to k, one gets the n-th term of A002191, the list of possible values for the function sum of divisors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula