Golf a bijection within the natural numbers which map the primes to a proper subset of the primes

Question

Definitions

• A bijection from a set S to a set T is a function from S to T such that one element in T is mapped by exactly one element in S.

• A bijection within a set S is a bijection from S to S.

• The natural numbers are the integers which are greater than or equal to 0.

• A subset of a set S is a set such that every element in the set is also in S.

• A proper subset of a set S is a set that is a subset of S which is not equal to S.

Task

Write a program/function that takes a natural number as input and outputs a natural number. It must be a bijection, and the image of the primes under the program/function, {f(p) : p ∈ ℙ}, must be a proper subset of ℙ, where ℙ is the prime numbers.

Scoring

This is code-golf. Shortest answer in bytes wins. Standard loopholes apply.

Answer 1

Mathematica, 54 48 bytes

±(t=x_?PrimeQ)=NextPrime@x
±n_:=Abs[n-1]/.t:>x-1

Defines the following bijection:

 n  0, 1, 2, 3, 4, 5, 6,  7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, ...
±n  1, 0, 3, 5, 2, 7, 4, 11, 6, 8,  9, 13, 10, 17, 12, 14, 15, 19, ...

The basic idea is to map each prime to the next, to ensure that they are mapped to a proper subset. This results in a "gap" at 2. To fill that gap, we want to map 4 to 2 and then each other composite number to the previous composite number, to "bubble up" the gap. Since 2 and 3 are the only two adjacent primes, we can express both of those mappings as "n-1 or if that's a prime then n-2". Finally, this mapping ends up sending 1 to 0 and we make it send 0 back to 1 by taking the absolute value of n-1.

Answer 2

MATL, 21 bytes

Thanks to Emigna for spotting a mistake, now corrected

tZp?_Yq}q:Zp~fX>sG~E+

Try it online!

This implements the following bijection. Write the primes in a row and the non-primes below:

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

Then the output is obtained by following the arrow from the input:

2 > 3 > 5 > 7 > 11 > 13 > 17 ...
^
0 < 1 < 4 < 6 <  8 <  9 < 10 ...

Explained code

t       % Implicit input. Duplicate
Zp      % Is it a prime? Gives true / false
?       % If so
  _Yq   %   Next prime
}       % Else
  q     %   Subtract 1
  :     %   Range from 1 to that
  Zp~   %   Is each entry not a prime? Gives an array of true / false
  f     %   Find non-zero entries, i.e. non-primes. Will be empty for input 1
  X>    %   Maximum. This gives the greatest non-prime less than the input.
        %   Will be empty for input 1
  s     %   Sum. This is to transform empty into 0
  G~E   %   Push input, negate, times 2. This gives 2 for input 0, or 0 otherwise
  E     %   Add. This handles the case of input 0, so that it outputs 2
        % End (implicit). Display (implicit)

Answer 3

Jelly, 14 bytes

Æn’’ÆP¿$ÆP?2¹?

Try it online!

Uses Luis's algorithm.

Answer 4

JavaScript (ES6), 82 77 75 bytes

Implements the same logic as Luis Mendo's answer.

f=(n,i=(P=(n,x=n)=>n%--x?P(n,x):x==1||-1)(x=n))=>x?x==n|P(n)-i?f(n+i,i):n:2

Formatted and commented

f = (                   // given:
  n,                    // - n = input
  i =                   // - i = 'direction' to move towards
    (P = (n, x = n) =>  // - P = function that returns:
      n % --x ?         //   - 1 when given a prime
        P(n, x)         //   - -1 when given a composite number
      :                 //
        x == 1 || -1    //
    )(x = n)            // - x = copy of the original input
) =>                    //
  x ?                   // if the input is not zero:
    x == n | P(n) - i ? //   if n equals the input or doesn't match its primality:
      f(n + i, i)       //     do a recursive call in the chosen direction
    :                   //   else:
      n                 //     return n
  :                     // else:
    2                   //   return 2

Demo

f=(n,i=(P=(n,x=n)=>n%--x?P(n,x):x==1||-1)(x=n))=>x?x==n|P(n)-i?f(n+i,i):n:2

for(n = 0; n < 50; n++) {
  console.log(n, '->', f(n));
}

Answer 5

Jelly, 12 bytes

Æn_ḍ@¡ÆP?2»0

Try it online!

How it works

Æn_ḍ@¡ÆP?2»0  Main link. Argument: n (non-negative integer)

      ÆP?     If the input is prime:
Æn                Compute the next prime after n.
              Else:
   ḍ@¡   2        Do once if n is divisible by 2, zero times if not.
  _      2        Subtract 2.
              So far, we've mapped all primes to the next prime, all even integers
              (except 2) to the previous even integer, and all composite, odd,
              positive integers to themselves. In particular, 0 -> 2, but 0 doesn't
              have a preimage, so we need 0 -> 0.
          »0  Take the maximum of the result and 0, mapping 0 -> max(-2, 0) = 0.