Wenn eine Primzahl Pgrößer als ist 10, muss Ihr Programm oder Ihre Funktion die Teilungsregel ermitteln x, die als Ganzzahl mit dem kleinsten absoluten Wert definiert ist und ein Vielfaches der ursprünglichen Primzahl ergibt, wenn sie mit der letzten Ziffer der Primzahl multipliziert und zum Rest des Originals addiert wird prime.

Beispiel

Bei einer Eingabe 31ist die letzte Ziffer 1und der Rest der Zahl 3. Daher muss Ihr Programm die Ganzzahl xmit dem minimalen absoluten Wert finden, der 1*x + 3ein Vielfaches von ist 31. In diesem Fall x=-3funktioniert, so dass das Programm oder die Funktion zurückkehren würde -3.

Bei einer Eingabe 1000003ist die letzte Ziffer 3und der Rest der Zahl 100000. So würde dein Programm x=300001denn finden, 3*300001+100000 = 1000003was ein Vielfaches von ist 1000003.

Mathematischer Hintergrund

Der Wert von xkann als Teilbarkeitstest verwendet werden. Wenn eine Zahl Ndurch teilbar ist P, ergibt das Addieren xder letzten Ziffer von Nzum Rest von Nein Vielfaches von Pnur dann, wenn sie überhaupt Ndurch teilbar ist P.

Denn P=11wir erhalten x=-1, was der bekannten Teilbarkeitsregel für äquivalent ist 11: Eine Zahl ist teilbar durch 11wechselnde Differenz ihrer Ziffern ist teilbar durch 11.

Regeln

• Die Ausgabe kann in jeder Form erfolgen, die sowohl das Vorzeichen als auch den Wert der Ausgabe eindeutig codiert.
• Die Eingangsprimzahl liegt zwischen 10 und 2 ^ 30.
• Sie müssen nicht damit umgehen, wenn der Eingang keine Primzahl ist oder nicht im Bereich liegt.
• Sie müssen nicht behandeln, wenn beide xund -xgültige Ausgaben sind (sollte nicht passieren).
• Brute Force ist erlaubt, aber kreativere Lösungen werden geschätzt.
• Das ist Code-Golf , also gewinnt der kürzeste Code in jeder Sprache ! Lassen Sie sich von Antworten in Golfsprachen nicht davon abhalten, in anderen Sprachen zu posten.

Testfälle

Input   Output
11  -1
13  4
17  -5
19  2
23  7
29  3
31  -3
37  -11
41  -4
43  13
47  -14
53  16
59  6
61  -6
67  -20
71  -7
73  22
79  8
83  25
89  9
97  -29
101 -10
103 31
107 -32
109 11
113 34
127 -38
131 -13
1000003 300001
2000003 600001
2999999 300000
9999991 -999999

JavaScript (ES6), 32 25 23 Byte

f=
n=>(3/(n%5*2-5)*n+1)/10

<input type=number min=1 oninput=o.textContent=this.value%5*(this.value%2)?f(this.value):``><pre id=o>

3/(n%5*2-5)würde geschrieben werden, 9/n(mod -10)wenn ich Zugang zu einer ausgeglichenen Modulo-Division hätte. Bearbeiten: 2 Bytes dank @EgorSkriptunoff gespeichert

Python 2 , 27 Bytes

lambda n:(n%5*2-5^2)*n/10+1

Probieren Sie es online!

Die Operationen werden von links nach rechts durchgeführt: (((n%5)*2)-5)^2.

Ich habe meinen arithmetischen Brute Forcer verwendet, um den Ausdruck n%5*2-5^2zu finden, der ausgeführt werden {1:-1,3:3,2:-3,4:1}[k]soll. Dabei habe ich die negative Inverse eines Residuen-Mods 5 in den Bereich aufgenommen [-2..2].

Gelee ,10 8 Bytes

,N⁵æiAÞḢ

Probieren Sie es online!

Erklärungen

,N       Get [Input, -Input].
⁵æi      Modular inverse of 10 mod each of [Input, -Input].
AÞ       Sort by absolute value.
Ḣ        First.

Brachylog , 14 Bytes

