A216200 -id:A216200 - cp's OEIS frontend

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.

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

A257670 Minimum term in the sigma(x) -> x subtree whose root is n.

Original entry on oeis.org

1, 2, 2, 2, 5, 5, 2, 2, 9, 10, 11, 5, 9, 9, 2, 16, 17, 10, 19, 19, 21, 22, 23, 2, 25, 26, 27, 5, 29, 29, 16, 16, 33, 34, 35, 22, 37, 37, 10, 27, 41, 19, 43, 43, 45, 46, 47, 33, 49, 50, 51, 52, 53, 34, 55, 5, 49, 58, 59, 2, 61, 61, 16, 64, 65, 66, 67, 67, 69

Offset: 1

Michel Marcus, May 03 2015

nonn

			We have the following trees (a <- b means sigma(a) = b):
  2 <-- 3 <-- 4 <-- 7 <-- 8 <-- 15 <-- 24 <-- 60 <-- ...
                    9 <-- 13 <-- 14 <-’
  5 <-- 6 <-- 12 <-- 28 <-- 56 <-- 120 <-- ...
        11 <-’             /
       10 <-- 18 <-- 39 <-’
The number 1 has strictly speaking an arrow to itself, so it is not part of a tree. (For all n > 1, sigma(n) > n, so no other fixed point or longer "cycle" can exist.) But actually we rather consider connected components, and let a(1) = 1 as the smallest element of this connected component.
a(2) = 2, since there is no smaller x such that sigma(x) = 2: the subtree with root 2 is reduced to a single node: 2. Similarly, a(m) = m for all m in A007369.
For n=3, since sigma(2) = 3, the tree whose root is 3 has 2 nodes: 2 and 3, and the smallest one is 2, hence a(3) = 2.
Similarly, although 24 occurs directly first at sigma(14), it is also reached from 15 which is in turn reached, via intermediate steps, from 2. Thus, the subtree with root 24 has as 2 as smallest element, whence a(24) = 2.

M. F. Hasler, Table of n, a(n) for n = 1..20000, Nov 19 2019 (first 1000 terms from Michel Marcus)
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.
R. J. Mathar, Illustrations

Cf. A000203 (sigma), A007369  (sigma(x) = n has no solution).
Cf. A216200 (number of disjoint trees), A257348 (minimal node of all trees).
Cf. A257669 (number of terms in current tree).

lista(nn) = {my(v = vector(nn)); v[1] = 1; for (i=2, nn, my(s = i); while (s <= nn, if (v[s] == 0, v[s] = i); s = sigma(s););); for (i=1, nn, if (v[i] == 0, v[i] = i);); v;} \\ Michel Marcus, Nov 19 2019

A257670(n)=if(n>2,vecmin(concat(apply(self,invsigma(n)),n)),n) \\ See Alekseyev-link for invsigma(). - David A. Corneth and M. F. Hasler, Nov 20 2019

a(m) = m for m in A007369: sigma(x) = m has no solution. [Corrected by M. F. Hasler, Nov 19 2019]

a(A007497(n)) = 2; a(A051572(n)) = 5; a(A257349(n)) = 16. (These sequences being the trajectory of 2, 5 resp. 16 under iterations of sigma = A000203.)

Edited by M. F. Hasler, Nov 19 2019

A234534 Terms of the cycles reached after iterations of numerator(sigma(n)/n) = A017665(n).

Original entry on oeis.org

1, 8, 15, 127, 128, 144, 255, 403, 448, 512, 1023, 29127, 47360

Offset: 1

Michel Marcus, Dec 27 2013

If all integers were in A014567, then this sequence would not exist and we would be looking at A216200; but some are in A069059, allowing the trajectories of A017665 to go down.
The term of the sequence correspond to the 5 cycles: [1], [15, 8], [448, 127, 128, 255, 144, 403], [1023, 512], [47360, 29127].
Are there some starting x's whose fate will remain unknown, like 276 for A098007?
Are there other cycles to be found?
No other cycles found with largest member less than 10^9.
There are no other cycles with the smallest member < 10^11. All numbers < 10^11 reach one of the five known cycles. - Donovan Johnson, Jan 07 2014

			Obviously 1 is a fixed point for A017665, so 1 is in the sequence.
A017665(8) = 15 and A017665(15) = 8, so both 8 and 15 are in the sequence.

Cf. A000203, A017665.

