19
\$\begingroup\$

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 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 , shortest wins!

\$\endgroup\$
6
  • 7
    \$\begingroup\$ An interesting variant of this would be to have the ratio grow arbitrarily small. \$\endgroup\$
    – Wheat Wizard
    Commented Dec 27, 2023 at 14:30
  • \$\begingroup\$ Why not just allow any n-indexing(=allow a finite amount of failure)? \$\endgroup\$
    – l4m2
    Commented Dec 27, 2023 at 14:32
  • \$\begingroup\$ @l4m2 0-indexing and 1-indexing are standard, and I've decided to allow 2-indexing for this challenge because of the n=1 edgecase in most approaches. \$\endgroup\$
    – emanresu A
    Commented Dec 27, 2023 at 14:33
  • 2
    \$\begingroup\$ If every integer occurs infinitely many times, than all integers occur the same number of times. None occurs more often than the rest. \$\endgroup\$
    – Purple P
    Commented Dec 28, 2023 at 17:30
  • 2
    \$\begingroup\$ @PurpleP No. This question specifically uses a definition of proportionality used in number theory, which makes sense and can be a value other than 1 even when both occurs infinitely often. \$\endgroup\$
    – Trebor
    Commented Dec 29, 2023 at 5:24

9 Answers 9

15
\$\begingroup\$

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.

\$\endgroup\$
10
  • \$\begingroup\$ The link is broken. \$\endgroup\$
    – Simd
    Commented Dec 27, 2023 at 15:10
  • 1
    \$\begingroup\$ An integer is "\$k\$-powerful" (or "\$k\$-full") if all of the exponents in its prime-power factorization are at least \$k\$; we can call an integer "exactly \$k\$-powerful" if it is \$k\$-powerful but not \$(k+1)\$-powerful. It's a 1934 theorem of Erdős and Szekeres that the number of \$k\$-powerful integers up to \$x\$ is asymptotic to a constant times \$x^{1/k}\$, which implies the same result for exactly \$k\$-powerful integers. This argument justifies the correctness of this answer. \$\endgroup\$ Commented Dec 28, 2023 at 2:58
  • \$\begingroup\$ By the way, if the minimum of the list can be changed to the gcd of the list with another character, then the integers yielding an output of \$k\$ are exactly the \$k\$th powers (that aren't higher powers), which simplifies the proof of correctness substantially. \$\endgroup\$ Commented Dec 28, 2023 at 3:01
  • \$\begingroup\$ @GregMartin I don't see how the result on \$k\$-powerful integers helps, because a lower bound isn't hard regardless, and this doesn't directly apply to an upper bound, because \$18 = 2 \cdot 3^2 \$ still returns 2, for example. \$\endgroup\$ Commented Dec 28, 2023 at 3:21
  • \$\begingroup\$ Sorry—I misread the function as returning the smallest prime exponent, which is a valid answer to the challenge and to which my argument applies. \$\endgroup\$ Commented Dec 28, 2023 at 3:24
7
\$\begingroup\$

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.
\$\endgroup\$
0
5
\$\begingroup\$

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!

\$\endgroup\$
6
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

Charcoal, 35 bytes

Nθ⊞υ¹W›θΣυ«≧⁻Συθ⊞υ×⌈υLυ»I⊕ΣEυ›θΣ✂υκ

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

Nθ

Input n.

⊞υ¹

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

W›θΣυ«

While more terms are needed, ...

≧⁻Συθ

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

⊞υ×⌈υLυ

generate a new set of terms.

»I⊕ΣEυ›θΣ✂υκ

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.

\$\endgroup\$
1
  • \$\begingroup\$ Interestingly, I believe if each group were reversed, it would not count as a solution. \$\endgroup\$
    – Tbw
    Commented Dec 27, 2023 at 21:14
2
\$\begingroup\$

JavaScript (Node.js), 27 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

C (gcc), 39 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ -1 byte, I think (I don't speak Scala). \$\endgroup\$
    – pajonk
    Commented Dec 28, 2023 at 6:52
0
\$\begingroup\$

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
 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.

\$\endgroup\$
1
  • \$\begingroup\$ check int with ⍵≠⌊⍵ \$\endgroup\$
    – att
    Commented Dec 29, 2023 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.