7
\$\begingroup\$

In one of this question's bonuses I asked you to design a permutation on the natural numbers such that the probability of a random term being odd was \$1\$. Now let's kick it up a notch. I want you to design and implement a permutation, \$f\$, on the natural numbers such that, for every integer \$n\$ greater than 0, the probability on \$f\$ of a member being divisible by \$n\$ is \$1\$.

Definition of Probability

To avoid confusion or ambiguity I am going to clearly lay out what is meant by probability in this question. This is adapted directly from my original question.

Let us say we have a function \$f\$ and a predicate \$P\$. The probability of a number fulfilling \$P\$ will be defined as the limit of the number of members of \$f\{1..n\}\$ fulfilling the predicate \$P\$ divided by \$n\$.

Here it is in a nice Latex formula

$$ \lim_{n\to\infty} \dfrac{\left|\left\{x : x\in \left\{1\dots n\right\}\right\},P(f(x))\right|}{n} $$


In order to have a probability of something being \$1\$ you don't need every member to satisfy the predicate, you just need the ones that don't to get farther apart the bigger they are.

This is so answers will be scored in bytes with less bytes being better.

You may take the natural numbers to either include or exclude 0. Both are fine.

\$\endgroup\$
0

1 Answer 1

3
\$\begingroup\$

Husk, 11 bytes

!uΣz:NCNmΠN

Try it online! Or showing the stats for the first 100 n in the first 5000 terms

Explanation

        mΠ     Map factorial over 
          N    the Natural numbers
      CN       Cut into lists of lengths corresponding to the natural numbers
   z:N         ZipWith append the natural numbers and ^
  Σ            Concatenate into one list
 u             Remove duplicates
!              Index

Proof (Without the u)

For triangle numbers : f(½n*(n+1))=n

Otherwise : f(n)=k! for some k.

As the density of triangular numbers is zero, this has the same probability as the sequence of factorials: 1

\$\endgroup\$
2
  • \$\begingroup\$ Thought that Π was a П (russian P) \$\endgroup\$
    – Stan Strum
    Sep 7, 2017 at 22:38
  • \$\begingroup\$ @StanStrum Nope Pi, as in product \$\endgroup\$
    – H.PWiz
    Sep 7, 2017 at 22:42

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.