45
\$\begingroup\$

Your task here will be to implement a function1 that forms a permutation on the positive integers (A bijection from the positive integers onto themselves). This means that each positive integer should appear exactly once in the permutation. The catch is your function should have a larger probability of outputting an odd number than an even number.

Now this may seem strange or impossible. Surely there are just as many odd numbers as even numbers? And while this intuition is correct for finite sets it actually does not hold for infinite sets. For example take the following permutation:

1 3 2 5 7 4 9 11 6 13 15 8 17 19 10 21 23 12 25 27 14 29 31 16 33 35 18 37 39 20 41 43 22 45 47 24 49 51 26 53 55 ...

If you take any subsection of the sequence with size greater than \$1\$ you will have at least as many odd numbers as even numbers, thus it seems that the probability of any random term being odd is greater than that of being even. You will also note every number odd or even number will eventually appear in the sequence and can only appear once. Thus the sequence is a true permutation.

Definition of Probability

To avoid confusion or ambiguity I am going to clearly lay out what is meant by probability in this question.

Let us say we have a function \$f\$. The probability of a number being odd will be defined as the limit of ratio odd members of the set to the size of the set \$f\{1\dots n\}\$ as \$n\$ tends towards infinity.

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

For example the aforementioned function would have a probability of being odd of \$2/3\$.


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


Extra Challenges

Here are some fun ideas to play around with and perhaps try to implement. These are just for fun and do not affect scoring in any way. Some of these are not even valid solutions to this challenge, and an answer which only includes solutions to challenges 2 or 3 is not a valid answer, and is liable to be deleted.

  • Write a permutation with an odd probability of \$1\$. (this is possible)

  • Write a permutation that has more odd numbers than even numbers in \$f\{1\dots n\}\$ for any \$n\$ but has a odd probability of \$1/2\$.

  • Write a permutation that has no defined probability (that is there is no limit).


1: Here function will mean program or function. It is just a piece of code that takes input and produces output.

\$\endgroup\$

22 Answers 22

22
\$\begingroup\$

Jelly, 7 bytes

Æf^<¥4P

Swaps 2s and 3s in the input's prime factorization. The probability of odds is 2/3.

Try it online!

How it works

Æf^<¥4P  Main link. Argument: n

Æf       Compute all prime factors of n, with duplicates.
    ¥4   Combine the two links to the left into a dyadic chain and call it with
         right argument 4.
   <       Compare each prime factor with 4. Yields 1 for 2 and 3, 0 otherwise.
  ^        Bitwise XOR the results with the corresponding prime factors.
         This maps 2 to 3, 3 to 2, and all other primes to themselves.
      P  Take the product of the resulting primes.
\$\endgroup\$
  • \$\begingroup\$ This answer is quite clever. I believe I understand why it works but you might want to include a proof that it works because I found it unintuitive at first. \$\endgroup\$ – Wheat Wizard Sep 2 '17 at 16:32
  • 6
    \$\begingroup\$ Proof that this is a permutation: the function is its own inverse. Proof of ratio: chance that an output is odd is the chance that the original had no factors 3, which is exactly when it's not divisible by three. That chance is 2/3. \$\endgroup\$ – tomsmeding Sep 3 '17 at 8:40
15
\$\begingroup\$

Husk, 11 10 bytes

-1 byte thanks to Leo, and a slightly different function

This has an odd probability of 1

!uΣz:NCNİ1

Try it online!

It indexes the sequence:

[1,2,3,5,7,9,11,4,13,15,17,19,21,23,25,27,29,6,31,33]
1 odd, 1 even, 5 odd, 1 even, 9 odd, 1 even, 13 odd...

Explanation

