Spielen Sie eine Bijektion innerhalb der natürlichen Zahlen ab, die die Primzahlen einer geeigneten Teilmenge der Primzahlen zuordnen

14

Definitionen

  • Eine Bijektion von einer Menge Szu einer Menge Tist eine Funktion von Sbis T, sodass ein Element in Tvon genau einem Element in abgebildet wird S.

  • Ein Bijection innerhalb eines Sets S ist ein Bijection von Sbis S.

  • Die natürlichen Zahlen sind die ganzen Zahlen, die größer oder gleich sind 0.

  • Eine Teilmenge einer Menge Sist eine Menge, bei der sich jedes Element in der Menge auch in befindet S.

  • Eine richtige Teilmenge einer Menge Sist eine Menge, bei der es sich um eine Teilmenge Shandelt, die nicht gleich ist S.

Aufgabe

Schreiben Sie ein Programm / eine Funktion, die eine natürliche Zahl als Eingabe verwendet und eine natürliche Zahl ausgibt. Es muss eine Bijektion sein, und das Bild der Primzahlen unter dem Programm / Funktion, {f(p) : p ∈ ℙ}muss eine echte Teilmenge von sein , wo die Primzahlen sind.

Wertung

Das ist . Kürzeste Antwort in Bytes gewinnt. Es gelten Standardlücken .

Undichte Nonne
quelle

Antworten:

17

Mathematica, 54 48 Bytes

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

Definiert die folgende Bijektion:

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

Die Grundidee besteht darin, jede Primzahl der nächsten zuzuordnen, um sicherzustellen, dass sie einer richtigen Teilmenge zugeordnet sind. Dies führt zu einer "Lücke" bei 2 . Um diese Lücke zu füllen, wollen wir 4 bis 2 und dann die jeweils andere zusammengesetzte Zahl der vorherigen zusammengesetzten Zahl zuordnen, um die Lücke zu "sprudeln". Da 2 und 3 die einzigen zwei benachbarten Primzahlen sind, können wir beide Zuordnungen als " n-1 " ausdrücken, oder wenn dies eine Primzahl ist, dann n-2 . Schließlich sendet dieses Mapping 1 zu 0 und wir lassen es 0 zu 1 zurücksenden, indem wir den absoluten Wert von n-1 nehmen .

Martin Ender
quelle
Müssen Sie abbilden 0?
Neil
@Neil das tue ich, aber ich habe die Bijektion jetzt trotzdem geändert.
Martin Ender
8

MATL , 21 Bytes

Vielen Dank an Emigna für das Erkennen eines Fehlers, der jetzt korrigiert wurde

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

Probieren Sie es online!

Dies implementiert die folgende Bijektion. Schreibe die Primzahlen in eine Reihe und die Nicht-Primzahlen unten:

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

Dann erhalten Sie die Ausgabe, indem Sie dem Pfeil von der Eingabe folgen:

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

Erklärter 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)
Luis Mendo
quelle
3

JavaScript (ES6), 82 77 75 Byte

Implementiert dieselbe Logik wie Luis Mendos Antwort .

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

Formatiert und kommentiert

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

Gelee , 12 Bytes

Æn_ḍ@¡ÆP?2»0

Probieren Sie es online!

Wie es funktioniert

Æ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
quelle
Ähm, bitte eine Erklärung hinzufügen?
Erik der Outgolfer
@EriktheOutgolfer Hinzugefügt.
Dennis
Gut, jetzt können mehr Leute dieses Durcheinander verstehen ... was eigentlich viel zu offensichtlich ist, warum habe ich nicht daran gedacht?
Erik der Outgolfer