Гольф биекция в натуральных числах, которые отображают простые числа в надлежащее подмножество простых чисел

14

Определения

  • Биекция из набора Sк набору Tявляется функцией от , Sчтобы Tтаким образом, что один из элементов в Tсопоставляются ровно один элементом S.

  • Биекция в наборе S является биекцией от SдоS .

  • В натуральных числах целых числа , которые больше или равно0 .

  • Подмножество множества Sпредставляет собой набор таким образом, что каждый элемент в наборе также находится вS .

  • Собственное подмножество множества Sпредставляет собой набор , который является подмножеством , Sкоторое не равно S.

задача

Напишите программу / функцию, которая принимает натуральное число в качестве входных данных и выводит натуральное число. Это должна быть биекция, и изображение простых чисел в программе / функции {f(p) : p ∈ ℙ}должно быть правильным подмножеством , где есть простые числа.

счет

Это . Кратчайший ответ в байтах побеждает. Применяются стандартные лазейки .

Дрянная Монахиня
источник

Ответы:

17

Mathematica, 54 48 байтов

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

Определяет следующую биекцию:

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

Основная идея состоит в том, чтобы сопоставить каждое простое число следующему, чтобы гарантировать, что они сопоставлены с правильным подмножеством. Это приводит к "разрыву" в 2 . Чтобы заполнить этот пробел, мы хотим отобразить 4 к 2 и затем каждое другое составное число к предыдущему составному номеру, чтобы «увеличить» разрыв. Поскольку 2 и 3 являются единственными двумя смежными простыми числами, мы можем выразить оба этих отображения как « n-1 или, если это простое число, то n-2 ». Наконец, это отображение заканчивается отправкой 1 в 0, и мы заставляем его отправлять 0 обратно в 1 , принимая абсолютное значение n-1 .

Мартин Эндер
источник
Вам нужно карту 0?
Нил
@ Нет, но я все равно изменил биографию.
Мартин Эндер
8

MATL , 21 байт

Спасибо Emigna за обнаружение ошибки, теперь исправлена

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

Попробуйте онлайн!

Это реализует следующую биекцию. Запишите простые числа в ряд и не простые числа ниже:

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

Затем результат получается, следуя стрелке из ввода:

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

Объясненный код

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)
Луис Мендо
источник
3

JavaScript (ES6), 82 77 75 байт

Реализует ту же логику, что и ответ Луиса Мендо .

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

Отформатировано и прокомментировано

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

демонстрация

Arnauld
источник
2

Желе , 12 байт

Æn_ḍ@¡ÆP?2»0

Попробуйте онлайн!

Как это устроено

Æ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.
Деннис
источник
Хмм, пожалуйста, добавьте объяснение?
Эрик Outgolfer
@EriktheOutgolfer Добавлено.
Деннис
Хорошо, теперь больше людей могут понять этот беспорядок ... что на самом деле слишком очевидно, почему я не подумал об этом?
Эрик Outgolfer