!               Index the following sequence (1-indexed)
 u              remove duplicates                     [1,2,3,5,7,9,11,4,13,15...]
  Σ              Concatenate                          [1,1,2,3,5,3,7,9,11,4,13..]
   z:            Zipwith append                       [[1,1],[2,3,5],[3,7,9,11]..
     N          Natural numbers
      CNİ1      Odd numbers cut into lists of lengths [[1],[3,5],[7,9,11]...]
                corresponding to the Natural numbers
\$\endgroup\$
8
\$\begingroup\$

Haskell, 35 34 32 bytes

f n=n:2*n+1:2*n+3:f(n+2)
(f 0!!)

Implements the example sequence [1,3,2,5,7,4,9,11,6,13,15,8,17,19,10,21,...].

Try it online!

For reference: old version, 34 bytes (-1 byte thanks to @xnor):

(!!)$do e<-[0,2..];[e,2*e+1,2*e+3]

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Save a paren: (!!)$do ... \$\endgroup\$ – xnor Sep 2 '17 at 1:24
8
\$\begingroup\$

Husk, 8 bytes

!uΣzeİ1N

Try it online!

This implements the example sequence (1,3,2,5,7,4...).

Explanation

!uΣzeİ1N
   ze       zip together
     İ1       the odd numbers
       N      with the natural (positive) numbers
  Σ         flatten the resulting list
 u          remove duplicates
!           index into the obtained sequence with the input
\$\endgroup\$
7
\$\begingroup\$

Everybody does Challenge 1, so let's do the other two.

Perl 6, 26 bytes — Challenge 2

{($_==1)+$_-(-1)**($_%%2)}

Try it online!

It's just 1 3 2 5 4 7 6... In an even number of terms, there are always 2 more odd numbers than even. In an odd number, 1 more. However this has clearly limit of (n+2)/(2n+2) -> ½.


Perl 6, 70 bytes — Challenge 3

{((1,),(2,4),->@a,@ {@(map(@a[*-1]+2*(*+1),^(4*@a)))}...*).flat[$_-1]}

Try it online!

Admittedly, this is horribly golfed. It indexes a sequence that contains 2⁰ odd numbers, then 2¹ even, then 2² odd, then 2³ even, and so on.

The probability after n such "blocks", if n is odd, is (2⁰+2²+2⁴+...+2ⁿ⁻¹)/(2ⁿ-1). The sum in the numerator is equal to ⅓(4½(n+1) - 1) = ⅓(2n+1 - 1). So the probability after odd number of blocks is ⅔ (in the limit).

If we add one more block (and strike an even count of them n+1), however, we didn't add any odd numbers (numerator stays the same) but there is now (2n+1 - 1) numbers in total. The parentheses cancel and we get the probability of ⅓ (in the limit).

This is apparently supposed to have 2 different cluster points, ⅓ and ⅔, to make sure that the limit doesn't exist, but this doesn't really prove it. My attempt to do a solid, rigorous proof can be found in this Math.SE answer: https://math.stackexchange.com/a/2416990/174637. Bashing mistakes is welcome.


Perl 6, 39 bytes — The core challenge.

{my$l=$_ div 3;$_%3??2*($_-$l)-1!!2*$l}

Try it online!

Though I posted this answer because of the challenges 2 and 3 which offered a pleasant little mathy puzzle, there is a strict requirement for all answers to contain a solution to the core challenge. Here it is then.

This is the example sequence.

\$\endgroup\$
  • 2
    \$\begingroup\$ These are extra challenges. For this to be a valid answer you must supply a solution to the core challenge. A solution to challenge 1 is also a solution to the core challenge, but a solution to challenges 2 or 3 is not. \$\endgroup\$ – Peter Taylor Sep 2 '17 at 7:23
  • 1
    \$\begingroup\$ Well, the extra challenges are what's interesting on this question for me. The core challenge is not. But I added some solution anyway. \$\endgroup\$ – Ramillies Sep 2 '17 at 11:34
  • \$\begingroup\$ I asked for a proof that your response to Challenge 3 has no limit in this Math.SE question: math.stackexchange.com/questions/2416053/… \$\endgroup\$ – Kevin - Reinstate Monica Sep 4 '17 at 5:05
  • \$\begingroup\$ @Kevin, thanks for asking. I think I may have confused you. I was quite sure it was OK. The only thing is that I often prove things quite rigorously for myself, just for the peace of mind (because your feet may slip quite easily, esp. when handling infinite objects like this) — and I haven't done it here. That's all what I wanted to say. \$\endgroup\$ – Ramillies Sep 4 '17 at 17:33
  • 1
    \$\begingroup\$ @Kevin — so after all, I overcame my laziness (a heroic deed!) and made the proof. I posted it as an answer to your Math.SE question. Hopefully it's OK (doing this kind of work at the night isn't really a good idea :—)). It turned out that it isn't nearly as horrible as I initially thought. \$\endgroup\$ – Ramillies Sep 4 '17 at 23:06
