Dado un primo Pmayor que 10, su programa o función debe calcular su regla de divisibilidad x, definida como el número entero con el valor absoluto más pequeño que produce un múltiplo del primo original cuando se multiplica por el último dígito del primo y se agrega al resto del original. principal.

Ejemplo

Dada una entrada 31, el último dígito es 1y el resto del número es 3. Por lo tanto, su programa debe encontrar el número entero xcon un valor absoluto mínimo tal que 1*x + 3sea ​​un múltiplo de 31. En este caso, x=-3funciona, por lo que el programa o función volvería -3.

Dada una entrada 1000003, el último dígito es 3y el resto del número es 100000. Por lo tanto su programa encontraría x=300001ya 3*300001+100000 = 1000003que es un múltiplo de 1000003.

Antecedentes matemáticos

El valor de xse puede usar como prueba de divisibilidad. Si un número Nes divisible por P, entonces al sumar xveces el último dígito de Nal resto de, se Nobtendrá un múltiplo de Pif y only if Nes divisible por Pen primer lugar.

Para P=11, obtenemos x=-1, que es equivalente a la conocida regla de divisibilidad para 11: un número es divisible por 11la diferencia alterna de sus dígitos es divisible por 11.

Reglas

• La salida puede tener cualquier forma que codifique claramente tanto el signo como el valor de la salida.
• El primo de entrada estará entre 10 y 2 ^ 30.
• No necesita manejar si la entrada no es un primo o no está en el rango.
• No es necesario que si ambos mango xy -xson salidas válidas (no debería suceder).
• Se permite la fuerza bruta, pero se aprecian soluciones más creativas.
• Este es el código de golf , por lo que gana el código más corto en cada idioma . No permita que las respuestas en los idiomas de golf lo desalienten a publicar en otros idiomas.

Casos de prueba

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 bytes

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)se escribiría 9/n(mod -10)si tuviera acceso a una división de módulo equilibrada. Editar: Guardado 2 bytes gracias a @EgorSkriptunoff

Python 2 , 27 bytes

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

Pruébalo en línea!

Las operaciones se realizan izquierda a derecha: (((n%5)*2)-5)^2.

Utilicé mi fuerza bruta aritmética para encontrar la expresión n%5*2-5^2a realizar {1:-1,3:3,2:-3,4:1}[k], tomando el inverso negativo de un mod de residuo 5 en el rango [-2..2].

jalea ,10 8 bytes

,N⁵æiAÞḢ

Pruébalo en línea!

Explicaciones

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

Brachylog , 14 bytes

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

Pruébalo en línea!

Python 2 , 69 54 53 bytes

Editar: -15 bytes gracias a @ Mr.Xcoder

Editar: -1 byte usando recursividad

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

Pruébalo en línea!

Python 2 , 31 29 27 bytes

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

Pruébalo en línea!

Japt , 16 9 bytes

Se guardaron demasiados bytes gracias a una observación de @xnor

_*AÉ vU}c

¡Pruébalo en línea! Puede tomar un par de segundos en entradas más grandes.

Explicación

_  *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

Puerto de la respuesta JavaScrip (ES6) de @Neil , pero -2 bytes gracias a @Nevay debido a un piso implícito de enteros.

Pruébalo aquí

Pyke , 12 bytes

3Q5%}5-f*hTf

Pruébalo aquí!

Pyth , 14 bytes

