Bermain golf dalam bilangan asli yang memetakan bilangan prima ke subset bilangan prima yang tepat

14

Definisi

  • Sebuah bijection dari satu set Ske set Tadalah fungsi dari Ske Tsehingga salah satu unsur dalam Tdipetakan oleh tepat satu elemen di S.

  • Sebuah bijih di dalam set S adalah bijih dari Ske S.

  • The bilangan adalah bilangan bulat yang lebih besar dari atau sama dengan 0.

  • Sebuah bagian dari suatu himpunan Sadalah satu set sehingga setiap elemen dalam set juga di S.

  • Sebuah subset dari set Sadalah satu set yang merupakan bagian dari Syang tidak sama dengan S.

Tugas

Tulis program / fungsi yang mengambil bilangan asli sebagai input dan menghasilkan bilangan alami. Itu harus menjadi sebuah peninggalan, dan gambar bilangan prima di bawah program / fungsi {f(p) : p ∈ ℙ},, harus menjadi subset yang tepat , di mana bilangan prima.

Mencetak gol

Ini adalah . Jawaban terpendek dalam byte menang. Celah standar berlaku .

Biarawati Bocor
sumber

Jawaban:

17

Mathematica, 54 48 byte

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

Mendefinisikan bijection berikut:

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

Ide dasarnya adalah memetakan setiap prime ke yang berikutnya, untuk memastikan bahwa mereka dipetakan ke subset yang tepat. Ini menghasilkan "celah" pada 2 . Untuk mengisi celah itu, kami ingin memetakan 4 hingga 2 dan kemudian masing-masing nomor komposit lainnya ke nomor komposit sebelumnya, untuk "menggembungkan" celah tersebut. Karena 2 dan 3 adalah hanya dua bilangan prima yang berdekatan, kita dapat mengekspresikan kedua pemetaan tersebut sebagai " n-1 atau jika itu bilangan prima, maka n-2 ". Akhirnya, pemetaan ini akhirnya mengirim 1 ke 0 dan kami membuatnya mengirim 0 kembali ke 1 dengan mengambil nilai absolut n-1 .

Martin Ender
sumber
Apakah Anda perlu memetakan 0?
Neil
@Neil saya lakukan, tapi saya sudah mengubah bijection sekarang pula.
Martin Ender
8

MATL , 21 byte

Terima kasih kepada Emigna karena menemukan kesalahan, sekarang diperbaiki

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

Cobalah online!

Ini mengimplementasikan penambangan berikut. Tuliskan bilangan prima secara berturut-turut dan non-bilangan prima di bawah ini:

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

Kemudian output diperoleh dengan mengikuti panah dari input:

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

Kode yang dijelaskan

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
sumber
3

JavaScript (ES6), 82 77 75 byte

Menerapkan logika yang sama dengan jawaban 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

Diformat dan dikomentari

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
sumber
2

Jelly , 12 byte

Æn_ḍ@¡ÆP?2»0

Cobalah online!

Bagaimana itu bekerja

Æ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
sumber
Umm, tolong tambahkan penjelasan?
Erik the Outgolfer
@EriktheOutgolfer Ditambahkan.
Dennis
Bagus, sekarang lebih banyak orang dapat memahami kekacauan ini ... yang sebenarnya terlalu jelas mengapa saya tidak memikirkannya?
Erik the Outgolfer