∧.ℤ≜×₁₀-₁;?%0∧

Probieren Sie es online!

Python 2 , 69 54 53 Bytes

Edit: -15 Bytes dank @ Mr.Xcoder

Bearbeiten: -1 Byte unter Verwendung von Rekursion

f=lambda a,x=-1:(a%10*x+a/10)%a and f(a,-x-(x>0))or x

Probieren Sie es online!

Python 2 , 31 29 27 Bytes

lambda n:3/(n%5*2-5)*n/10+1

Probieren Sie es online!

Japt , 16 9 Bytes

Dank einer Beobachtung von @xnor viel zu viele Bytes gespeichert

_*AÉ vU}c

Testen Sie es online! Bei größeren Eingängen kann dies einige Sekunden dauern.

Erläuterung

_  *AÉ  vU}c    Implicit: U = input integer
Z{Z*A-1 vU}c    Ungolfed
Z{        }c    Loop through each integer Z in [0, -1, 1, -2, ...] and yield the first where
  Z*A             Z times 10
     -1           minus 1
        vU        is divisible by the input.
                Implicit: output result of last expression

Java 8, 23 21 Bytes

n->3/(n%5*2-5)*++n/10

Port der Antwort von @Neil auf JavaScrip (ES6) , aber -2 Byte dank @Nevay aufgrund impliziter Ganzzahlen.

Probieren Sie es hier aus.

Pyke , 12 Bytes

3Q5%}5-f*hTf

Probieren Sie es hier aus!

Pyth , 14 Bytes