5
\$\begingroup\$

Brain-Flak, 120 bytes

(({})<{{({}[()]<({}(()[{}]))>)}{}({}[({})]<({}<>{}<({}())>)><>)}>)<>({}[()]){{}((<>{}<>[{}]){}[()])<>}{}{(({}){})<>{}}<>

Try it online!

Performs the following function:

function

This function generates the sequence

2 4 1 6 3 5 7 8 9 11 13 15 17 19 21 10 23 25 27 29...

The function has an odd probability of 1

\$\endgroup\$
4
\$\begingroup\$

R, 82 bytes (Extra challenge 1)

f<-function(n){if(sqrt(n)==floor(sqrt(n))){2*sqrt(n)}else{2*(n-floor(sqrt(n)))-1}}

Try it Online!

If the input is a perfect square, gives an even number. Otherwise, gives an odd number. The perfect squares have natural density 0, which means that this sequence gives odd numbers with probability 1.

\$\endgroup\$
  • \$\begingroup\$ Could you add a TIO link please? \$\endgroup\$ – H.PWiz Sep 1 '17 at 23:39
  • 1
    \$\begingroup\$ 58 bytes \$\endgroup\$ – Giuseppe Sep 6 '17 at 17:28
  • \$\begingroup\$ 56 bytes \$\endgroup\$ – Giuseppe Sep 26 '17 at 15:37
  • \$\begingroup\$ 53 bytes \$\endgroup\$ – Giuseppe Jan 24 '18 at 22:42
3
\$\begingroup\$

C (gcc), 29 bytes

f(n){return n&3?n+n/2|1:n/2;}

Try it online!

Every fourth number is even:

1 3 5   7 9 11   13 15 17   19 21 23   25 27 29
      2        4          6          8          10

Extra challenge 1, 52 bytes

f(n,i){for(i=0;n>>i/2;i+=2);return n&n-1?2*n-i-1:i;}

Try it online!

Returns 2*(x+1) if n equals 2x and consecutive odd numbers otherwise:

    1   3 5 7   9 11 13 15 17 19 21    23 25
2 4   6       8                     10      
\$\endgroup\$
3
\$\begingroup\$

Brain-Flak, 140 138 136 bytes

({}<(((()())()()))((<>[()])[()()])>){({}[()]<(({}(({}({}))[({}[{}])]))[({}[{}])]<>(({}(({}({}))[({}[{}])]))[({}[{}])])<>)>)}{}({}<{}{}>)

Try it online!

Explanation

This performs a similar function to the one suggested in the question.

2 3 1 4 7 5 6 11 9 8 15 13 10 17 15 ...

It works mostly based on a snippet I made to roll the stack for size 3 stacks.

(({}(({}({}))[({}[{}])]))[({}[{}])])

We set up two stacks one with accumulator values (two odd one even) and one with the numbers 4 4 2. Each iteration we roll both stacks and add the top of the left stack to the top of the right stack.

(({}(({}({}))[({}[{}])]))[({}[{}])]<>(({}(({}({}))[({}[{}])]))[({}[{}])])<>)

This will increment each odd number by 4 and the one even number by 2. As we loop through we get a pattern of 2 odd 1 even, with every positive integer being hit. Thus we just loop n times with n being the input. This has an asymptotic probability of 2/3.

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

Jelly, 10 bytes

ÆE;0ṭ2/FÆẸ

The probability of odds is 2/3.

Try it online!

How it works

ÆE;0ṭ2/FÆẸ  Main link. Argument: n

ÆE          Compute the exponents of n's prime factorization.
  ;0        Append a 0.
     2/     Reduce all pairs by...
    ṭ         tack, appending the left argument to the right one.
            This inverts all non-overlapping pairs of exponents.
       F    Flatten the result.
        ÆẸ  Consider the result a prime factorization and compute the corresponding
            integer.
