A060937 -id:A060937 - cp's OEIS frontend

A036459 Number of iterations required to reach stationary value when repeatedly applying d, the number of divisors function (A000005).

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

Offset: 1

Labos Elemer

nonn

Iterating d for n, the prestationary prime and finally the fixed value of 2 is reached in different number of steps; a(n) is the number of required iterations.

Each value n > 0 occurs an infinite number of times. For positions of first occurrences of n, see A251483. - Ivan Neretin, Mar 29 2015

			If n=8, then d(8)=4, d(d(8))=3, d(d(d(8)))=2, which means that a(n)=3. In terms of the number of steps required for convergence, the distance of n from the d-equilibrium is expressed by a(n). A similar method is used in A018194.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
B. L. Mayer and L. H. A. Monteiro, On the divisors of natural and happy numbers: a study based on entropy and graphs, AIMS Mathematics (2023) Vol. 8, Issue 6, 13411-13424.

Equals A060937 - 1. Cf. A007624, A036450, A036452, A036453, A036455, A030630.

Table[ Length[ FixedPointList[ DivisorSigma[0, # ] &, n]] - 2, {n, 105}] (* Robert G. Wilson v, Mar 11 2005 *)

for(x = 1,150, for(a=0,15, if(a==0,d=x, if(d<3,print(a-1),d=numdiv(d) )) ))

a(n)=my(t);while(n>2,n=numdiv(n);t++);t \\ Charles R Greathouse IV, Apr 07 2012

a(n) = a(d(n)) + 1 if n > 2.

a(n) = 1 iff n is an odd prime.

A006165 a(1) = a(2) = 1; thereafter a(2n+1) = a(n+1) + a(n), a(2n) = 2a(n).

Original entry on oeis.org

1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 8, 8, 8, 8, 8, 9, 10, 11, 12, 13, 14, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43

Offset: 1

N. J. A. Sloane

a(n+1) is the second-order survivor of the n-person Josephus problem where every second person is marked until only one remains, who is then eliminated; the process is repeated from the beginning until all but one is eliminated. a(n) is first a power of 2 when n is three times a power of 2. For example, the first appearances of 2, 4, 8 and 16 are at positions 3, 6, 12 and 24, or (3*1),(3*2),(3*4) and (3*8). Eugene McDonnell (eemcd(AT)aol.com), Jan 19 2002, reporting on work of Boyko Bantchev (Bulgaria).
Appears to coincide with following sequence: Let n >= 1. Start with a bag B containing n 1's. At each step, replace the two least elements x and y in B with the single element x+y. Repeat until B contains 2 or fewer elements. Let a(n) be the largest element remaining in B at this point. - David W. Wilson, Jul 01 2003
Hsien-Kuei Hwang, S Janson, TH Tsai (2016) show that A078881 is the same sequence, apart from the offset. - N. J. A. Sloane, Nov 26 2017

			From _Peter Bala_, Aug 01 2022: (Start)
1) The sequence {n - a(a(n)) : n >= 1} begins [0, 1, 2, 3, 3, 4, 5, 6, 6, 6, 7, 8, 9, 10, 11, 12, 12, 12, 12, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 49, ...] has the repeated values 3 (twice), 6 (three times), 12 (five times), 24 (nine times), 48 (seventeen times) ..., conjecturally of the form 3*2^m
2) The sequence {n - a(a(a(n))) : n >= 1} begins [0, 1, 2, 3, 4, 5, 6, 7, 7, 8, 9, 10, 11, 12, 13, 14, 14, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 28, 28, 28, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 56, 56, 56, 56, 56, 56, 56, 56, 57, ...] has the repeated values 7 (twice), 14 (three times), 28 (five times), 56 (nine times) ..., conjecturally of the form 7*2^m. (End)

J. Arkin, D. C. Arney, L. S. Dewald and W. E. Ebel, Jr., Families of recursive sequences, J. Rec. Math., 22 (No. 22, 1990), 85-94.
Hsien-Kuei Hwang, S Janson, TH Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint, 2016; http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf. Also Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 1..1024
J.-P. Allouche and J. Shallit, The Ring of k-regular Sequences, II
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
Dale Gerdemann, Second-Order Josephus Problem (video)
Jeffrey Shallit, Intertwining of Complementary Thue-Morse Factors, arXiv:2203.02917 [cs.FL], 2022.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Index entries for sequences related to the Josephus Problem

Cf. A053644, A060973, A066997, A078881.

a := proc (n) option remember; if n = 1 then 1 else n - a(n - a(a(n-1))) end if end proc: seq(a(n), n = 1..100); # Peter Bala, Jul 31 2022

t = {1, 1}; Do[If[OddQ[n], AppendTo[t, t[[Floor[n/2]]] + t[[Ceiling[n/2]]]], AppendTo[t, 2*t[[n/2]]]], {n, 3, 128}] (* T. D. Noe, May 25 2011 *)

a(n) = my(i=logint(n,2)-1); if(bittest(n,i), 2<Kevin Ryde, Aug 06 2022

a(n)=if(n<2,1,n-a(n-a(n\2))); \\ Benoit Cloitre, May 12 2024

from functools import lru_cache
@lru_cache(maxsize=None)
def A006165(n): return 1 if n <= 2 else A006165(n//2) + A006165((n+1)//2) # Chai Wah Wu, Mar 08 2022

def A006165(n): return min(n-(m:=1<1 else 1 # Chai Wah Wu, Oct 22 2024

For n >= 2, if a(n) >= A006257(n), i.e., if msb(n) > n - a(n)/2, then a(n+1) = a(n)+1, otherwise a(n+1) = a(n). - Henry Bottomley, Jan 21 2002
a(n+1) = min(msb(n), 1+n-msb(n)/2) for all n (msb = most significant bit, A053644). - Boyko Bantchev (bantchev(AT)math.bas.bg), May 17 2002
a(1)=1, a(n) = n - a(n - a(a(n-1))). - Benoit Cloitre, Nov 08 2002
a(1)=1, a(n) = n - a(n - a(floor(n/2))). - Benoit Cloitre, May 12 2024
For k > 0, 0 <= i <= 2^k-1, a(2^k+i) = 2^(k-1)+i; for 2^k-2^(k-2) <= x <= 2^k a(x) = 2^(k-1); (also a(m*2^k) = a(m)*2^k for m >= 2). - Benoit Cloitre, Dec 16 2002
G.f.: x * (1/(1+x) + (1/(1-x)^2) * Sum_{k>=0} t^2*(1-t)) where t = x^2^k. - Ralf Stephan, Sep 12 2003
a(n) = A005942(n+1)/2 - n = n - A060973(n) = 2n - A007378(n). - Ralf Stephan, Sep 13 2003
a(n) = A080776(n-1) + A060937(n). - Ralf Stephan
From Peter Bala, Jul 31 2022: (Start)
For k a positive integer, define the k-th iterated sequence a^(k) of a by a^(1)(n) = a(n) and setting a^(k)(n) = a^(k-1)(a(n)) for k >= 2. For example, a^(2)(n) = a(a(n)) and a^(3)(n) = a(a(a(n))).
Conjectures: for n >= 2 there holds
(i) a(n) + a(n - a(n - a(n - a(n - a(n))))) = n;
(ii) a(n - a(n - a(n - a(n)))) = a(n - a(n - a(n - a(n - a(n - a(n))))));
(iii) a^2(n) = a(n - a(n - a(n - a(n))));
(iv) n - a(n) = a(n - a^(2)(n));
(v) a(n - a(n)) = a^(2)(n - a^(2)(n - a^(2)(n - a^(2)(n))));
(vi) for k >= 2, a^(k)(n - a^(k)(n)) = a^(k)(n - a^(k)(n - a^(k)(n - a^(k)(n)))).
(vii) for k >= 1, the sequence {n - a^(k)(n) : n >= 1} has first differences either 0 or 1. We conjecture that the repeated values of the sequence are of the form (2^k - 1)*2^m. The number of repeated values appears to always be 2, 3, 5, 9, 17, 35, ..., independent of k, conjecturally A000051. Two examples are given below.
A similar property may hold for the sequences {n - A060973^(k)(n) : n >= 2^(k-1)}, k = 1,2,3,.... (End)

More terms from Larry Reeves (larryr(AT)acm.org), Jun 12 2002

A200815 Number of iterations of k -> d(k) until n reaches an odd prime.

Original entry on oeis.org

0, 1, 0, 2, 0, 2, 1, 2, 0, 3, 0, 2, 2, 1, 0, 3, 0, 3, 2, 2, 0, 3, 1, 2, 2, 3, 0, 3, 0, 3, 2, 2, 2, 2, 0, 2, 2, 3, 0, 3, 0, 3, 3, 2, 0, 3, 1, 3, 2, 3, 0, 3, 2, 3, 2, 2, 0, 4, 0, 2, 3, 1, 2, 3, 0, 3, 2, 3, 0, 4, 0, 2, 3, 3, 2, 3, 0, 3, 1, 2, 0, 4, 2, 2, 2, 3, 0

Offset: 3

Charles R Greathouse IV, Nov 23 2011

nonn

Csajbók and Kasza call this the tau-iteration length.

			d(10) = 4 and d(4) = 3, an odd prime, so a(10) = 2.

Antti Karttunen, Table of n, a(n) for n = 3..10000
Tímea Csajbók and János Kasza, Iterating the tau-function, Annales Univ. Sci. Budapest., Sec. Math. 35 (2011), pp. 83-93.

Cf. A036459, A060937, A061286, A200810.

nop[n_]:=Length[NestWhileList[DivisorSigma[0,#]&,n,#<3 || CompositeQ[ #]&]]-1; Array[ nop,100,3] (* Harvey P. Dale, Nov 14 2020 *)

a(n)=my(i);while(!isprime(n),i++;n=numdiv(n));i

a(n) <= pi(log_2(n)) = A000720(A000523(n)).

a(n) = A036459(n)-1 = A060937(n)-2, for n >= 3. - Antti Karttunen, Oct 06 2017

A320016 a(1) = a(2) = 1; for n > 2, a(n) = A000005(n) * a(A000005(n)), where A000005(n) gives the number of divisors of n.

Original entry on oeis.org

1, 1, 2, 6, 2, 24, 2, 24, 6, 24, 2, 144, 2, 24, 24, 10, 2, 144, 2, 144, 24, 24, 2, 192, 6, 24, 24, 144, 2, 192, 2, 144, 24, 24, 24, 54, 2, 24, 24, 192, 2, 192, 2, 144, 144, 24, 2, 240, 6, 144, 24, 144, 2, 192, 24, 192, 24, 24, 2, 1728, 2, 24, 144, 14, 24, 192, 2, 144, 24, 192, 2, 1728, 2, 24, 144, 144, 24, 192, 2, 240, 10, 24, 2, 1728

Offset: 1

Antti Karttunen, Nov 24 2018

nonn

Antti Karttunen, Table of n, a(n) for n = 1..10080

Cf. A000005, A036459, A060937.

Cf. also A320009, A320118.

a:=[1,1];; for n in [3..100] do a[n]:=Tau(n)*a[Tau(n)]; od; a; # Muniru A Asiru, Nov 24 2018

Nest[Append[#1, #2 #1[[#2]] ] & @@ {#, DivisorSigma[0, Length@ # + 1]} &, {1, 1}, 82] (* Michael De Vlieger, Nov 25 2018 *)

A320016(n) = if(n<=2,1,numdiv(n)*A320016(numdiv(n)));

a(1) = a(2) = 1; for n > 2, a(n) = A000005(n) * a(A000005(n)), where A000005(n) gives the number of divisors of n.

A346213 Number of iterations of A000688 needed to reach 1 starting at n (n is counted).

Original entry on oeis.org

1, 2, 2, 3, 2, 2, 2, 3, 3, 2, 2, 3, 2, 2, 2, 3, 2, 3, 2, 3, 2, 2, 2, 3, 3, 2, 3, 3, 2, 2, 2, 3, 2, 2, 2, 4, 2, 2, 2, 3, 2, 2, 2, 3, 3, 2, 2, 3, 3, 3, 2, 3, 2, 3, 2, 3, 2, 2, 2, 3, 2, 2, 3, 3, 2, 2, 2, 3, 2, 2, 2, 3, 2, 2, 3, 3, 2, 2, 2, 3, 3, 2, 2, 3, 2, 2, 2

Offset: 1

Amiram Eldar, Jul 10 2021

nonn

The least value of n such that a(n) = 1, 2, ..., 5 is 1, 2, 4, 36 and 264600.

			a(4) = 3 since the trajectory of n = 4, {n, A000688(n), A000688(A000688(n))} = {4, 2, 1}, has the length 3.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Paul Erdős and Aleksandar Ivić, On the iterates of the enumerating function of finite abelian groups, Bulletin Académie serbe des sciences et des arts, Classe des sciences mathématiques et naturelles, Sciences mathématiques, No. 17 (1989), pp. 13-22; alternative link.

Cf. A000688, A060937.

a[n_] := -1 + Length @ FixedPointList[FiniteAbelianGroupCount, n]; Array[a, 100]

Sum_{k<=x} a(k) ~ c*x + O(x^(1/2 + eps)), where c > 1 is a constant (Erdős and Ivić, 1989).

A375513 Irregular triangle read by rows in which row n lists the iterates of the sigma_0(x) map starting at n, until a fixed point is reached, where sigma_0(x) is the number-of-divisors function (A000005).

Original entry on oeis.org

1, 2, 3, 2, 4, 3, 2, 5, 2, 6, 4, 3, 2, 7, 2, 8, 4, 3, 2, 9, 3, 2, 10, 4, 3, 2, 11, 2, 12, 6, 4, 3, 2, 13, 2, 14, 4, 3, 2, 15, 4, 3, 2, 16, 5, 2, 17, 2, 18, 6, 4, 3, 2, 19, 2, 20, 6, 4, 3, 2, 21, 4, 3, 2, 22, 4, 3, 2, 23, 2, 24, 8, 4, 3, 2, 25, 3, 2, 26, 4, 3, 2

Offset: 1

Paolo Xausa, Aug 18 2024

From the second row onward, the fixed point is 2.

First differs from A325239 at row n = 8.

			Triangle begins:
   1;
   2;
   3, 2;
   4, 3, 2;
   5, 2;
   6, 4, 3, 2;
   7, 2;
   8, 4, 3, 2;
   9, 3, 2;
  10, 4, 3, 2;
  11, 2;
  12, 6, 4, 3, 2;
  ...

Paolo Xausa, Table of n, a(n) for n = 1..10000 (rows 1..2292 of triangle, flattened).

Cf. A000005, A036459 (row lengths - 1), A060937 (row lengths, for n >= 2), A053477 (row sums), A325239.

Array[Most[FixedPointList[DivisorSigma[0, #] &, #]] &, 30]

row(n) = if (n==1, [1], my(list=List()); listput(list, n); while (n != 2, n = numdiv(n); listput(list, n)); Vec(list)); \\ Michel Marcus, Aug 21 2024

T(n,1) = n; T(n,k) = A000005(T(n,k-1)), for k = 2..A036459(n)+1.

cp's OEIS Frontend

A036459 Number of iterations required to reach stationary value when repeatedly applying d, the number of divisors function (A000005).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A006165 a(1) = a(2) = 1; thereafter a(2n+1) = a(n+1) + a(n), a(2n) = 2a(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Python

Formula

Extensions

A200815 Number of iterations of k -> d(k) until n reaches an odd prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A320016 a(1) = a(2) = 1; for n > 2, a(n) = A000005(n) * a(A000005(n)), where A000005(n) gives the number of divisors of n.

Views

Author

Keywords

Links

Crossrefs

Programs

GAP

Mathematica

PARI

Formula

A346213 Number of iterations of A000688 needed to reach 1 starting at n (n is counted).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A375513 Irregular triangle read by rows in which row n lists the iterates of the sigma_0(x) map starting at n, until a fixed point is reached, where sigma_0(x) is the number-of-divisors function (A000005).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula