Biorąc pod uwagę liczbę pierwszą Pwiększą niż 10, twój program lub funkcja musi ustalić zasadę podzielnościx liczbę , zdefiniowaną jako liczba całkowita o najmniejszej wartości bezwzględnej, która daje wielokrotność pierwotnej liczby pierwszej, pomnożonej przez ostatnią cyfrę liczby pierwszej i dodanej do reszty oryginału główny.

Przykład

Biorąc pod uwagę 31, ostatnia cyfra to, 1a reszta liczby to 3. Dlatego twój program musi znaleźć liczbę całkowitą xo minimalnej wartości bezwzględnej, która 1*x + 3jest wielokrotnością 31. W takim przypadku x=-3działa, więc program lub funkcja powróci -3.

Biorąc pod uwagę 1000003, ostatnia cyfra to, 3a reszta liczby to 100000. W ten sposób Twój program znajdzie, x=300001ponieważ 3*300001+100000 = 1000003jest to wielokrotność1000003 .

Tło matematyczne

Wartość xmożna wykorzystać jako test podzielności. Jeśli liczba Njest podzielna przez P, to dodanie xczasów ostatniej cyfry Ndo reszty Nda wielokrotność Pif i tylko jeśli Njest podzielna przez P.

Dla P=11otrzymujemy x=-1, który jest odpowiednikiem znanego cecha podzielności przez 11: liczba jest podzielna przez 11różnicę przemiennym jej cyfr jest podzielna przez 11.

Zasady

• Dane wyjściowe mogą być w dowolnej formie, która wyraźnie koduje zarówno znak, jak i wartość wyniku.
• Liczba wejściowa będzie wynosić między 10 a 2 ^ 30.
• Nie trzeba obsługiwać, jeśli dane wejściowe nie są liczbą pierwszą lub nie znajdują się w zakresie.
• Nie trzeba do uchwytu, gdy oba xi -xsą ważne wyjścia (nie powinno się zdarzyć).
• Brutalna siła jest dozwolona, ​​ale bardziej kreatywne rozwiązania są doceniane.
• To jest golf golfowy , więc wygrywa najkrótszy kod w każdym języku ! Nie pozwól, aby odpowiedzi w językach golfowych zniechęcały Cię do publikowania postów w innych językach.

Przypadki testowe

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 bajtów

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)napisałbym, 9/n(mod -10)gdybym miał dostęp do zrównoważonego podziału modulo. Edycja: Zapisano 2 bajty dzięki @EgorSkriptunoff

Python 2 , 27 bajtów

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

Wypróbuj online!

Operacje są wykonywane od lewej do prawej: (((n%5)*2)-5)^2 .

Użyłem mojego arytmetycznego brutalnego forcera, aby znaleźć wyrażenie n%5*2-5^2do wykonania {1:-1,3:3,2:-3,4:1}[k], przyjmując ujemną odwrotność reszty mod 5 w zakresie [-2..2].

Galaretka ,10 8 bajtów

,N⁵æiAÞḢ

Wypróbuj online!

Objaśnienia

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

Brachylog , 14 bajtów

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

Wypróbuj online!

Python 2 , 69 54 53 bajtów

Edycja: -15 bajtów dzięki @ Mr.Xcoder

Edytuj: -1 bajt za pomocą rekurencji

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

Wypróbuj online!

Python 2 , 31 29 27 bajtów

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

Wypróbuj online!

Japt , 16 9 bajtów

Zaoszczędzono o wiele za dużo bajtów dzięki obserwacji @xnor

_*AÉ vU}c

Przetestuj online! Przy większych nakładach może to potrwać kilka sekund.

Wyjaśnienie

_  *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 bajtów

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

Port odpowiedzi JavaScrip (ES6) @Neil , ale -2 bajty dzięki @Nevay z powodu niejawnej podłogi liczb całkowitych.

Wypróbuj tutaj.

Pyke , 12 bajtów

3Q5%}5-f*hTf

Wypróbuj tutaj!

Pyth , 14 bajtów

