A036452 -id:A036452 - 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.

A036450 a(n) = d(d(d(n))), the 3rd iterate of the number-of-divisors function with an initial value of n.

Original entry on oeis.org

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

Offset: 1

Labos Elemer

nonn

The iterated d function rapidly converges to the fixed point 2.
From N. J. A. Sloane, Jun 02 2014: (Start)
The fourth iterate begins as follows:
1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ... . (End)

			n = 5040, d(5040) = 60, d(d(5040)) = d(60) = 12 and a(5040) = d(12) = 6.

S. Ramanujan, Collected Papers, Ed. G. H. Hardy et al., Cambridge 1927; Chelsea, NY, 1962, p. 128. - N. J. A. Sloane, Jun 02 2014

Enrique Pérez Herrero, Table of n, a(n) for n = 1..2000
R. Bellman and H. N. Shapiro, On a problem in additive number theory, Annals Math., 49 (1948), 333-340.

Cf. A000005, A010553, A036452, A036453.

f[n_]:=Length[Divisors[n]];Table[Nest[f,n,3],{n,6!}] (* Vladimir Joseph Stephan Orlovsky, Mar 10 2010 *)

a(n)=numdiv(numdiv(numdiv(n))) \\ Charles R Greathouse IV, Nov 16 2022

from sympy import divisor_count
def A036450(n): return divisor_count(divisor_count(divisor_count(n))) # Chai Wah Wu, Nov 17 2022

A036453 a(n) = d(d(d(d(d(n))))), the 5th iterate of the number-of-divisors function d = A000005, with initial value n.

Original entry on oeis.org

1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2

Offset: 1

Labos Elemer

nonn

The iterated d function rapidly converges to fixed point 2. In the 5th iterated d-sequence, the first term different from the fixed point 2 appears at n = 5040. The 6th and further iterated sequences have very long initial segment of 2's. In the 6th one the first non-stationary term is a(293318625600) = 3. In such sequences any large value occurs infinite many times and constructible.

Differs from A007395 for n = 1, 5040, 7920, 8400, 9360, 10080, 10800, etc. - R. J. Mathar, Oct 20 2008

			E.g., n = 96 and its successive iterates are 12, 6, 4, 3 and 2. The 5th term is a(96) = 2 is stationary (fixed).

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Cf. A000005, A010553, A036450, A036452.