\$\endgroup\$
1
\$\begingroup\$

C, 80 bytes

#define R if(k++==n)return
i,j,k;f(n){for(i=k=1,j=2;;i+=4,j+=2){R i;R i+2;R j;}}

Implementation of the example permutation from the question.

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Batch, 36 bytes

@cmd/cset/an=%1*2,(-~n*!!(n%%3)+n)/3

Implements the sequence given in the question.

\$\endgroup\$
1
\$\begingroup\$

JavaScript, 23 bytes

n=>n/2+n/2%2+(n%4&&n-1)

Output: 1, 3, 5, 2, 7, 9, 11, 4, 13, 15, 17, 6, 19, 21, 23, 8...

  • For all n = 4k:
    • f(n) = n/2 = 2k
  • For all n = 4k + b
    • f(n) = n/2 + b/2 + n - 1 = 3/2 * (4k + b) + 1/2 * b - 1 = 6k + 2b - 1

Challenge 2:

n=>n^(n>1)

Output: 1, 3, 2, 5, 4, 7, 6, 9, 8, 11, 10, 13, 12, 15, 14

\$\endgroup\$
  • \$\begingroup\$ n=>n%4?1.5*n|1:n/2 is 5 bytes shorter. \$\endgroup\$ – nwellnhof Sep 2 '17 at 16:01
1
\$\begingroup\$

CJam (21 bytes)

