Golf uma bijeção dentro dos números naturais que mapeiam os números primos para um subconjunto adequado dos números primos

14

Definições

  • Uma bijeção de um conjunto Spara um conjunto Té uma função de Spara Tque um elemento em Tseja mapeado por exatamente um elemento em S.

  • Uma joia dentro de um conjunto S é uma joia de Spara S.

  • Os números naturais são os números inteiros maiores ou iguais a 0.

  • Um subconjunto de um conjunto Sé um conjunto de forma que todos os elementos do conjunto também estejam S.

  • Um subconjunto adequado de um conjunto Sé um conjunto cujo subconjunto Snão é igual a S.

Tarefa

Escreva um programa / função que aceite um número natural como entrada e emita um número natural. Deve ser uma bijeção, e a imagem dos números primos sob o programa / função {f(p) : p ∈ ℙ}, deve ser um subconjunto apropriado de , onde estão os números primos.

Pontuação

Isso é . A resposta mais curta em bytes vence. Aplicam-se brechas padrão .

Freira Furada
fonte

Respostas:

17

Mathematica, 54 48 bytes

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

Define a seguinte bijeção:

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

A idéia básica é mapear cada prime para o próximo, para garantir que eles sejam mapeados para um subconjunto adequado. Isso resulta em uma "lacuna" em 2 . Para preencher essa lacuna, queremos mapear 4 a 2 e depois o número composto para o número composto anterior, para "aumentar" a diferença. Como 2 e 3 são os únicos dois números primos adjacentes, podemos expressar ambos os mapeamentos como " n-1 ou, se for um primo, então n-2 ". Finalmente, esse mapeamento acaba enviando 1 para 0 e enviamos 0 de volta para 1 , assumindo o valor absoluto de n-1 .

Martin Ender
fonte
Você precisa mapear 0?
911 Neil
@ Neil eu faço, mas eu mudei a bijeção agora de qualquer maneira.
Martin Ender
8

MATL , 21 bytes

Agradecimentos a Emigna por detectar um erro, agora corrigido

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

Experimente online!

Isso implementa a seguinte bijeção. Escreva os primos seguidos e os não primos abaixo:

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

Em seguida, a saída é obtida seguindo a seta da 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
fonte
3

JavaScript (ES6), 82 77 75 bytes

Implementa a mesma lógica da resposta 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

Formatado e 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

Demo

Arnauld
fonte
2

Gelatina , 12 bytes

Æn_ḍ@¡ÆP?2»0

Experimente online!

Como 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
fonte
Umm, por favor, adicione uma explicação?
Erik the Outgolfer
@EriktheOutgolfer Adicionado.
Dennis
Bom, agora mais pessoas podem entender essa bagunça ... o que é realmente muito óbvio por que eu não pensei nisso?
Erik the Outgolfer