An unknowably odd function

Question

This challenge initially appeared in this challenge as a an extra brain teaser. I am posting it with permission from the original author so that we can have a formal competition.

---

Your task here will be to implement a function¹ that forms a permutation on the positive integers. This means that each positive integer should be the output of calling the function with exactly one positive integer.

In the earlier challenge we calculated the odd probability for such sequences. We defined it as so:

If 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}$$

Your task is to write a function with no defined odd probability. That is a function \$f\$ for which the above limit does not converge.

---

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

---

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

Answer 1

JavaScript (ES7),  33  29 bytes

This is A307485: one odd, two even, four odd, eight even, etc.

n=>n-~n-(4<<Math.log2(n))/3|0

Try it online!

For \$n\in\mathbb{N}^*\$, this is equivalent to:

$$a(n)=2n+1-\left\lceil\frac{2^{\lfloor log_2 n\rfloor+2}}{3}\right\rceil$$

It produces the sequence:

1
2 4
3 5 7 9
6 8 10 12 14 16 18 20
...

The ratio of odd values is 'bouncing' ad infinitum between \$1/3\$ and \$2/3\$, more and more slowly:

Answer 2

sed -E, 20 17 bytes

s/\B(.)(.*)/\2\1/

Try it online!

Saved 3 bytes as per user41805's suggestion.

This takes the input number and moves the 2nd digit (from the left) to the end of the number (the one's place).

The numbers from 1 to 10ⁿ are just rearranged, so the proportion of odd numbers for inputs up to 10ⁿ is 0.5.

All the numbers from 10ⁿ+1 to 10ⁿ+10^n-1-1 map to even numbers, so the proportion of odd numbers for inputs up to 10ⁿ+10^n-1 is $$\frac{10^n/2+1}{10^n+10^{n-1}}=\frac{5+10^{-(n-1)}}{11},$$ which approaches 5/11 as n approaches infinity.

Answer 3

MATL, 18 17 16 bytes

:"vtn@W:2e+!h]G)

Try it online!

This produces the following permutation of the positive integers:

1 2 3 5 4 6 7 9 11 13 8 10 12 14 15 17 19 21 23 25 27 29 16 18 20 22 24 26 28 30 ...

The pattern is easier to see if the sequence is arranged as follows (read top to down, then left to right):

1
2
3   5
4   6
7   9 11 13
8  10 12 14
15 17 19 21 23 25 27 29
16 18 20 22 24 26 28 30
...

It's clear that the cumulative proportion of odd values has limit superior 2/3 and limit inferior 1/2. Or see the proportion graphically at MATL Online!

Explanation

The code produces a longer sequence than needed (with length exponential in the input number), and then outputs the term specified by the input.

:       % Implicit input, n. Push range [1 2 ... n]
"       % For each k in [1 2 ... n]
  v     %   Concatenate stack vertically. This is only useful in the first
        %   iteration, to produce the empty array [], which will later be 
        %   extended with terms of the sequence
  tn    %   Duplicate sequence so far. Push its number of elements, say m
  @W:   %   Push range [1 2 3 ... 2^k]
  2e    %   Arrange as a two-row matrix in column-major order. Gives
        %   [1 3 5 ... 2^k-1;
        %    2 4 6 ... 2^k]
  +     %   Add, element-wise. Gives
        %   [m+1 m+3 m+5 ... m+2^k-1;
        %    m+2 m+4 m+6 ... m+2^k]
  !h    %   Transpose, then concatenate into a row vector. This extends the
        %   sequence. The transpose is needed so that, when concatenating,
        %   the terms are included in the correct order
]       % End
G)      % Take the n-th entry. Implicit display

Answer 4

APL (Dyalog Extended), ⁸ 4 bytes

⌽1⌽⍞

Try it online!

Based on xnor's idea to keep the first digit and reverse the rest. A full program that takes the input from STDIN as a string, rotates left once (1⌽), reverses (⌽), and prints to STDOUT.

---

APL (Dyalog Extended), 8 bytes

⊥1,1⌽1↓⊤

Try it online!

Generates a sequence that is very similar to Luis Mendo's MATL answer:

1
2
3
4 6
5 7
8 10 12 14
9 11 13 15
16 18 20 22 24 26 28 30
17 19 21 23 25 27 29 31
...

How it works

⊥1,1⌽1↓⊤
       ⊤  ⍝ Convert to binary digits
     1↓   ⍝ Remove the leading 1
   1⌽     ⍝ Rotate left once; move 2nd bit to last
 1,       ⍝ Add back the leading 1
⊥         ⍝ Convert binary digits to integer

Answer 5

Haskell, 18 bytes

f(h:t)=h:reverse t

Try it online!

Based on Mitchell Spector's idea. Leaves the first digit in place and reverses the rest. Input and output are as strings.

Answer 6

Retina, 6 5 bytes

,V1,`

Try it online! Link includes test cases shamelessly stolen from @xnor. Uses the same suffix reversal algorithm inspired by @MitchellSpector's sed answer. Edit: Saved 1 byte thanks to @FryAmTheEggman. Explanation:

V`

Reverse the matched characters (defaults to matching each line).

,

Reverse all matches

1,

Exclude the first character of each match from being reversed. (^0 also works.)

Answer 7

Python, 22 bytes

lambda s:s[0]+s[:0:-1]

Try it online!

Based on Mitchell Spector's idea. Leaves the first digit in place and reverses the rest. Input and output are as strings.

Answer 8

Pure Bash, 27 bytes

echo ${1:0:1}${1:2}${1:1:1}

Try it online!

This uses the same method as my sed answer.

Answer 9

Retina, 18 17 bytes

(.)(.)(.*)
$1$3$2

Try it online!

This is a port of my sed answer (moving the second digit to the far right). I've never programmed in Retina before, so I took a quick look at the language documentation and put this together. I assume that it can be made much shorter using more advanced features of Retina.

Also, if there's any error in the Retina code, please let me know. It does appear to work :) .

Answer 10

Charcoal, 7 bytes

§θ⁰⮌✂θ¹

Try it online! Link is to verbose version of code. This is the Charcoal port of the 6-byte Retina 1 answer that I alluded to in my comments to @MitchellSpector's sed answer, and then presumably independently discovered by @xnor. I/O as strings (which Charcoal defaults to anyway). Explanation:

§θ⁰

Print the first character of the input number.

⮌✂θ¹

Print the remaining characters of the input number, but reversed.