14
\$\begingroup\$

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 . Shortest answer in bytes wins. Standard loopholes apply.

\$\endgroup\$
1

5 Answers 5

17
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Do you need to map 0? \$\endgroup\$
    – Neil
    Jun 8, 2017 at 15:34
  • \$\begingroup\$ @Neil I do, but I've changed the bijection now anyway. \$\endgroup\$ Jun 8, 2017 at 15:37
8
\$\begingroup\$

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)
\$\endgroup\$
0
4
\$\begingroup\$

Jelly, 14 bytes

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

Try it online!

Uses Luis's algorithm.

\$\endgroup\$
3
\$\begingroup\$

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));
}

\$\endgroup\$
0
2
\$\begingroup\$

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.
\$\endgroup\$
3
  • \$\begingroup\$ Umm, please add an explanation? \$\endgroup\$ Jun 10, 2017 at 12:22
  • \$\begingroup\$ @EriktheOutgolfer Added. \$\endgroup\$
    – Dennis
    Jun 10, 2017 at 14:05
  • \$\begingroup\$ Good, now more people can understand this mess...which is actually way too obvious why didn't I think of that? \$\endgroup\$ Jun 10, 2017 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.