A211668 Number of iterations sqrt(sqrt(sqrt(...(n)...))) such that the result is < 3.

0, 0, 1, 1, 1, 1, 1, 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, 3, 3, 3, 3, 3, 3

Offset: 1

Author

Hieronymus Fischer, Apr 30 2012

Keywords

• base
• nonn

Comments

For the general case of "Number of iterations f(f(f(...(n)...))) such that the result is < q, where f(x) = x^(1/p), p > 1, q > 1", the resulting g.f. is g(x) = 1/(1-x)*Sum_{k>=0} x^(q^(p^k))

= (x^q + x^(q^p) + x^(q^(p^2)) + x^(q^(p^3)) + ...)/(1-x).

Examples

			a(n) = 1, 2, 3, 4, 5 for n = 3^1, 3^2, 3^4, 3^8, 3^16, i.e., n = 3, 9, 81, 6561, 43946721.
		

Crossrefs

Cf. A001069, A010096, A211662, A211666, A211670.

Programs

Mathematica

a[n_] := Length[NestWhileList[Sqrt, n, # >= 3 &]] - 1; Array[a, 100] (* Amiram Eldar, Dec 08 2018 *)

PARI

a(n) = {my(nbi = 0); if (n < 3, return (nbi)); r = n; nbi= 1; while ((nr = sqrt(r)) >= 3, nbi++; r = nr); return (nbi);} \\ Michel Marcus, Oct 23 2014

PARI

A211668(n, c=0)={while(n>=3, n=sqrtint(n); c++); c} \\ M. F. Hasler, Dec 07 2018

Python

from sympy import integer_log
A048766=lambda n: integer_log(n,3)[0].bit_length() # Natalia L. Skirrow, May 17 2023

Formula

a(3^(2^n)) = a(3^(2^(n-1))) + 1, for n >= 1.

G.f.: g(x) = 1/(1-x)*Sum_{k >= 0} x^(3^(2^k))

= (x^3 + x^9 + x^81 + x^6561 + x^43946721 + ...)/(1 - x).

Extensions

Edited by Michel Marcus, Oct 23 2014 and M. F. Hasler, Dec 07 2018