h/*x-y%QK5K2QT

Wypróbuj tutaj.

Python 2 , 44 43 bajty

(Przekreślone 44 to wciąż 44.) Dzięki Fireflame241 za uratowanie bajtu!

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

Wypróbuj online!

Jest dokładnie jedna liczba pomiędzy 0i P-1która jest odwrotnością 10. Ale jeśli ta odwrotność ujest większa niż P/2, to (u-P)jest również odwrotnością i ma mniejszą wartość bezwzględną niż u. Okazuje się więc, że naprawdę szukamy unikalnej liczby xpomiędzy -P/2i P/2która jest odwrotnością 10.

Powyższy kod robi dokładnie to, zaczynając od (najniższy poziom) P/2i schodząc w dół, aż do osiągnięcia odwrotności. To musi się zdarzyć dla pewnej liczby większej niż -P/2tak długo, jak liczba Ppierwsza jest większa niż 10. Mówiąc dokładniej, zakończy się wtedy i tylko wtedy, gdy Pjest chroniony prawem autorskim 10.

Edycja: Okazuje się, że xna pewno jest pomiędzy -P/3i P/3, więc bieżąca wersja zaczyna się od P/3i schodzi z tego miejsca. Wyjaśnienie tego znajduje się w sekcji „ Poprawiona granica” .

Wyjaśnienie matematyczne

Nie od razu zrozumiałem, dlaczego zadziałał test podzielności. Oto wyjaśnienie, na wypadek gdyby ktoś się zastanawiał.

Niech Pbędzie liczbą pierwszą, większą niż 10, której ostatnią cyfrą jest b. A zatem

P = 10a + b

gdzie a > 0i 0 <= b < 10. W rzeczywistości bjest albo 1, 3, 7, lub 9, z powodu doskonałej większy niż 10końcowy musi w jednej z tych cyfr.

Załóżmy teraz bx + a = 0 (mod P). Następnie

a = -bx (mod P)

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

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

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

Ponieważ Pjest liczbą pierwszą, liczby całkowite mod Psą domeną integralną . Więc albo b = 0 (mod P), albo 1 - 10x = 0 (mod P).

Wiemy 0 <= b < 10 < P, więc jeśli b = 0 (mod P)potem b = 0. Ale my powiedzieliśmy balbo jest 1, 3, 7, lub 9, więc jest to niemożliwe. Dlatego 1 - 10x = 0 (mod P)tak 10x = 1 (mod P). Innymi słowy, xjest odwrotnością 10modulo P.

Załóżmy teraz, że Njest nieujemną liczbą całkowitą, której ostatnia cyfra to d, więc N = 10c + d. mamy łańcuch równoważnych instrukcji:

10c + d = 0 (mod P)

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

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

CO BYŁO DO OKAZANIA.

Przydatność?

Zastanawiałem się również, czy test podzielności (podany N = 10c + d, zastąpiony Nprzez dx + c) rzeczywiście byłby produktywny w praktyce. Czy przynajmniej rzetelnie zastępuje Ngo liczbą mniejszą niż N(w wartości bezwzględnej)?

Załóżmy N = 10c + d, gdzie c >= 0i 0 <= d < 10. W związku z tym 10c = N - d <= N. Przez nierówność trójkąta

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

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

Jeśli więc 5P <= 9N/10to |c + dx| < N.

W szczególności, jeśli N >= 6P, to |c + dx| < N. Tak więc, biorąc pod uwagę Pzaczynamy od obliczenia 2P, 3P, ..., 6Pwraz z x. Następnie podano N, prowadzimy wielokrotnie test podzielności aż osiągniemy liczbę mniejszą niż lub równy 6P, i sprawdzić, czy wynik jest każda z liczb 0, P, 2P, ..., 6P.

(Oczywiście, ilekroć osiągniemy liczbę ujemną, zastępujemy ją wartością bezwzględną, co jest w porządku, ponieważ qmożna ją podzielić przez „ Ptylko i tylko jeśli” (-q)).

Ulepszona granica

Zauważyłem, że |x|/Pnigdy nie było tak blisko 1/2. W rzeczywistości wydawało się, że zawsze było mniej niż 1/3... lub po bliższym zbadaniu, był zawsze bardzo blisko albo 1/10albo 3/10. Wydawało się, że jest ono największe 4/13(co dzieje się, kiedy P=13i x=4). Dlaczego miałoby to być?

Niech ubędzie liczbą całkowitą i załóżmy, że 10u = kP + 1dla jakiejś liczby całkowitej k, tak ujest odwrotnie 10, modulo P. Wiemy również, że kjest to względnie pierwszy 10, ponieważ k(-P)jest równoważne 1modulo 10.

Teraz wiemy, że wszystkie odwrotności 10modulo Próżnią się wielokrotnościami P, więc możemy wziąć liczbę całkowitą ui dodawać lub odejmować wielokrotności według Pwoli, a wynik zawsze będzie odwrotnością 10modulo P. Załóżmy, że zdecydujemy się odjąć Pod u: otrzymujemy

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

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

Innymi słowy, zmniejszenie (odpowiednio zwiększenie) uo Podpowiada zmniejszeniu (wzrost) ko 10. Chcemy dodawać / odejmować wielokrotności Pod, uaż lewa strona zostanie zminimalizowana w wartości bezwzględnej; ale po lewej stronie jest dokładnie zminimalizowane, gdy po prawej stronie jest zminimalizowane, a więc chcemy dodać / odjąć 10od kdopóki po prawej stronie jest minimalizowane w wartości bezwzględnej.

Ale wiemy, że to się stanie, gdy kjest między -5i 5, a więc (ponieważ kjest stosunkowo prime do 10) to oznacza kto albo -3, -1, 1, lub 3. (To jest treść komentarza @ Neil w OP. Dzięki, Neil! )

Tak więc, gdy |u|jest zminimalizowany (tj u=x), będziemy mieć x/P = u/P = k/10 + 1/(10P), gdzie kjest albo -3, -1, 1, lub 3. W związku z tym |x|/P <= 3/10 + 1/(10P). Odpowiednio |x| <= (3P + 1)/10.

Co więcej, nierówność ta jest surowa w P=11, ponieważ w P=11mamy x=-1i k=-1. Najmniejsze, Pdla którego obowiązuje równość, to P=13(gdzie x=4i k=3).

Dlatego największa, |x|/Pjaka kiedykolwiek dostaje, jest 3/10 + 1/(10*13), ponieważ P=13jest to pierwsza liczba pierwsza, dla której mamy k=3, a wśród tych z k=3, 1/(10P)termin jest największy, gdy Pjest najmniejszy (tj. At P=13). Dlatego też wszyscy Pmamy |x|/P <= 3/10 + 1/130 = 4/13 < 1/3. To wyjaśnia, dlaczego w powyższym kodzie możemy zainicjować o, i = P/3zamiast zaczynać od P/2.

Ponadto można teraz poprawić granice w powyższej sekcji Przydatność .

Lemma : Niech N = 10c + dgdzie c > 0i 0 <= d <= 9. Potem c + d|x| < N/10 + 9(3P + 1)/10. (Zwróć uwagę na ścisłą nierówność.)

Dowód lematu: według przypadków. Przypadek I: d = 0tak N = 10c. Potem c + d|x| = c = N/10 < N/10 + 9(3P + 1)/10.

Przypadek II: 0 < d <= 9. Więc 10c = N - d < Ntak c < N/10. W związku z tym c + d|x| < N/10 + d|x| <= N/10 + 9|x| <= N/10 + 9(3P + 1)/10. CO BYŁO DO OKAZANIA.

Zatem jeśli N > 3P (i N = 10c + djak poprzednio), to

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

Więc jeśli N > 3Ptak c + d|x| < N.

Dlatego też, musimy tylko znaleźć P, 2Pa 3Pwraz z x. Biorąc pod uwagę N > 0, natomiast N > 3P, możemy zastąpićN przez |c + dx|, co zmniejsza N. W końcu dostaniemy N <= 3P; W tym momencie możemy zatrzymać się i sprawdzić, czy Njest równa żadnej z liczb 0, P, 2P, lub 3P.

Nie możemy zrobić nic lepszego niż 3Pogólnie. Załóżmy na przykład P = 13i N = 39takx = 4 . Następnie zastąpione Nprzez dx + c = 9(4) + 3liście Nbez zmian.

Biała spacja , 92 bajty

Zauważ, że składnia tego języka składa się tylko z białych znaków , więc każdy znak białych znaków ma tutaj przedrostek S, T lub L (odpowiednio odpowiednio Spacja, Tab i Przesuw wiersza). Można je usunąć bez utraty funkcjonalności, ale są tu zawarte w celu poprawnego wyświetlenia.

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
.

Wypróbuj online!

Japt , 14 bajtów

Zainspirowany rozwiązaniem Neila .

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

Przetestuj online!

Wyjaśnienie:

  Ì  *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 bajtów

~IIT*tR%)h

Wypróbuj tutaj!

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

Excel, 27 bajtów

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

Można wprowadzić do komórki jako

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

dla 25 bajtów, ale automatyczne aktualizacje programu Excel.