A036459 -id:A036459 - cp's OEIS frontend

A182859 Numbers n such that A036459(n) is even.

1, 2, 4, 9, 12, 16, 18, 20, 24, 25, 28, 30, 32, 40, 42, 44, 45, 48, 49, 50, 52, 54, 56, 63, 64, 66, 68, 70, 75, 76, 78, 80, 81, 88, 92, 98, 99, 102, 104, 105, 110, 112, 114, 116, 117, 121, 124, 128, 130, 135, 136, 138, 144, 147, 148, 152, 153, 154, 162, 164, 165, 169, 170

Offset: 1

Matthew Vandermast, Jan 05 2011

nonn

The sequence is also given by taking the smallest positive integer n such that A000005(n) is not already in the sequence. - Drake Thomas, May 05 2015

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

Complement of A080218.

A036459:= proc(n) option remember;
  procname(numtheory:-tau(n))+1;
end proc:
A036459(1):= 0: A036459(2):= 0:
select(t -> A036459(t)::even, [$1..1000]); # Robert Israel, Aug 31 2015

Position[Table[Length[FixedPointList[DivisorSigma[0, #] &, n]] - 2, {n, 170}], Integer?EvenQ] // Flatten (* _Michael De Vlieger, Aug 31 2015, after Robert G. Wilson v at A036459 *)

A251483 Position of first occurrence of n in A036459.

Original entry on oeis.org

1, 3, 4, 6, 12, 60, 5040, 293318625600, 635197862493622653217009501211465321419691071212633792891415680000000000

Offset: 0

Ivan Neretin, Mar 29 2015

nonn

			For n=7, a(7) = 293318625600 -> 5040 -> 60 -> 12 -> 6 -> 4 -> 3 -> 2.
For n=8, a(8) -> 1111523212800 -> 5040 -> 60 -> 12 -> 6 -> 4 -> 3 -> 2.

Coincides with A009287 for n <= 7 (only).

a036459(n) = {if (n<=2, return(0)); nb = 1; while ((nd = numdiv(n)) > 2, n = nd; nb++); nb;}
a(n) = {k = 1; while (a036459(k) != n, k++); k;} \\ Michel Marcus, Oct 28 2015

A066029 Incorrect version of A036459.

Original entry on oeis.org

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

Offset: 1

Joseph L. Pe, Dec 11 2001

dead

a(p) should be 1 instead of 0 when p is an odd prime.

A182850 a(n) = number of iterations that n requires to reach a fixed point under the x -> A181819(x) map.

Original entry on oeis.org

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

Offset: 1

Matthew Vandermast, Jan 04 2011

nonn

The fixed points of the x -> A181819(x) map are 1 and 2. Note that the x -> A000005(x) map has the same fixed points, and that A000005(n) = A181819(n) iff n is cubefree (cf. A004709). Under the x -> A181819(x) map, it seems significantly easier to generalize about which kinds of integers take a given number of iterations to reach a fixed point than under the x -> A000005(x) map.

Also the number of steps in the reduction of the multiset of prime factors of n wherein one repeatedly takes the multiset of multiplicities. For example, the a(90) = 5 steps are {2,3,3,5} -> {1,1,2} -> {1,2} -> {1,1} -> {2} -> {1}. - Gus Wiseman, May 13 2018

			A181819(6) = 4; A181819(4) = 3; A181819(3) = 2; A181819(2) = 2. Therefore, a(6) = 3, a(4) = 2, a(3)= 1, and a(2) = 0.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Fixed Point
Eric Weisstein's World of Mathematics, Map

A182857 gives values of n where a(n) increases to a record.

Cf. A000961, A001222, A003434, A005117, A007916, A036459, A112798, A130091, A181819, A182851-A182858, A238748, A304455, A304464, A304465.

a182850 n = length $ takeWhile (`notElem` [1,2]) $ iterate a181819 n
-- Reinhard Zumkeller, Mar 26 2012

Table[If[n<=2,0,Length[FixedPointList[Sort[Length/@Split[#]]&,Sort[Last/@FactorInteger[n]]]]-1],{n,100}] (* Gus Wiseman, May 13 2018 *)

;; With memoization-macro definec.
(definec (A182850 n) (if (<= n 2) 0 (+ 1 (A182850 (A181819 n))))) ;; Antti Karttunen, Feb 05 2016

For n > 2, a(n) = a(A181819(n)) + 1.
a(n) = 0 iff n equals 1 or 2.
a(n) = 1 iff n is an odd prime (A000040(n) for n>1).
a(n) = 2 iff n is a composite perfect prime power (A025475(n) for n>1).
a(n) = 3 iff n is a squarefree composite integer or a power of a squarefree composite integer (cf. A182853).
a(n) = 4 iff n's prime signature a) contains at least two distinct numbers, and b) contains no number that occurs less often than any other number (cf. A182854).

A053475 1 + the number of iterations of A051953 (Euler-cototient) function needed to reach 0, starting at n.

Original entry on oeis.org

2, 3, 3, 4, 3, 5, 3, 5, 4, 6, 3, 6, 3, 6, 4, 6, 3, 7, 3, 7, 5, 7, 3, 7, 4, 7, 5, 7, 3, 8, 3, 7, 4, 8, 4, 8, 3, 8, 5, 8, 3, 9, 3, 8, 6, 8, 3, 8, 4, 9, 4, 8, 3, 9, 5, 8, 6, 9, 3, 9, 3, 8, 6, 8, 4, 9, 3, 9, 5, 9, 3, 9, 3, 9, 5, 9, 4, 10, 3, 9, 6, 10, 3, 10, 6, 9, 4, 9, 3, 10, 4, 9, 5, 9, 4, 9, 3, 9, 6, 10, 3, 10

Offset: 1

Labos Elemer, Jan 14 2000

nonn

Analogous sequences of iteration-lengths for A000005 or A000010 are A036459 and A049108 resp. The length values of 3 occur if the initial value is prime resulting in {p,1,0} iterations.

			Starting with n=18, the iterations of A051953 are as follows: {18,12,8,4,2,1,0}. The length of this sequence is 7, so a(18) = 7. The function is applied a(n)-1 times.

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

Cf. A000005, A000010, A051953, A036459, A049108, A076640.

Table[Length@ NestWhileList[# - EulerPhi@ # &, n, # > 0 &], {n, 84}] (* Michael De Vlieger, Jul 04 2016 *)

a(n) = A076640(n) + 1. - Michael De Vlieger, Jul 04 2016

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

A060937 Number of iterations of d(n) (A000005) needed to reach 2 starting at n (n is counted).

Original entry on oeis.org

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

Offset: 2

Ahmed Fares (ahmedfares(AT)my-deja.com), May 06 2001

nonn

By the definition of a(n) we have for n >= 3 the recursion a(n) = a(d(n)) + 1. a(n) = 2 iff n is an odd prime.

			If n=12 the trajectory is {12,6,4,3,2}. Its length is 5, thus a(12)=5.

József Sándor, Dragoslav S. Mitrinovic, Borislav Crstici, Handbook of Number Theory I, Springer Science & Business Media, 2005, chapter 2, page 66.

Charles R Greathouse IV, Table of n, a(n) for n = 2..10000
Paul Erdős and Imre Kátai, On the growth of d_k(n), Fibonacci Quarterly, Vol. 7, No. 3 (1969), pp. 267-274.

Equals A036459 + 1.

Cf. A000005, A049108, A003434.

with(numtheory): interface(quiet=true): for n from 2 to 200 do if (1=1) then temp := n: count := 1: end if; while (temp > 2) do temp := tau(temp): count := count + 1: od; printf("%d,", count); od;

a[n_] := -1 + Length @ FixedPointList[DivisorSigma[0, #] &, n]; Array[a, 100, 2] (* Amiram Eldar, Jul 10 2021 *)

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

0 < lim sup_{n->oo} (a(n)-1)/log(log(log(n))) < oo (Erdős and Kátai, 1969). - Amiram Eldar, Jul 10 2021

More terms from Winston C. Yang (winston(AT)cs.wisc.edu), May 21 2001

A080218 Monotonically increasing sequence such that every positive integer n appears if and only if d(n) doesn't (d(n)=number of divisors of n, A000005).

Original entry on oeis.org

3, 5, 6, 7, 8, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 27, 29, 31, 33, 34, 35, 36, 37, 38, 39, 41, 43, 46, 47, 51, 53, 55, 57, 58, 59, 60, 61, 62, 65, 67, 69, 71, 72, 73, 74, 77, 79, 82, 83, 84, 85, 86, 87, 89, 90, 91, 93, 94, 95, 96, 97, 100, 101, 103, 106, 107, 108, 109

Offset: 1

Matthew Vandermast, Mar 16 2003

			d(1)=1 and d(2)=2; therefore neither are included. Members include 3 (2 divisors), 6 (4 divisors) and 60 (12 divisors); other nonmembers include 4 (3 divisors), 12 (6 divisors) and 5040 (60 divisors).

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 840.

Robert Israel, Table of n, a(n) for n = 1..10000
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].

Cf. A182859.

A036459:= proc(n) option remember;
  procname(numtheory:-tau(n))+1;
end proc:
A036459(1):= 0: A036459(2):= 0:
select(t -> A036459(t)::odd, [$1..1000]); # Robert Israel, Aug 31 2015

a = {}; Do[Which[DivisorSigma[0, k] == k, 0, MemberQ[a, DivisorSigma[0, k]], 0, True, AppendTo[a, k]], {k, 109}]; a (* Michael De Vlieger, Aug 31 2015 *)

A185816 Number of iterations of lambda(n) needed to reach 1.

Original entry on oeis.org

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

Offset: 1

Michel Lagneau, Feb 05 2011

nonn

lambda(n) is the Carmichael lambda function, A002322.

a(n) = (length of row n in table A246700) - 1. - Reinhard Zumkeller, Sep 02 2014

			If n = 23 the trajectory is 23, 22, 10, 4, 2, 1. Its length is 6, thus a(23) = 5.

T. D. Noe, Table of n, a(n) for n = 1..10000
Paul Erdős, Andrew Granville, Carl Pomerance, and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204.
Paul Erdős, Andrew Granville, Carl Pomerance, and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204. [Annotated copy with A-numbers]
Paul Erdős, A. Granville, C. Pomerance, and C. Spiro, On the Normal Behavior of the Iterates of some Arithmetic Functions, in Analytic number theory (Allerton Park, IL, 1989), Progr. Math., 85 Birkhäuser Boston, Boston, MA, (1990), 165-204.
Nick Harland, The iterated Carmichael lambda function, arXiv:1111.3667v1 [math.NT], Nov 15, 2011.
Nick Harland, The number of iterates of the Carmichael lambda function required to reach 1, arXiv:1203.4791 [math.NT], Mar 21, 2012.

Cf. A002322, A036459, A003434.

Cf. A027763, A173927, A246700.

a185816 n = if n == 1 then 0 else a185816 (a002322 n) + 1
-- Reinhard Zumkeller, Sep 02 2014

a:= n-> `if`(n=1, 0, 1+a(numtheory[lambda](n))):
seq(a(n), n=1..100);  # Alois P. Heinz, Apr 27 2019

f[n_] := Length[ NestWhileList[ CarmichaelLambda, n, Unequal, 2]] - 2; Table[f[n], {n, 1, 120}]

For n > 1: a(n) = a(A002322(n)) + 1. - Reinhard Zumkeller, Sep 02 2014

cp's OEIS Frontend

A182859 Numbers n such that A036459(n) is even.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A251483 Position of first occurrence of n in A036459.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

A066029 Incorrect version of A036459.

Views

Author

Keywords

Comments

A182850 a(n) = number of iterations that n requires to reach a fixed point under the x -> A181819(x) map.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Scheme

Formula

A053475 1 + the number of iterations of A051953 (Euler-cototient) function needed to reach 0, starting at n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

A060937 Number of iterations of d(n) (A000005) needed to reach 2 starting at n (n is counted).