# What an Odd Function

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). (Now a standalone challenge here)

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

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

• 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. Sep 2, 2017 at 16:32
• 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. Sep 3, 2017 at 8:40

# 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


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! • Save a paren: (!!)$do ...
– xnor
Sep 2, 2017 at 1:24

# 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


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

{($_==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.

• 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. Sep 2, 2017 at 7:23
• Well, the extra challenges are what's interesting on this question for me. The core challenge is not. But I added some solution anyway. Sep 2, 2017 at 11:34
• I asked for a proof that your response to Challenge 3 has no limit in this Math.SE question: math.stackexchange.com/questions/2416053/… Sep 4, 2017 at 5:05
• @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. Sep 4, 2017 at 17:33
• @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. Sep 4, 2017 at 23:06

# 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

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

• 58 bytes Sep 6, 2017 at 17:28
• 56 bytes Sep 26, 2017 at 15:37
• 53 bytes Jan 24, 2018 at 22:42

# 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

• return n&n-1?2*n-i-1:i; can be return~-n&n?2*n+~i:i for -2. In addition, but return  can be n= to save some more bytes. Mar 12, 2020 at 16:11

# Brain-Flak, 140138 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.

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


# 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

• n=>n%4?1.5*n|1:n/2 is 5 bytes shorter. Sep 2, 2017 at 16:01

# Re:direction, 20 19 bytes

+++>>
v>
+>>
v>
<


Try it online!

-1 by rearranging to remove a space.

Here's what happens, based on the input number:

• 3n: It runs along the first line n times, picking up 2n >s, before going down from the first +. It then adds a v, and hits the bottom <, which points to itself to halt, outputting 2n.
• 3n+1: It again runs along the first line n times, picking up 2n >s, and then it passes the first + and goes down on the second one. It then adds a v. The loop on the third line doubles the number of >s in the queue to 4n before ending by consuming the v. On the fourth line, another > is added, for 4n+1, before ending in the same way as the previous case, outputting 4n+1.
• 3n+2: Mostly the same as the above case, except going down from the third + and then adding an extra > before joining the same path, making 2n+1, which becomes 4n+2, then 4n+3, and outputting 4n+3.

# 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!

## Batch, 36 bytes

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


Implements the sequence given in the question.

## 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
}


# Perl 40 bytes

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


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

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

# Lean, 85 bytes

import data.nat.prime
λx,list.prod$list.map(λp,if p<4then 5-p else p)$nat.factors x


Try it online!

Swaps 2s with 3s in the prime factorization.

# Vyxal, 6 bytes

ǐ:4<꘍Π


Port of Dennis's Jelly answer. 1J is needed due to a bug in Vyxal where the product of [] returns 0 instead of 1. Bug fixed.

## How?

ǐ:4<꘍Π
ǐ      # Get the prime factors with duplicates
:     # Duplicate
4<   # For each item, is it less than 4? (Vectorizes, produces a list of 1s and 0s)
꘍  # Bitwise XOR the two arrays (vectorizes)
Π # Product of resulting array

• Producing 0 from input 1 makes this invalid.
– m90
May 13 at 17:36
• @m90 Added a hacky workaround. There was a bug in Vyxal where product of [] = 0. May 13 at 18:43

# Python 2, 46104 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.

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

# Jelly, 9 bytes

Ḥ€’ĖUẎQ⁸ị


Try it online!

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

# 05AB1E, 11 bytes

·ÅÉā‚ø˜Ù¹<è


Try it online!

# Pyth, 9 bytes

*Fmxd<d4P


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


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.


# Java 8, 20 bytes

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


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.

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

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

# 05AB1E, 6 bytes

ÒD4‹^P


Port of @Dennis' Jelly answer, so make sure to upvote him!

The probability of odds is therefore also $$\\frac{2}{3}\$$.

Explanation:

Ò       # Get the prime factors of the (implicit) input-integer, counting multiplicities
D      # Duplicate this list
4‹    # Check for each value whether it's smaller than 4 (1 for 2 and 3; 0 otherwise)
^   # Bitwise-XOR the two lists at the same indices
# (2 becomes 3; 3 becomes 2; everything else remains unchanged)
P  # And take the product of this
# (after which the result is output implicitly)


# x86 32-bit machine code, 12 bytes

a8 03 74 05 8d 04 40 0c 02 d1 e8 c3


A port of nwellnhof's C answer. Uses the regparm(1) calling convention – argument in EAX, result in EAX.

Try it online! (contains all five functions)

Assembly:

f:
test al, 3                  # Take the low two bits of the value.
jz point0                   # Jump if they are both 0.
lea eax, [eax + eax * 2]    # Triple the value in EAX.
or al, 2                    # Set the twos bit in EAX.
point0:
shr eax, 1                  # Shift EAX right by 1 bit.
ret                         # Return.


## The opposite

I also found an 11-byte function with a 1/4 odd probability:

0f bc c8 d3 e8 83 f1 01 d3 e0 c3


Assembly:

fe:
bsf ecx, eax    # Set ECX to the position of the lowest 1 bit in EAX.
shr eax, cl     # Shift EAX right by that quantity, removing all ending 0 bits.
xor ecx, 1      # Invert the lowest bit of ECX.
shl eax, cl     # Shift EAX left, introducing a modified number of ending 0 bits.
ret             # Return.


# 1st extra challenge: 18 bytes

f3 0f b8 c8 d1 e0 0f bd d0 d1 e2 48 29 d0 e2 01 92 c3


Implements a function several other answers have used, mapping powers of 2 to even numbers in ascending order and other numbers to odd numbers in ascending order: $$\ f_1(2^m) = 2m+2 \$$, and for $$\ n \in [2^m, 2^{m+1})\$$, $$\ f_1(n) = 2n - 2m - 3\$$.

Assembly:

f1:
popcnt ecx, eax # Set ECX to the number of 1 bits in EAX.
shl eax, 1      # Shift EAX left by 1, doubling it to 2n.
bsr edx, eax    # Set EDX to the position of the highest 1 bit in EAX -- m+1.
shl edx, 1      # Shift EDX left by 1, doubling it to 2m+2.
dec eax         # Decrement EAX to 2n-1.
sub eax, edx    # Subtract EDX from EAX, making it 2m-2n-3.
loop point1     # Decrement ECX and jump if it's nonzero -- if the value was not a power of 2.
xchg eax, edx   # Exchange EAX and EDX, making EAX 2m+2.
point1:
ret             # Return.


# 2nd extra challenge: 6 bytes

83 f0 01 74 fb c3


Produces $$\ 1, 3, 2, 5, 4, 7, 6, ... \$$

Assembly:

f2:
xor eax, 1  # Invert the lowest bit of the value.
jz f2       # Jump back if that makes it 0 (and it will be flipped back to 1).
ret         # Return.


# 3rd extra challenge: 12 bytes

0f bd c8 d3 d8 19 d2 d3 c0 29 d0 c3


Rearranges the bits of the value by moving the second-highest bit to the bottom. This produces 1 odd, 1 even, 1 odd, 2 even, 2 odd, 4 even, 4 odd, ...

Assembly:

f3:
bsr ecx, eax    # Set ECX to the position of the highest 1 bit in EAX.
rcr eax, cl     # Rotate EAX and the carry flag CF together left by that quantity.
# Note that the value of CF after BSR is officially undefined,
#  but it is consistently 0 on at least some systems, which is what this function needs.
# This puts the second-highest bit of the value into CF,
#  while the highest bit goes to the bottom position and the lower bits go to the top.
sbb edx, edx    # Subtract EDX+CF from EDX, making its value -CF.
rol eax, cl     # Rotate EAX right by the same value, not including CF in the rotation.
# EAX now contains all the bits of the original value except the second-highest,
#  followed by a single 0 bit; if the original value was 1, EAX is now 1.
sub eax, edx    # Subtract EDX from EAX, replacing the removed bit at the bottom.
ret             # Return.


# Python 2, 39 bytes

lambda n:[n/3*4+1,n/3*4+3,n/3*2+2][n%3]


Try it online!

outputs :

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


Odd probability = 2/3

If generating the sequence without taking an inputs is accepted, I also have:

### Python 2, 34 bytes

i=3
while 1:print-~i/2,i-2,i,;i+=4


Try it online!

Outputs:

2 1 3 4 5 7 6 9 11 8 13 15 10 17 19 12 21 23 14 25 27 16 29 31 18 33 35 20 37 39 22 41 ...


Odd probability = 2/3

# Mathematical function, 48 bytes

You said "function", so I'm making a function. Takes an input x and returns the x+1th term. It does mess up when given a non-integer.

       x>=1>(x-1) mod 2:x+2
f(x)={ x>=1>x mod 2:x       }
x=0:1


Excluding non-meaningful whitespace.

Here's a graph:

There are always one or two more odd numbers than even ones.