[Question]
  [
In this challenge, an *infinitely proportional sequence* is defined as a infinite sequence of positive integers such that:
* All positive integers are contained infinitely many times within the sequence.
* As more and more terms are added to the sequence, for all positive integers \$n\$, the ratio of the number of \$n\$s to the number of \$n+1\$s in the sequence must grow arbitrarily large.
An example of such a sequence is the following function taking an index and returning a value:
$$
S(n)=\begin{cases}S(\sqrt{n})+1 & n \text{ is perfect square > 1} \\ 1 & \text{otherwise} \end{cases}
$$
This results in a sequence `[1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 3 ...`, and it's fairly easy to see why this list satisfies the given properties. The first 4 occurs at index \$2^8 = 256\$, the first 5 at index \$2^{16} = 65536\$, and so on, with each positive integer occuring infinitely many more times than the previous.
An example of an invalid sequence is this:
$$
S(n)=\begin{cases}S(\frac{n}{2})+1 & n \text{ is even} \\ 1 & \text{otherwise} \end{cases}
$$
This sequence goes `[1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, ...]`, and while it does contain every positive integer infinitely many times, and contains each positive integer more than the previous, it does not contain each integer infinitely many more than the previous. In the limiting case, the sequence contains twice as many 1s as 2s, twice as many 2s as 3s, and so on.
Your challenge is to output any infinitely proportional sequence. Standard [sequence](/questions/tagged/sequence "show questions tagged 'sequence'") rules apply - you may output as a function that takes \$n\$ and outputs the \$n\$th or first \$n\$ terms, or output an infinite sequence in some form. You may use 0-indexing, 1-indexing or 2-indexing (taking the first term as f(2))
This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), shortest wins!
  
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 2 bytes
```
√ìŒ∏
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m73MwDQxyTB1wQZDAwNXPzt7JQVdOwUlez-7paUlaboWSw5PPrdjSXFScvFCHYjIggUQGgA)
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](http://www.numdam.org/item/JTNB_1993__5_2_411_0.pdf), 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](https://github.com/Adriandmen/05AB1E), 2 bytes, thanks to @GregMartin
```
√ì¬ø
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m73MwDQxyTB1wQZDAwNXPzt7JQVdOwUlez-7paUlaboWSw5PPrR_SXFScvFCHYjIggUQGgA)
Returns the gcd of the prime exponents, which is the largest \$k\$ such that \$n\$ is a \$k\$-th power.
[Answer]
# [Haskell](https://www.haskell.org) + [hgl](https://gitlab.com/wheatwizard/haskell-golfing-library), 10 bytes
```
nM l<gr<bi
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m708I7E4OzUnZ8FN3czcgvyiEoXC0sSczLTM1BSFgKLUnNKUVC6oRABXmpWVZ16Jrh2QWFpakqZrsSbNNs9XIccmvcgmKRMitDU3MTPPNjdeoaBIJc0m2lBPz9DAIBYit2ABhAYA)
## 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.
[Answer]
# [Python](https://www.python.org), 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!](https://ato.pxeger.com/run?1=m72soLIkIz9vwYKlpSVpuhY3VdJscxJzk1ISFfKsdPPU8mzyFPKLdOvSNHJS8zSSMvM08jQ1NaFqlQqKMvNKNKLTNDI10_KLFDIVMvMUihLz0lM1DHWMTM01Y6EqYaYDAA)
**[39 bytes](https://ato.pxeger.com/run?1=m72soLIkIz9vwYKlpSVpuhY31dNscxJzk1ISFfKs8tTydA0T81IUDPOLdOvSNHJS8zSSMvM08jQ1NaHKlQqKMvNKNKLTNDI10_KLFDIVMvMUihLz0lM1DHWMTM01Y6EqYRYAAA) 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](https://www.python.org), 36 bytes
*suggested by Wheat Wizard*
```
lambda n:len(min(bin(n).split("1")))
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m72soLIkIz9vweI025ilpSVpuhY3VXISc5NSEhXyrHJS8zRyM_M0koA4T1OvuCAns0RDyVBJU1MTqla5oCgzr0QjOk0jUzMtv0ghUyEzT6EoMS89VcNQx9DAyFgzFqp0wQIIDQA)
[Answer]
# [R](https://www.r-project.org), 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!](https://ato.pxeger.com/run?1=m72waMGiNNulpSVpuhY3FdJsYzTydDJt8-L0TDUTMtMSNDJVVQ11DHXSNDI1tQ01oerU0jSMTM00uYpTS_wSc1OLNYoTCwpyKjWMrAwNgGo1dcAMqOoFCyA0AA)
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 35 bytes
```
ÔºÆŒ∏‚äûœÖ¬πÔº∑‚Ä∫Œ∏Œ£œÖ¬´‚âß‚ÅªŒ£œÖŒ∏‚äûœÖ√ó‚åàœÖÔº¨œÖ¬ªÔº©‚äïŒ£Ôº•œÖ‚Ä∫Œ∏Œ£‚úÇœÖŒ∫
```
[Try it online!](https://tio.run/##Xc7NCsIwDAfws32KHlOYsJ13Eg8ycDKcL1BrWIttnf1QQXz2usp2MaeQf/glQnInblyn1NgxhkM0Z3RwZzXpopcQC1pN/VMqjRR2DnnIcUH7aCAyxuibrFo@brxXgz2qQQZolY1@2ShotlYLdlIGPbT8pcwc79EOQf6smnxI55QNsOU@QGOFQ4M24AUyNp3JxN8TvVYC8/zK5qpTqsqyTOuH/gI "Charcoal ‚Äì Try It Online") Link is to verbose version of code. Outputs the `n`th 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.
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), 27 bytes
```
S=n=>++n**.5%1?1:S(n**.5)+1
```
[Try it online!](https://tio.run/##HchRCoAgDADQ0wSbq2Af/STaITxBlMYiXFh0faP@Hm@fn/laipx3l3WNtQaXnSfKxvRDwxOPAX4jcU1aQBxbSyQoCQIIesZF86VH7A/dQNovsb4 "JavaScript (Node.js) ‚Äì Try It Online")
[Answer]
# [C (gcc)](https://gcc.gnu.org/), 39 bytes
```
i;f(n){i=sqrt(n);n=i*i-n||1/n?:f(i)+1;}
```
[Try it online!](https://tio.run/##bVDbTsMwDH3fV1iVJiVto9FNPEAoPCC@gvahSpMRsWUjiURF118nuFeYRORY9rF95GPB9kKEoLkihrY6dx/WY8RNrmPNzOWSbczTvSKaJhnvgjYejpU2hEK7Anw9IJuzFF7WryXk0GYpjLadg3/T0XYdH2jEW2Vj9FK8S4s80DNFRfOyLZq7Z/y3UQp/8100TaqTBdJvoU0tGxy74VP4AE5/yZMi8350MwHxgnBIkqF71jNr8sg00iSQ8auSw5Iinl6jEtHlEMNk@dtwttiiSLSugT0C@rUrDCryKbh0kY0UObhyIu5WXfgW6lDtXWCfgR2OPw "C (gcc) ‚Äì Try It Online")
[Answer]
# [Scala 3](https://www.scala-lang.org/), ~~64~~ 63 bytes
A port of [@pajonk's R answer](https://codegolf.stackexchange.com/a/268808/110802) 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!](https://ato.pxeger.com/run?1=NY9BTsMwEEX3PcWoEpItlLSGDUqVoCI2SHSFWFUVclKnNXLGwZ5Ao6onYdMNbLgD9-ht6oSwmvme_7-eP799IY28_lmOI7Qf0uF4dZrZ_FUVBAupEfYjgLUqoQqCSbfxCcydk-3yiZzGzYon8IyaIO2d8NVQGd2cbrtIyTC5t01uFE8ekNL9uzSg00rSNvZvjhjymS6ZvhDZlAtQxquQ0fxSHIaa39AIkwnM69q0QNtwb7AgbRHI9hqbKlfOQ-lsBVfdq5gKkLiGOuBR73HKN4Z8hwcdwqADMvtP8LiSNUNIM0CIsg49JjvA87AuZN3n-1aDbOgIl0ftKfbW0V3Ldmm2i18E58F7GA2_OB7_5hk)
[Answer]
# [APL(Dyalog Unicode)](https://dyalog.com), 16 bytes [SBCS](https://github.com/abrudz/SBCS)
```
{‚çµ‚â†‚åä‚çµ:0‚ãÑ1+‚àá‚çµ*.5}
```
[Try it on APLgolf!](https://razetime.github.io/APLgolf/?h=AwA&c=q37Uu/VR54JHPV1AhpXBo@4WQ@1HHe1AjpaeaS0A&f=K0ktLil@1DbBUPtR72YTS64SEF8nWs80Nu3QCjAHAA&i=AwA&r=tryapl&l=apl-dyalog-extended&m=train&n=f)
-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
 0‚â†               ‚çù ‚Äé‚Å¢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](https://vyxal.github.io/Luminespire).
]