Table[Nest[DivisorSigma[0,#]&,n,5],{n,110}] (* Harvey P. Dale, Jun 18 2021 *)

a(n)=my(d=numdiv);d(d(d(d(d(n))))) \\ Charles R Greathouse IV, Apr 07 2012

Previous Mathematica program replaced by Harvey P. Dale, Jun 18 2021

A036454 Prime powers with special exponents: q^(p-1) where p > 2 and q are prime numbers.

Original entry on oeis.org

4, 9, 16, 25, 49, 64, 81, 121, 169, 289, 361, 529, 625, 729, 841, 961, 1024, 1369, 1681, 1849, 2209, 2401, 2809, 3481, 3721, 4096, 4489, 5041, 5329, 6241, 6889, 7921, 9409, 10201, 10609, 11449, 11881, 12769, 14641, 15625, 16129, 17161, 18769, 19321

Offset: 1

Labos Elemer

Composite numbers with a prime number of divisors.

			From powers of 2: 4,16,64,1024,4096,65536 are in the sequence since exponent+1 is also prime. The same powers of any prime base are also included.

T. D. Noe, Table of n, a(n) for n = 1..1000

Intersection of A002808 and A009087.

Cf. A000005, A010051, A010553, A010055, A100995, A036450, A036452, A036459, A283262.

a009087 n = a009087_list !! (n-1)
a009087_list = filter ((== 1) . a010051 . (+ 1) . a100995) a000961_list
-- Reinhard Zumkeller, Jun 05 2013

[n: n in [1..20000] | not IsPrime(n) and IsPrime(DivisorSigma(0, n))]; // Vincenzo Librandi, May 19 2015

N:= 10^5:
P1:= select(isprime,[2,seq(2*i+1,i=1..floor((sqrt(N)-1)/2))]):
P2:= select(`<=`,P1,1+ilog2(N))[2..-1]:
S:= {seq(seq(p^(q-1), q = select(`<=`,P2,1+floor(log[p](N)))),p=P1)}:
sort(convert(S,list)); # Robert Israel, May 18 2015

specialPrimePowerQ[n_] := With[{f = FactorInteger[n]}, Length[f] == 1 && PrimeQ[f[[1, 1]]] && f[[1, 2]] > 1 && PrimeQ[f[[1, 2]] + 1]]; Select[Range[20000], specialPrimePowerQ]  (* Jean-François Alcover, Jul 02 2013 *)
Select[Range[20000], ! PrimeQ[#] && PrimeQ[DivisorSigma[0, #]] &] (* Carlos Eduardo Olivieri, May 18 2015 *)

for(n=1,34000, if(isprime(n), n++,x=numdiv(n); if(isprime(x),print(n))))

list(lim)=my(v=List(),t);lim=lim\1+.5;forprime(p=3,log(lim)\log(2) +1, t=p-1; forprime(q=2,lim^(1/t),listput(v,q^t))); vecsort(Vec(v))
\\ Charles R Greathouse IV, Apr 26 2012

from sympy import primepi, integer_nthroot, primerange
def A036454(n):
    def f(x): return int(n+x-sum(primepi(integer_nthroot(x, p-1)[0]) for p in primerange(3,x.bit_length()+1)))
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    return bisection(f,n,n) # Chai Wah Wu, Sep 12 2024

d(d(a(n))) = 2, where d(x) = tau(x) = sigma_0(x) is the number of divisors of x.
a(n) = (n log n)^2 + 2n^2 log n log log n + O(n^2 log n). - Charles R Greathouse IV, Apr 26 2012
(1 - A010051(a(n))) * A010055(a(n)) * A010051(A100995(a(n))+1) = 1. - Reinhard Zumkeller, Jun 05 2013
A036459(a(n)) = 2. - Ivan Neretin, Jan 25 2016
a(n) = A283262(n)^2. - Amiram Eldar, Jul 04 2022
Sum_{n>=1} 1/a(n) = Sum_{k>=2} P(prime(k)-1) = 0.54756961912815344341..., where P is the prime zeta function. - Amiram Eldar, Jul 10 2022

A036455 Numbers n such that d(d(n)) is an odd prime, where d(k) is the number of divisors of k.

Original entry on oeis.org

6, 8, 10, 14, 15, 21, 22, 26, 27, 33, 34, 35, 36, 38, 39, 46, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95, 100, 106, 111, 115, 118, 119, 120, 122, 123, 125, 129, 133, 134, 141, 142, 143, 145, 146, 155, 158, 159, 161, 166, 168, 177, 178, 183

Offset: 1

Labos Elemer

nonn

Compare with sequence A007422 and A030513 -- the resemblance is rather strong. Still this sequence is different. For example, 36, 100, 120, and 168 are here.

			a(15) = 39 and d(39) = 4, d(d(39)) = d(4) = 3 and d(d(d(39))) = 2. After 3 iteration the equilibrium is reached.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Cf. A000005, A007422, A030513, A036450, A036452, A036454, A036456, A036457, A036458.

filter:= proc(n) local r;
  r:= numtheory:-tau(numtheory:-tau(n));
  r::odd and isprime(r)
end proc:
select(filter, [$1..1000]); # Robert Israel, Feb 02 2016

fQ[n_] := Module[{d2 = DivisorSigma[0, DivisorSigma[0, n]]}, d2 > 2 && PrimeQ[d2]]; Select[Range[200], fQ] (* T. D. Noe, Jan 22 2013 *)

is(n)=isprime(n=numdiv(numdiv(n))) && n>2 \\ Charles R Greathouse IV, Jan 22 2013

d(d(d(a(n)))) = 2 for all n.

A036459(a(n)) = 3. - Ivan Neretin, Jan 25 2016

Definition clarified by R. J. Mathar and Charles R Greathouse IV, Jan 22 2013

A036457 Numbers k for which exactly 5 applications of A000005 are needed to reach 2.

Original entry on oeis.org

60, 72, 84, 90, 96, 108, 126, 132, 140, 150, 156, 160, 180, 198, 200, 204, 220, 224, 228, 234, 240, 252, 260, 276, 288, 294, 300, 306, 308, 315, 336, 340, 342, 348, 350, 352, 360, 364, 372, 380, 392, 396, 414, 416, 420, 432, 444, 450, 460, 468, 476, 480

Offset: 1

Labos Elemer

nonn

Subsequences include A030630 (numbers with 12 divisors), A030636 (numbers with 18 divisors), A030638 (numbers with 20 divisors), A137491 (numbers with 28 divisors), etc. [edited by Jon E. Schoenfield, May 12 2018]

			a(13)=180; the successive iterates are 18, 6, 4, 3, and finally the 5th is 2;
a(3)=84; divisor numbers are 12, 6, 4, 3, and 2.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A000005, A007624, A036450, A036452, A036453, A036455, A030630.

A036459:= proc(n) option remember;
  if n <= 2 then 0 else 1 + procname(numtheory:-tau(n)) fi
end proc:
select(A036459 = 5, [$1..1000]); # Robert Israel, Jan 25 2016

Select[Range@ 480, Last@ # == 2 && #[[5]] != 2 &@ NestList[DivisorSigma[0, #] &, #, 5] &] (* Michael De Vlieger, Jan 26 2016 *)

is(n)=for(i=1,4,n=numdiv(n); if(n<3, return(0))); numdiv(n)==2 \\ Charles R Greathouse IV, Sep 17 2015

d(d(d(d(d(a(n)))))) = 2 for all n.

A036459(a(n)) = 5. - Ivan Neretin, Jan 25 2016

New name from Robert Israel, Jan 25 2016

A053472 a(n) is the cototient of n (A051953) iterated 4 times.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 4, 0, 2, 0, 4, 0, 4, 0, 4, 0, 4, 0, 8, 0, 4, 1, 4, 0, 4, 0, 8, 0, 4, 0, 8, 0, 4, 1, 8, 0, 8, 0, 4, 1, 4, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 16, 0, 8, 1, 12, 0, 16, 1, 8, 0, 8, 0, 16, 0, 8, 0, 8, 0, 8, 0, 8, 1, 16, 0, 16

Offset: 1

Labos Elemer, Jan 14 2000

nonn

As iteration of A051953 progresses, powers of 2 may appear and it ends at fixed point 0. Analogous 4th iterates for A000005 or A000010 are A036452 and A049100.

It is assumed here that the value of A051953 at 0 is 0. - Antti Karttunen, Dec 22 2017

			n=50, n_1 = n - phi(n) = 50 - 20 = 30, n_2 = n_1 - Phi(n_1) = 30 - 8 = 22, n_3 = 22 - Phi(22) = 12, n_4 = n_3 - Phi(n_3) = 12 - 4 = 8 so the 50th term is 8.

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

Cf. A051953, A000005, A000010, A036452, A049100.

Cf. A053470, A053471, A053473.

Array[Nest[# - EulerPhi@ # &, #, 4] &, 102] (* Michael De Vlieger, Dec 23 2017 *)

A051953(n) = if(!n,n,(n-eulerphi(n))); \\ With modification that returns zero for zero.
A053472(n) = A051953(A051953(A051953(A051953(n)))); \\ Antti Karttunen, Dec 22 2017

A036456 Numbers k for which exactly 4 applications of A000005 are needed to reach 2.

Original entry on oeis.org

12, 18, 20, 24, 28, 30, 32, 40, 42, 44, 45, 48, 50, 52, 54, 56, 63, 66, 68, 70, 75, 76, 78, 80, 88, 92, 98, 99, 102, 104, 105, 110, 112, 114, 116, 117, 124, 128, 130, 135, 136, 138, 144, 147, 148, 152, 153, 154, 162, 164, 165, 170, 171, 172, 174, 175, 176, 182

Offset: 1

Labos Elemer

nonn

Similar to but different from A007624. Terms like 60, 72, 84, 90, 96, 108, 126, etc. are not present here.

			a(3)=20 and a(17)=63; for both x=20 and 63, d(x)=6 and d(d(x))=4, the 3rd iterates are 3 and the equilibrium value, i.e., 2 appears as 4th iterates.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000005, A007624, A036450, A036452, A036453, A036455.

isok(n) = ((nd=numdiv(n)) != 2) && ((nd=numdiv(nd)) != 2) && ((nd=numdiv(nd)) != 2) && ((nd=numdiv(nd)) == 2); \\ Michel Marcus, Dec 30 2013 & Jan 26 2015

With d(n) = number of divisors(n), d(d(d(d(a(n))))) = 2 and d(d(d(a(n)))) > 2.

A036459(a(n)) = 4. - Ivan Neretin, Jan 25 2016

New name (using new name for A036457 from Robert Israel) from Jon E. Schoenfield, May 12 2018

A053477 Sum of iterates of divisor number function A000005.

Original entry on oeis.org

1, 2, 5, 9, 7, 15, 9, 17, 14, 19, 13, 27, 15, 23, 24, 23, 19, 33, 21, 35, 30, 31, 25, 41, 30, 35, 36, 43, 31, 47, 33, 47, 42, 43, 44, 50, 39, 47, 48, 57, 43, 59, 45, 59, 60, 55, 49, 67, 54, 65, 60, 67, 55, 71, 64, 73, 66, 67, 61, 87, 63, 71, 78, 73, 74, 83, 69, 83, 78, 87, 73

Offset: 1

Labos Elemer, Jan 14 2000

nonn

			If n is prime then the iteration sequence is {p,2} and the sum is p+2. If n=30, then iterations of the d function are {30,8,4,3,2} and their sum is a(30)=47.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A000005, A036452, A036453, A036454, A036455, A036459.

f:= proc(n) option remember;
  if n <= 2 then n
  else n + procname(numtheory:-tau(n));
  fi
end proc:
map(f, [$1..80]); # Robert Israel, Nov 14 2016

g[n_] := DivisorSigma[0, n]; f[n_] := Plus @@ Drop[ FixedPointList[g, n], -1]; Table[ f[n], {n, 71}] (* Robert G. Wilson v, Dec 16 2004 *)

A174457 Infinitely refactorable numbers: numbers k such that each iteration under the map x -> A000005(x) produces a divisor of k.

Original entry on oeis.org

1, 2, 12, 24, 36, 60, 72, 84, 96, 108, 132, 156, 180, 204, 228, 240, 252, 276, 288, 348, 360, 372, 396, 444, 468, 480, 492, 504, 516, 564, 600, 612, 636, 640, 672, 684, 708, 720, 732, 792, 804, 828, 852, 864, 876, 936, 948, 972, 996, 1044, 1056, 1068, 1116, 1152

Offset: 1

Matthew Vandermast, Dec 04 2010

nonn

In other words, let d^1(n) = A000005(n) and, for all positive integers k, let d^(k+1)(n) = A000005(d^k(n)). Sequence lists numbers n with the property that every such value of d^k(n) divides n.
A141586 is a subsequence. Is A110821 a subsequence?
Not a subsequence of A141551: 504 is the smallest term in this sequence not member of A141551.
a(n) is even for all n, since for any n >= 2, d^k(n) = 2 for some k. Proof: {d^k(n)} is a nonincreasing sequence of k, so it must stablize at a fixed point of the map x -> A000005(x), namely x = 1 or 2. But d^k(n) = 1 for some k implies that n = 1. - Jianing Song, Apr 20 2022

			9 has 3 divisors, and 9 is a multiple of 3. But 3 has 2 divisors, and 9 is not a multiple of 2. Hence, 9 does not belong to this sequence.
36 has 9 divisors, 9 has 3 divisors, 3 has 2 divisors, and 9, 3, and 2 are all divisors of 36. (Since 2 has 2 divisors, all further steps produce a value of 2.) Hence, 36 belongs to this sequence.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A036459 (number of steps of the map), A000005 (d(n): number of divisors).
Cf. A010553 (d(d(n))), A036450 (d^3(n)), A036452 (d^4(n)), A036453 (d^5(n)).
Subsequence of A033950 (refactorable numbers: d(n) | n) and A141113 (d(d(n))| n).

is_A174457(n, d=n)=!until(d<3, n%(d=numdiv(d)) && return) \\ M. F. Hasler, Dec 05 2010, updated PARI syntax Apr 16 2022

Edited by M. F. Hasler, Apr 16 2022

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

A036450 a(n) = d(d(d(n))), the 3rd iterate of the number-of-divisors function with an initial value of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

A036453 a(n) = d(d(d(d(d(n))))), the 5th iterate of the number-of-divisors function d = A000005, with initial value n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A036454 Prime powers with special exponents: q^(p-1) where p > 2 and q are prime numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Formula

A036455 Numbers n such that d(d(n)) is an odd prime, where d(k) is the number of divisors of k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A036457 Numbers k for which exactly 5 applications of A000005 are needed to reach 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple