APL(Dyalog Unicode), 16 bytes ^SBCS

{⍵≠⌊⍵:0⋄1+∇⍵*.5}

Try it on APLgolf!

-1 byte thanks to att.

A tacit function which takes an integer \$n\geq 2\$ on the right and outputs the \$n\$th term in the sequence in the question.

{⍵≠⌊⍵:0⋄1+∇⍵*.5}­⁡​‎‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢‏⁠‎⁡⁠⁣‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢‏⁠‎⁡⁠⁣‏⁠‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁣⁡‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁤⁡‏⁠‎⁡⁠⁤⁢‏⁠‎⁡⁠⁤⁣‏⁠‎⁡⁠⁤⁤‏‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁣⁤‏‏​⁡⁠⁡‌⁢⁤​‎⁠‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏‏​⁡⁠⁡‌­
   ⌊⍵             ⍝ floor ‎⁡input
 ⍵≠               ⍝ ‎⁢not input
 ⍵≠⌊⍵:            ⍝ ‎⁣If input is non-integer:
      0           ⍝ ‎⁤    return 0
       ⋄          ⍝ ‎⁢⁡Else:
           ⍵*.5   ⍝ ‎⁢⁢sqrt input
          ∇       ⍝ ‎⁢⁣apply this dfn 
        1+        ⍝ ‎⁢⁤add 1
💎

Created with the help of Luminespire.

Python, 36 bytes

-6 bytes thanks to l4m2, Command Master and xnor

f=lambda n:-n&n<n or-~f(len(bin(n)))

Attempt This Online!

39 bytes if using True as 1 is not allowed:

f=lambda n:n&n-1and 1or-~f(len(bin(n)))

Similar to example but with logarithm base 2 instead of square root.

I known that len(bin(n)) is not exactly the logarithm, but it does not make a difference for the purpose of this challenge

Python, 36 bytes

suggested by Wheat Wizard

lambda n:len(min(bin(n).split("1")))

Attempt This Online!

Scala 3, 64 63 bytes

A port of @pajonk's R answer in Scala.

Saved 1 byte(s) thanks to the comment of @pajonk

def f(n:Double):Int={val i=math.sqrt(n);if(i%1>0)1 else f(i)+1}

Attempt This Online!

05AB1E, 2 bytes

Óθ

Attempt This Online!

Returns the exponent of the largest prime factor of \$n\$.

Proof of correctness

Let's look at the ratio between the number of values which return \$k\$ and the number which return \$k + 1\$. For each number which gives \$k+1\$, with greater prime factor \$p_m\$, we can create \$m-1\$ new numbers, by dividing by \$p_m\$ and multiplying by \$p_i\$ for \$i < m\$. However, some numbers are generated multiple times, but it's bounded by their number of distinct prime divisors. If we look at numbers up to \$n\$, that's bounded by \$O(\frac{\log(n)}{\log\log(n)})\$. Therefore we have \$\sum_{p_m} \frac{(m-1)\log\log(n)}{\log(n)} \Psi(\frac n{p_m^{k+1}}, p_m-1) \leq \sum_{p_m} \Psi(\frac n{p_m^k}, p_m-1)\$. We want to show that for every \$N\$, for large enough \$n\$, we have \$ N \sum_{p_m} \Psi(\frac n{p_m^{k+1}}, p_m-1) \leq \sum_{p_m} \frac{(m-1)\log\log(n)}{\log(n)} \Psi(\frac n{p_m^{k+1}}, p_m-1)\$. We'll split it at \$m = 2N \log(n)\$. From theorem 1.4 in Integers without large prime factors, we have \$\Psi(n, p_m) = n^{O_N(\frac 1{\log\log n})}\$. The inequality is trivial for \$m > 2N \log(n)\$, and because \$\sum_{p_m} \Psi(\frac n{p_m^{k+1}}, p_m-1) = \Omega(\frac{n^{k+1}}{\log(n)})\$ grows faster than \$n^{O_N(\frac 1{\log\log n})}\$ the fact that we used \$2N\$ balances the terms we split out.

05AB1E, 2 bytes, thanks to @GregMartin

Ó¿

Attempt This Online!

Returns the gcd of the prime exponents, which is the largest \$k\$ such that \$n\$ is a \$k\$-th power.

Haskell + hgl, 10 bytes

nM l<gr<bi

Attempt This Online!

Explanation

• bi convert the input to binary
• gr group equal elements
• nM l length of the shortest group

This finds the shortest run of equal elements in the binary expansion of the input.

Proof

I will provide a proof that the proportion of 1s approaches 1. That is \$P(f(x)=1)=1\$ This argument can be repurposed to show that for any number the proportion relative to numbers greater than or equal to it approaches 1. That is \$P(f(x)=n\mid f(x)\geq n)=1\$.

Let's consider the two least significant bits of a number \$x\$. If they are 10 or 01 then \$f(x)=1\$.

The two other options 11 and 00 may be any value. This means that at least half of all numbers give 1.

Now in the general case, let us treat the case where the least significant \$2n\$ bits do not rule out values other than 1. Considering the least significant \$2n+2\$ bits. A fourth of all cases of begin with 010 or 101 and thus \$f(x)=1\$. So 3/4 of all cases have the possibility of being something other than 1.

We can use recursion to then derive the following formula:

\$ P(f(x)\neq 1) \leq \frac{1}{2}\left(\frac34\right)^n \$

We can take the limit:

\$ \displaystyle P(f(x)\neq 1)\leq\frac{1}{2}\lim_{n\rightarrow\infty} \left(\frac{3}{4}\right)^n=0 \$

So the probability of getting a 1 converges to 1.

Reflection

There are a couple of things that would be nice here.

• There is sss which gives the shortest continuous substring satisfying a predicate, and sSn which gives the maximal substrings satisfying a predicate. Here it would have been useful to have a function which gives the shortest maximal substring satisfying a predicate.
• It might be nice to have a version of gr which just gives the lengths of the groups. It's not uncommon to care only about group lengths and not their contents.

Charcoal, 35 bytes

Ｎθ⊞υ¹Ｗ›θΣυ«≧⁻Συθ⊞υ×⌈υＬυ»Ｉ⊕ΣＥυ›θΣ✂υκ

Try it online! Link is to verbose version of code. Outputs the nth term. Explanation:

Ｎθ

Input n.

⊞υ¹

Start with 1 1 as the first term of the sequence.

Ｗ›θΣυ«

While more terms are needed, ...

≧⁻Συθ

... account for previous terms, and...

⊞υ×⌈υＬυ

generate a new set of terms.

»Ｉ⊕ΣＥυ›θΣ✂υκ

Calculate the resulting term.

The result is the following sequence:

1
1 2
1 1 2 3
1 1 1 1 1 1 2 2 3 4
1 (24 times) 2 2 2 2 2 2 3 3 4 5
1 (120 times) 2 (24 times) 3 3 3 3 3 3 4 4 5 6
1 (720 times) 2 (120 times) ...

Within each group, the number of times m-1 appears more than m is more than the number of times m-1 appeared more than n in the previous group.

R, 32 bytes

f=\(n,i=n^.5)`if`(i%%1,1,f(i)+1)

Uses the sequence from the question (2-indexed).

Attempt This Online!

C (gcc), 39 bytes

i;f(n){i=sqrt(n);n=i*i-n||1/n?:f(i)+1;}

Try it online!

JavaScript (Node.js), 27 bytes

S=n=>++n**.5%1?1:S(n**.5)+1

Try it online!