h/*x-y%QK5K2QT

Pruébalo aquí

Python 2 , 44 43 bytes

(Tachado 44 sigue siendo 44.) ¡ Gracias a Fireflame241 por guardar un byte!

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

Pruébalo en línea!

Hay exactamente un número entre 0y P-1que es un inverso de 10. Pero si ese inverso ues mayor que P/2, entonces (u-P)también es inverso y tiene un valor absoluto menor que u. Resulta que realmente estamos buscando el número único xentre -P/2yP/2 que es un inverso de 10.

El código anterior hace exactamente eso, comenzando en (el piso de) P/2y bajando hasta alcanzar un inverso. Esto debe suceder para un número mayor que -P/2mientras Psea ​​un primo mayor que 10. Más precisamente, terminará si y solo si Pes coprime para10 .

Editar: en realidad resulta que xestá garantizado entre -P/3y P/3, por lo que la versión actual comienza en P/3y baja desde allí. Ver la sección etiquetada Mejorado vinculado para obtener una explicación de esto.

Explicación matemática

No fue inmediatamente obvio para mí por qué funcionó la prueba de divisibilidad. Aquí hay una explicación, en caso de que alguien más se preguntara.

Sea Pun primo, mayor que 10, cuyo último dígito es b. Así

P = 10a + b

donde a > 0y 0 <= b < 10. De hecho bes o bien 1, 3, 7, o 9, a causa de una mayor prime10 final necesidad en uno de estos dígitos.

Ahora supongamos bx + a = 0 (mod P). Luego

a = -bx (mod P)

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

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

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

Como Pes primo, los enteros mod Pson un dominio integral . Entonces b = 0 (mod P), o 1 - 10x = 0 (mod P).

Sabemos 0 <= b < 10 < P, por lo que si b = 0 (mod P)a continuación b = 0. Pero dijimos bestá bien 1, 3, 7, o 9, por lo que esto es imposible. Por 1 - 10x = 0 (mod P)lo tanto , entonces 10x = 1 (mod P). En otras palabras, xes el inverso de 10, módulo P.

Ahora suponga que Nes un entero no negativo cuyo último dígito es d, por N = 10c + d. lo que tenemos una cadena de declaraciones equivalentes:

10c + d = 0 (mod P)

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

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

QED

¿Utilidad?

También me preguntaba si la prueba de divisibilidad (dada N = 10c + d, reemplazada Npor dx + c) sería realmente productiva en la práctica. O al menos, ¿se reemplaza confiablemente Npor un número menor que N(en valor absoluto)?

Supongamos N = 10c + d, donde c >= 0y 0 <= d < 10. Por lo tanto 10c = N - d <= N. Por la desigualdad del triángulo,

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

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

Entonces si 5P <= 9N/10, entonces |c + dx| < N.

En particular, si N >= 6P, entonces |c + dx| < N. Por lo tanto, dado Pque comenzamos calculando 2P, 3P, ..., 6P, junto con x. Entonces dado N, corremos el test de la divisibilidad en repetidas ocasiones hasta llegar a un número menor o igual a 6P, y comprobar si el resultado es cualquiera de los números 0, P, 2P, ..., 6P.

(Por supuesto, cada vez que alcanzamos un número negativo, lo reemplazamos por su valor absoluto, lo cual está bien ya que qes divisible por Psi y solo si lo (-q)es).

Límite mejorado

Me di cuenta de que |x|/Pnunca parecía estar cerca 1/2. De hecho, parecía que siempre era menor que 1/3... o, al examinarlo más de cerca, siempre estaba muy cerca de uno 1/10u otro 3/10. El más grande que haya tenido parece ser 4/13(lo que sucede cuando P=13y x=4). ¿Por qué sería esto?

Deje user un número entero y suponga que 10u = kP + 1para algún número entero k, también lo ues un 10módulo inverso P. Entonces también sabemos que kes relativamente primo 10, ya que k(-P)es equivalente al 1módulo 10.

Ahora, sabemos que todas las inversas del 10módulo Pdifieren en múltiplos de P, por lo que podemos tomar el número entero uy sumar o restar múltiplos Pa voluntad, y el resultado siempre será un inverso del 10módulo P. Supongamos que elegimos restar Pde u: obtenemos

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

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

En otras palabras, la disminución (respectivamente, aumentando) upor Pcorresponde a la disminución (en aumento) kpor 10. Queremos añadir / restar múltiplos de Ppartir uhasta que el lado izquierdo se reduce al mínimo en valor absoluto; pero el lado izquierdo se minimiza exactamente cuando se minimiza el lado derecho, y así queremos añadir / restar 10dek hasta que el lado derecho se reduce al mínimo en valor absoluto.

Pero sabemos que esto sucederá cuando kestá entre -5y 5, y por lo tanto (ya que kes relativamente primos a 10) este medio kes o bien -3, -1, 1, o 3. (Este es el contenido del comentario de @ Neil bajo el OP. ¡ Gracias, Neil! )

Así, cuando |u|se reduce al mínimo (es decir, u=x), tendremos x/P = u/P = k/10 + 1/(10P), donde kes o bien -3, -1, 1, o 3. Por lo tanto |x|/P <= 3/10 + 1/(10P). De manera equivalente, |x| <= (3P + 1)/10.

Además, esta desigualdad es estricta en P=11, porque en P=11tenemos x=-1y k=-1. El más pequeño Ppara el que se cumple la igualdad es P=13(dónde x=4y k=3).

Por lo tanto, el más grande que |x|/Pse obtiene es 3/10 + 1/(10*13), porque P=13es el primer primo para el que tenemos k=3, y entre aquellos con k=3, el 1/(10P)término es más grande cuando Pes más pequeño (es decir, en P=13). Por lo tanto, para todos P, también tenemos |x|/P <= 3/10 + 1/130 = 4/13 < 1/3. Esto explica por qué en el código anterior podemos inicializar en i = P/3lugar de tener que comenzar enP/2 .

Además, los límites en la utilidad sección de anterior ahora se pueden mejorar.

Lema : Dejar N = 10c + ddónde c > 0y 0 <= d <= 9. Luegoc + d|x| < N/10 + 9(3P + 1)/10 . (Tenga en cuenta la estricta desigualdad).

Prueba de Lemma: por casos. Caso I: d = 0entonces N = 10c. Luegoc + d|x| = c = N/10 < N/10 + 9(3P + 1)/10 .

Caso II: 0 < d <= 9. Entonces 10c = N - d < N, entonces c < N/10. Por lo tantoc + d|x| < N/10 + d|x| <= N/10 + 9|x| <= N/10 + 9(3P + 1)/10 . QED

Por lo tanto, si N > 3P(y N = 10c + dcomo antes), entonces

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

Entonces, si N > 3Pentonces c + d|x| < N.

Por lo tanto, solo tenemos que encontrar P, 2Py 3P, junto con x. Dado N > 0, mientras N > 3P, reemplazamos Npor |c + dx|, lo que disminuye N. Finalmente lo conseguiremos N <= 3P; en ese punto nos detenemos y comprobar si Nes igual a cualquiera de los números 0, P, 2P, o 3P.

No podemos hacerlo mejor que 3Pen general. Por ejemplo, supongamos P = 13y N = 39, entonces x = 4. Luego reemplazando Npor dx + c = 9(4) + 3hojas Nsin cambios.

Espacio en blanco , 92 bytes

Tenga en cuenta que la sintaxis de este lenguaje consiste solo en espacios en blanco , por lo que cada carácter de espacio en blanco se ha prefijado aquí con S, T o L (correspondiente a Espacio, Tabulación y Salto de línea, respectivamente). Estos se pueden eliminar sin perder la funcionalidad, pero se incluyen aquí para mostrarlos correctamente.

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
.

Pruébalo en línea!

Japt , 14 bytes

Inspirado en la solución de Neil .

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

¡Pruébelo en línea!

Explicación:

  Ì  *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

Pruébalo aquí!

~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

Podría ingresarse en la celda como

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

para 25 bytes, pero Excel se actualiza automáticamente.