h/*x-y%QK5K2QT

Probieren Sie es hier aus.

Python 2 , 44 43 Bytes

( Durchgestrichene 44 sind immer noch 44.) Danke an Fireflame241 für das Speichern eines Bytes!

P=input();i=P/3
while i*10%P-1:i-=1
print i

Probieren Sie es online!

Es gibt genau eine Zahl zwischen 0und P-1die ist eine Umkehrung von 10. Wenn diese Inverse ujedoch größer als ist P/2, (u-P)ist sie auch invers und hat einen kleineren absoluten Wert als u. Es stellt sich also heraus, dass wir wirklich nach der eindeutigen Zahl xzwischen -P/2und suchen, die P/2umgekehrt ist 10.

Der obige Code tut genau das, beginnend bei (dem Boden von) P/2und schrittweise nach unten, bis eine Umkehrung erreicht ist. Dies muss für eine Zahl geschehen, die größer als ist -P/2, solange Peine Primzahl größer als ist 10. Genauer gesagt, es wird genau dann beendet, wenn PCoprime an ist 10.

Edit: Es stellt sich tatsächlich heraus, dass xes garantiert zwischen -P/3und liegt P/3, also beginnt die aktuelle Version bei P/3und geht von dort aus weiter. Eine Erklärung hierzu finden Sie im Abschnitt Verbesserte Bindung .

Mathematische Erklärung

Mir war nicht sofort klar, warum der Teilbarkeitstest funktioniert hat. Hier ist eine Erklärung für den Fall, dass sich jemand anderes wundert.

Sei Peine Primzahl, größer als 10, deren letzte Ziffer ist b. Somit

P = 10a + b

wo a > 0und 0 <= b < 10. In der Tat bist entweder 1, 3, 7, oder 9, weil eine Primzahl größer als 10Muss Ende in einen dieser Stellen.

Nun nimm an bx + a = 0 (mod P). Dann

a = -bx (mod P)

10a + b = 10(-bx) + b (mod P)

0 = 10(-bx) + b (mod P)

0 = b(1 - 10x) (mod P)

Schon seit P es sich um eine Primzahl handelt, sind die ganzen Zahlen mod Peine integrale Domäne . Also entweder b = 0 (mod P)oder 1 - 10x = 0 (mod P).

Wir wissen 0 <= b < 10 < P, also wenn b = 0 (mod P)dann b = 0. Aber wir sagten , bist entweder 1, 3, 7, oder9 , so dass dies unmöglich ist. Deshalb 1 - 10x = 0 (mod P)so 10x = 1 (mod P). Mit anderen Worten, xist das Gegenteil von 10Modulo P.

Angenommen, es Nhandelt sich um eine nichtnegative Ganzzahl, deren letzte Ziffer lautet d. N = 10c + d. Wir haben also eine Kette von äquivalenten Anweisungen:

10c + d = 0 (mod P)

<==> 10xc + dx = 0 (mod P)

<==> c + dx = 0 (mod P)

QED.

Nützlichkeit?

Ich habe mich auch gefragt, ob der Teilbarkeitstest (gegeben N = 10c + d, ersetzt)N durch dx + c) in der Praxis tatsächlich produktiv sein würde. Oder zumindest, ersetzt es zuverlässig Ndurch eine Zahl, die kleiner als N(in absoluten Zahlen ) ist?

Angenommen N = 10c + d, wo c >= 0und 0 <= d < 10. Deshalb 10c = N - d <= N. Durch das Dreieck Ungleichung

|c + dx| <= |c| + |dx| = c + d|x| <= N/10 + d|x|

< N/10 + 10|x| <= N/10 + 10P/2 = N/10 + 5P

Also wenn 5P <= 9N/10 , dann |c + dx| < N.

Insbesondere wenn N >= 6P, dann |c + dx| < N. Somit gegeben Pwir durch die Berechnung beginnen 2P, 3P..., 6Pzusammen mit x. Dann führen Nwir den Teilbarkeitstest wiederholt durch, bis wir eine Zahl kleiner oder gleich erreichen 6P, und prüfen, ob das Ergebnis eine der Zahlen 0ist.P , 2P, ..., 6P.

(Wenn wir eine negative Zahl erreichen, ersetzen wir sie natürlich durch ihren absoluten Wert. Das ist in Ordnung, da qes Pnur dann teilbar ist, wenn dies der Fall (-q)ist.)

Verbesserte Bindung

Mir ist aufgefallen, dass das |x|/Pnie nah zu sein schien 1/2. Tatsächlich schien es immer weniger zu sein als 1/3... oder bei näherer Betrachtung war es immer sehr nah an entweder 1/10oder 3/10. Der größte, den es je gab, schien zu sein 4/13(was passiert, wenn P=13und x=4). Warum sollte das so sein?

Lassen Sie ueine ganze Zahl sein , und nehmen wir an, dass 10u = kP + 1für eine ganze Zahl k, so uist eine Umkehrung von 10Modulo P. Dann wissen wir auch, dass dies krelativ primär ist 10, da k(-P)es gleichbedeutend mit 1Modulo ist 10.

Jetzt wissen wir, dass sich die Inversen von 10Modulo Palle um ein Vielfaches von Punterscheiden. Wir können also die ganze Zahl nehmen uund ein Vielfaches von Pnach Belieben addieren oder subtrahieren , und das Ergebnis ist immer noch eine Inverse von 10Modulo P. Nehmen wir an, wir subtrahieren Pvon u: wir bekommen

10(u - P) = 10u - 10P = kP + 1 - 10P

10(u - P) = (k - 10)P + 1

Mit anderen Worten, das Verringern (bzw. Erhöhen) uum Pentspricht dem Verringern (Erhöhen) kum 10. Wir möchten ein Vielfaches von Pvon addieren / subtrahieren, ubis der absolute Wert der linken Seite minimiert ist. Die linke Seite wird jedoch genau dann minimiert, wenn die rechte Seite minimiert wird, und daher möchten wir addieren / subtrahieren10 aus , kbis die rechte Seite wird in Absolutwert minimiert.

Aber wir wissen , dass dies geschehen wird , wenn kzwischen -5und 5, und daher (da krelativ prim zu 10) bedeutet dies kentweder -3, -1, 1, oder3 . (Dies ist der Inhalt von @ Neils Kommentar unter dem OP. Danke, Neil! )

Wenn somit |u|minimiert wird (dh u=x), wir haben x/P = u/P = k/10 + 1/(10P), wo kentweder -3, -1, 1, oder 3. Deshalb|x|/P <= 3/10 + 1/(10P) . Äquivalent |x| <= (3P + 1)/10.

Außerdem ist diese Ungleichung streng P=11, weil P=11wir x=-1und haben k=-1. Das kleinste, Pfür das Gleichheit gilt, ist P=13(wo x=4und k=3).

Daher ist der größte, der |x|/Pjemals erhalten wird 3/10 + 1/(10*13), weil P=13es die erste Primzahl ist, für die wir haben k=3, und unter denen mit k=3, ist der 1/(10P)Begriff am größten, wenn er Pam kleinsten ist (dh bei P=13). Deshalb Phaben wir für alle auch|x|/P <= 3/10 + 1/130 = 4/13 < 1/3 . Dies erklärt, warum wir im obigen Code bei initialisieren können, i = P/3anstatt bei beginnen zu müssen P/2.

Weiter die Grenzen im Nützlichen obigen Abschnitt jetzt verbessert werden.

Lemma : Lass N = 10c + dwo c > 0und0 <= d <= 9 . Dann c + d|x| < N/10 + 9(3P + 1)/10. (Beachten Sie die strikte Ungleichung.)

Beweis von Lemma: durch Fälle. Fall I: d = 0AlsoN = 10c . Dann c + d|x| = c = N/10 < N/10 + 9(3P + 1)/10.

Fall II: 0 < d <= 9. Dann 10c = N - d < Nalso c < N/10. Deshalb c + d|x| < N/10 + d|x| <= N/10 + 9|x| <= N/10 + 9(3P + 1)/10. QED.

Also, wenn N > 3P(und N = 10c + dwie zuvor), dann

3P + 1 <= N

9(3P + 1)/10 <= 9N/10

N/10 + 9(3P + 1)/10 <= N

c + d|x| < N/10 + 9(3P + 1)/10 <= N

Also, wenn N > 3Pdann c + d|x| < N.

Deshalb müssen wir nur finden P, 2Pund 3P, zusammen mit x. Gegeben N > 0, während N > 3Pwir ersetzen Ndurch |c + dx|, die abnimmt N. Irgendwann werden wir bekommen N <= 3P; stoppen und prüfen , ob an diesem Punkt uns Nauf eine der Zahlen gleich 0, P, 2P, oder 3P.

Wir können es nicht besser machen als 3Pim Allgemeinen. Nehmen wir zum Beispiel an, P = 13und N = 39so x = 4. Dann Ndurch unveränderte dx + c = 9(4) + 3Blätter ersetzen N.

Leerzeichen , 92 Bytes

Beachten Sie, dass die Syntax dieser Sprache nur aus Leerzeichen besteht. Daher wurde jedem Leerzeichen hier S, T oder L vorangestellt (entsprechend Leerzeichen, Tabulator bzw. Zeilenvorschub). Diese können entfernt werden, ohne dass die Funktionalität verloren geht. Sie sind jedoch hier enthalten, damit sie korrekt angezeigt werden.

S S S L
T   L
T   T   S S S L
T   T   T   S L
S S S S T   T   L
T   S S L
S L
T   S S S T S T L
T   S T T   S L
S T S S S S S S T   S T L
T   S S T   T   S T S S S S T   L
T   S S S S S S T   S T S L
T   S T S T L
S T L
L
L
.

Probieren Sie es online!

Japt , 14 Bytes

Inspiriert von Neils Lösung .

Ì*2%E-3 *UÄ /A

Online testen!

Erläuterung:

  Ì  *2%E-3 *UÄ  /A
((UgJ*2%E-3)*U+1)/A
  U                  // Implicit U = Input
   gJ                // Get the char at index -1 (last char)
     *2              // Multiply by 2
       %E            // Mod 14
         -3          // Minus 3
            *U+1     // Multiply by U+1
                 /A  // Divided by 10 

Pyke , 10 Bytes

~IIT*tR%)h

Probieren Sie es hier aus!

~I         -   Integers
  I     )  -  filter(^, not v)
   T*t     -    ^ *10 -1
      R%   -   input % ^
         h - ^[0]

Excel, 27 Bytes

=0.3/(MOD(A1,5)*2-5)*A1+0.1

Könnte in Cell als eingegeben werden

=.3/(MOD(A1,5)*2-5)*A1+.1

für 25 Bytes, aber Excel-Auto-Updates.