16
\$\begingroup\$

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

\$\endgroup\$
  • 16
    \$\begingroup\$ Was it hard to get permission from the original author? \$\endgroup\$ – Luis Mendo Mar 12 at 16:08
  • 11
    \$\begingroup\$ @LuisMendo Yes very, I wanted to post this a long time ago but it took me ages to convince them. :) \$\endgroup\$ – Ad Hoc Garf Hunter Mar 12 at 16:10

10 Answers 10

11
\$\begingroup\$

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:

graph

|improve this answer|||||
\$\endgroup\$
  • 2
    \$\begingroup\$ Are you sure this works? Unlike Luis' method, your blocks grow linearly. \$\endgroup\$ – xnor Mar 12 at 20:48
  • 2
    \$\begingroup\$ @xnor It was wrong indeed. I've switched to another approach. \$\endgroup\$ – Arnauld Mar 12 at 21:49
8
\$\begingroup\$

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
|improve this answer|||||
\$\endgroup\$
8
\$\begingroup\$

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 10n are just rearranged, so the proportion of odd numbers for inputs up to 10n is 0.5.

All the numbers from 10n+1 to 10n+10n-1-1 map to even numbers, so the proportion of odd numbers for inputs up to 10n+10n-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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ I believe \B can help save some bytes. \$\endgroup\$ – user41805 Mar 12 at 17:39
  • \$\begingroup\$ @user41805 Thanks -- I haven't even really looked at golfing this yet :) . \$\endgroup\$ – Mitchell Spector Mar 12 at 17:48
  • \$\begingroup\$ This could be 6 bytes in Retina. \$\endgroup\$ – Neil Mar 12 at 20:59
  • \$\begingroup\$ @Neil How would you do this in 6 bytes? I took a quick look at the Retina documentation (not being familiar with the language), and I posted an answer at codegolf.stackexchange.com/a/200959/59825 -- but the direct port from sed that I did is 17 bytes long. \$\endgroup\$ – Mitchell Spector Mar 13 at 6:46
  • \$\begingroup\$ @xnor already took the first step, which is that all you need to do is to reverse the digits after the first. Since Retina has a built-in that reverses the characters in the match, all you then have to do is to ensure that your match contains all characters except the first. \$\endgroup\$ – Neil Mar 13 at 11:39
6
\$\begingroup\$

APL (Dyalog Extended), 8 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
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ A080541 \$\endgroup\$ – xnor Mar 13 at 3:43
3
\$\begingroup\$

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

|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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 :) .

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ If you want to preserve your algorithm, you can still save bytes by using the reverse stage. I'm not convinced this is optimal, even without using the different approach Neil suggested. Happy Retina golfing :) \$\endgroup\$ – FryAmTheEggman Mar 13 at 16:14
  • \$\begingroup\$ @FryAmTheEggman I really don't know Retina yet, so if you want to post the 5-byte version, please go ahead. (I suggested that Neil post the 6-byte version, which he's done.) \$\endgroup\$ – Mitchell Spector Mar 13 at 16:22
  • \$\begingroup\$ I've moved my suggestion to his post, since it is just a golf of it. I hope you do get to know Retina :) \$\endgroup\$ – FryAmTheEggman Mar 13 at 16:24
  • \$\begingroup\$ @FryAmTheEggman Thanks -- it looks like a great language, and seeing posted examples makes it easier to learn. \$\endgroup\$ – Mitchell Spector Mar 13 at 16:26
0
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$

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.