iscycle(v, nextn) = {for (i=1, #v, if (v[i] == nextn, return (1););); return (0);}
fcycle(n, known) = {v = vector(1); v[1] = n; first = n; while ((nextn = numerator(sigma(n)/n)) <= first, if (vecsearch(known, nextn), return([])); if (iscycle(v, nextn), return (v)); v = concat(v, nextn); n = nextn;); return ([]);}
fcycles(na, nb) = {known = []; known = [1, 8, 127, 512, 29127]; for (n = na, nb, v = fcycle(n, known); if (#v, print(v, ", "); return();););} \\ use empty vector for known to search for cycles from start; when a new cycle is found, insert its smallest term to vector known.

Missing terms 512 and 1023 noticed by Donovan Johnson added by Michel Marcus, Jan 02 2014

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.

A241954 Number of integers x such that the repeated application of sigma(x)->x leads to n.

Original entry on oeis.org

1, 0, 1, 2, 0, 1, 3, 4, 0, 0, 0, 3, 1, 2, 5, 0, 0, 2, 0, 1, 0, 0, 0, 10, 0, 0, 0, 4, 0, 1, 2, 4, 0, 0, 0, 1, 0, 1, 3, 1, 0, 4, 0, 1, 0, 0, 0, 3, 0, 0, 0, 0, 0, 2, 0, 9, 1, 0, 0, 14, 0, 1, 5, 0, 0, 0, 0, 1, 0, 0, 0, 6, 0, 1, 0, 0, 0, 1, 0, 3, 0, 0, 0, 4, 0, 0

Offset: 1

Michel Marcus, Aug 09 2014

nonn

If n is A007369 (sigma(x) = n has no solution) then a(n) = 0.
Obviously a(n) >= A054973(n), number of solutions to sigma(x) = n.
The equality is obtained for terms of A007369, but not only: see a(n) for 1, 3, 6, 13, 18, 20, 30, 31, 36, 38 ...
The maxima for a(n) are : 1, 2, 3, 4, 5, 10, 14, 15 ... and are obtained for n: 1, 4, 7, 8, 15, 24, 60, 120, ...

			There is a single integer such that sigma(x) = 1 so a(1) = 1.
For n=4, we have only sigma(3) = 4 and sigma(sigma(2)) = 4, so a(4) = 2.
For n=7, we have only sigma(4) = 7, sigma(sigma(3)) = 7, and sigma(sigma(sigma(2))) = 7, so a(7) = 3.

Jens Kruse Andersen, 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 (see p. 97)

Cf. A000203, A007369, A054973, A216200.

isok(i, n) = {j = i; while((k = sigma(j)) < n, j = k); k == n;}
a(n) = {if (n == 1, return (1)); nb = 0; for (i=2, n-1, nb += isok(i, n);); nb;}

A256596 a(n) is the number of iterations of the map x->sigma(x) when starting from n before arriving at a number with more than one ancestor, with a(1)=0 and where sigma is the sum of divisors.

Original entry on oeis.org

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

Offset: 1

Michel Marcus, Apr 03 2015

nonn

That is, before arriving at a number x such that A054973(x) > 1.

			For n=2, the repeated map gives 2 -> 3 -> 4 -> 7 -> 8 -> 15 -> 24 where 24 is the first fork with sigma(15)=sigma(23)=24, so with 6 iterations starting from 2 we have a(2)=6, a(3)=5, a(4)=4, a(7)=3, a(8)=2, and a(15)=1.

G. L. Cohen and H. J. J. te Riele, Iterating the sum-of-divisors function, Experimental Mathematics, 5 (1996), pp. 93-100.

Cf. A000203, A054973, A085790, A216200, A241954.

isfork(n) = {my(nba = 0); for (i=2, n-1, if (sigma(i) == n, nba++); if (nba > 1, return (1)););}
a(n) = {if (n==1, return (0)); my(nbit = 0); ok = 0; while (! ok, newn = sigma(n); nbit++; ok = isfork(newn); n = newn;); nbit;}

cp's OEIS Frontend

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

A257670 Minimum term in the sigma(x) -> x subtree whose root is n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

Extensions

A234534 Terms of the cycles reached after iterations of numerator(sigma(n)/n) = A017665(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

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

A241954 Number of integers x such that the repeated application of sigma(x)->x leads to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A256596 a(n) is the number of iterations of the map x->sigma(x) when starting from n before arriving at a number with more than one ancestor, with a(1)=0 and where sigma is the sum of divisors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI