Golf una biyección dentro de los números naturales que asignan los números primos a un subconjunto apropiado de números primos

14

Definiciones

  • Una biyección de un conjunto Sa un conjunto Tes una función a partir Sde Ttal manera que uno de los elementos T, se estudia con exactamente un elemento en S.

  • Una biyección dentro de un conjunto S es una biyección de Sa S.

  • Los números naturales son los enteros que son mayores o iguales que 0.

  • Un subconjunto de un conjunto Ses un conjunto tal que todos los elementos del conjunto también están en S.

  • Un subconjunto adecuado de un conjunto Ses un conjunto que Sno es igual a un subconjunto S.

Tarea

Escriba un programa / función que tome un número natural como entrada y genere un número natural. Debe ser una biyección, y la imagen de los números primos bajo el programa / función {f(p) : p ∈ ℙ}, debe ser un subconjunto apropiado de dónde están los números primos.

Puntuación

Este es el . La respuesta más corta en bytes gana. Se aplican lagunas estándar .

Monja permeable
fuente

Respuestas:

17

Mathematica, 54 48 bytes

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

Define la siguiente biyección:

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

La idea básica es asignar cada primo al siguiente, para asegurarse de que estén asignados a un subconjunto adecuado. Esto da como resultado una "brecha" en 2 . Para llenar ese espacio, queremos asignar 4 a 2 y luego cada número compuesto al número compuesto anterior, para "burbujear" el espacio. Dado que 2 y 3 son los únicos dos primos adyacentes, podemos expresar ambas asignaciones como " n-1 o si es un primo, entonces n-2 ". Finalmente, esta asignación termina enviando 1 a 0 y hacemos que envíe 0 de nuevo a 1 tomando el valor absoluto de n-1 .

Martin Ender
fuente
¿Necesitas un mapa 0?
Neil
@Neil lo hago, pero he cambiado la biyección de todos modos.
Martin Ender
8

MATL , 21 bytes

Gracias a Emigna por detectar un error, ahora corregido

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

Pruébalo en línea!

Esto implementa la siguiente biyección. Escriba los primos en una fila y los no primos a continuación:

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

Luego, la salida se obtiene siguiendo la flecha de la entrada:

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

Código explicado

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)
Luis Mendo
fuente
3

JavaScript (ES6), 82 77 75 bytes

Implementa la misma lógica que la respuesta de Luis Mendo .

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

Formateado y comentado

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

Manifestación

Arnauld
fuente
2

Jalea , 12 bytes

Æn_ḍ@¡ÆP?2»0

Pruébalo en línea!

Cómo funciona

Æ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.
Dennis
fuente
Umm, ¿por favor agrega una explicación?
Erik the Outgolfer
@EriktheOutgolfer Añadido.
Dennis
Bien, ahora más personas pueden entender este desastre ... que en realidad es demasiado obvio ¿por qué no pensé en eso?
Erik the Outgolfer