What an Odd Function

Question

Your task here will be to implement a function¹ 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 code-golf 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.}

Answer 1

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.

Answer 2

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

Answer 3

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!

Answer 4

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

Answer 5

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) = ⅓(2ⁿ⁺¹ - 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 (2ⁿ⁺¹ - 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.

Answer 6

Brain-Flak, 120 bytes

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

Try it online!

Performs the following 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

Answer 7

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.

Answer 8

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 2^x and consecutive odd numbers otherwise:

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

Answer 9

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.

Answer 10

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.

Answer 11

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!

Answer 12

Batch, 36 bytes

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

Implements the sequence given in the question.

Answer 13

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

Answer 14

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
}

Answer 15

Perl 40 bytes

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

Answer 16

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.

Answer 17

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.

Answer 18

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.

Answer 19

Jelly, 9 bytes

Ḥ€’ĖUẎQ⁸ị

Try it online!

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

Answer 20

05AB1E, 11 bytes

·ÅÉā‚ø˜Ù¹<è

Try it online!

Answer 21

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.

Answer 22

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.