{2b_(&!\_,2*\1$~+2b?}

Online demo showing the first 32 outputs. This is an anonymous block (function).

This is also a solution to challenge 1: the numbers mapped to even numbers are the powers of 2, so the density of even numbers in the first n outputs is lg(n)/n which tends to zero.

Dissection

{         e# Declare a block; let's call the input x
  2b      e#   Convert to base 2
  _(&     e#   Copy, pull out first digit (1) and set intersection with rest
  !       e#   Boolean not, so empty set (i.e. power of 2) maps to 1 and non-empty
          e#   to 0
  \_,2*   e#   Take another copy, find its length, and double it
  \1$~+   e#   Take the original base 2 array and append ~(2L) = -2L-1
  2b      e#   Convert from base 2, to get 2x-2L-1
  ?       e#   Take the 2L if it was a power of 2, and the 2x-2L-1 otherwise
}
\$\endgroup\$
1
\$\begingroup\$

Perl 40 bytes

$,=$";$i=4;{say$i-3,$i/2,($i+=4)-5;redo}
\$\endgroup\$
1
\$\begingroup\$

Brain-Flueue, 88 bytes

({}<(((<>)[()])[()()])>)<>(((()())()()))<>{({})({})({})({}[()]<({}<>({})<>)>)}{}{}({}){}

Try it online!

Explanation

This implements the same function as my last answer but uses Brain-Flueue's FIFO model to cut some corners. Here are the first couple terms it generates.

2 3 1 4 7 5 6 11 9 8 15 13 10 17 15 ...

The first part of the code is just a bit of setup, we put 0,-1,-3 on the first stack and 2,4,4 on the second stack. The 2,4,4 will be used to cycle through even and odd numbers just as I did in my Brain-Flak answer.

We then loop n times, each time adding the top of the left stack to the right stack. Since Brain-Flueue uses queues as opposed to stacks the values naturally roll as we touch them preventing the need for extra code.

\$\endgroup\$
  • \$\begingroup\$ What is the difference between Flueue and Flak? \$\endgroup\$ – FantaC Jan 24 '18 at 22:16
  • \$\begingroup\$ @tfbninja Flueue uses a Queue instead of a stack. \$\endgroup\$ – Wheat Wizard Jan 24 '18 at 22:36
  • \$\begingroup\$ but...you're using the bflk interpreter... how do you make it different \$\endgroup\$ – FantaC Jan 25 '18 at 0:22
  • \$\begingroup\$ @tfbninja The -lflueue argument. \$\endgroup\$ – Wheat Wizard Jan 25 '18 at 3:15
0
\$\begingroup\$

Python 2, 46 104 55 bytes

lambda n:2*((n-int(n**.5))+.5,n**.5-1)[n!=1>0==n**.5%1]

Try it online!

Misread the question, now properly implemented a function that can be used to generate a sequence instead of one that generates a sequence. Also excluded 0 from the set of possible outputs.

Probability of finding an odd positive integer now converges to 1.

\$\endgroup\$
  • \$\begingroup\$ This should return an number, not a set / list as far as I understood \$\endgroup\$ – Mr. Xcoder Sep 1 '17 at 22:59
  • \$\begingroup\$ Also, this is not a correct permutation, since it contains 0. \$\endgroup\$ – Mr. Xcoder Sep 1 '17 at 23:05
  • \$\begingroup\$ @Mr.Xcoder Thanks for noticing. \$\endgroup\$ – Jonathan Frech Sep 2 '17 at 17:52
0
\$\begingroup\$

Jelly, 9 bytes

Ḥ€’ĖUẎQ⁸ị

Try it online!

Implements 1, 3, 2, 5, 7, 4, 9, 11, 6, ... (probability 2/3).

\$\endgroup\$
0
\$\begingroup\$

05AB1E, 11 bytes

·ÅÉā‚ø˜Ù¹<è

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Pyth, 9 bytes

*Fmxd<d4P

Try it here! or Test more in one go!

You can use this code to verify the ratio of odd numbers up to a certain point. Substitute 10000 with your desired limit (don't set it much higher, because it memory errors).

Km*Fmxk<k4PdS10000clf%T2KlK

Try it here.

The above gives roughly 0.667. The true probability of odd occurrences is 2/3. This approach is an equivalent implementation of Dennis' answer.


Explanation

*Fmxd<d4P   Full program.

        P   Prime factors.
  m         Map over ^.
   x        Bitwise XOR between:
    d          The current prime factor.
     <d4       The integer corresponding to the boolean value of current factor < 4.
*F          Product of the list.
\$\endgroup\$
0
\$\begingroup\$

Java 8, 20 bytes

n->n%4>0?n+n/2|1:n/2

Port of @nwellnhof's C answer.
Some things I tried myself ended up being a few bytes longer or slightly incorrect..

Implements: 1,3,5,2,7,9,11,4,13,15,17,6,19,21,23,8,25,27,29,10,31,33,35,12,37,...
with a probability of 3/4.

Try it here.

\$\endgroup\$
0
\$\begingroup\$

Lua, 67 53 bytes

Explanation coming when I'm done golfing this :)

This program takes an integer via command-line arguments as input and prints out the nth element of the exemple sequence to STDOUT

n=...print(n%3<1 and n/3*2or n+math.floor(n/3)+n%3-1)

Explanations

n=...                              -- shorthand for the argument
print(                             -- prints out the result of the following ternary
     n%3<1                         -- if n is divisible by 3
       and n/3*2                   -- prints out the corresponding even number
       or n+math.floor(n/3)+n%3-1) -- else prints out the odd number

The even numbers of this sequence are both the nth even number and the n multiple of 3, hence the formula n%3*2 is sufficient to generate them.

For odd numbers, it's a little bit more tough. Based on the fact that we can find them depending on the current n, we have the following table :

n       |  1   2   4   5   7   8   10   11  
target  |  1   3   5   7   9   11  13   15
target-n|  +0  +1  +1  +2  +2  +3  +3   +4

Let's call the value target-n i, we can see that each time n%3==2, i is incremented. There goes our formula :

n+math.floor(n/3)+n%3-1

The odd numbers are based on n on which we add i.

The value of i increments at the same rate as the euclidian division by 3, with an offset. math.floor(n/3) gives us the rate of increment and n%3-1 gives us the offset, making it happens on n%3==2 instead of n%3==0.

\$\endgroup\$
  • \$\begingroup\$ One byte could easily be saved by removing an unnecessary space (...and (n/...). \$\endgroup\$ – Jonathan Frech Sep 2 '17 at 17:55
  • \$\begingroup\$ @JonathanFrech was able to save 2 at this spot by totally removing the parenthesis as and n/3*2or works just as fine \$\endgroup\$ – Katenkyo Sep 6 '17 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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