Dado um primo Pmaior que 10, seu programa ou função deve descobrir sua regra de divisibilidade x, definida como o número inteiro com o menor valor absoluto, que gera um múltiplo do primo original quando multiplicado pelo último dígito do primo e adicionado ao restante do original. prime.

Exemplo

Dada uma entrada 31, o último dígito é 1e o restante do número é 3. Portanto, seu programa deve encontrar o número inteiro xcom valor absoluto mínimo, de modo que 1*x + 3seja múltiplo de 31. Nesse caso, x=-3funciona, para que o programa ou função retorne -3.

Dada uma entrada 1000003, o último dígito é 3e o restante do número é 100000. Assim, seu programa encontraria x=300001porque 3*300001+100000 = 1000003é um múltiplo de 1000003.

Formação Matemática

O valor de xpode ser usado como um teste de divisibilidade. Se um número Né divisível por P, a adição de xvezes o último dígito de Nao resto de Nproduzirá um múltiplo de Pse e somente se Né divisível por Pem primeiro lugar.

Pois P=11, entendemos x=-1, que é equivalente à conhecida regra de divisibilidade para 11: um número é divisível pela 11diferença alternada de seus dígitos é divisível por 11.

Regras

• A saída pode estar em qualquer forma que codifique claramente o sinal e o valor da saída.
• O primo de entrada estará entre 10 e 2 ^ 30.
• Você não precisa manipular se a entrada não for primária ou não estiver no intervalo.
• Você não precisa lidar com se ambos xe -xsão saídas válidas (não deve acontecer).
• A força bruta é permitida, mas soluções mais criativas são apreciadas.
• Isso é código-golfe , então o código mais curto em cada idioma vence! Não permita que respostas em idiomas de golfe o desencorajem de postar em outros idiomas.

Casos de teste

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)seria escrito 9/n(mod -10)se eu tivesse acesso à divisão de módulos equilibrada. Edit: Salvo 2 bytes graças a @EgorSkriptunoff

Python 2 , 27 bytes

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

Experimente online!

As operações são feitas esquerda para a direita: (((n%5)*2)-5)^2.

Eu usei meu forcador bruto aritmético para encontrar a expressão n%5*2-5^2para executar{1:-1,3:3,2:-3,4:1}[k] , levando o inverso negativo de um resíduo mod 5 para o intervalo [-2..2].

Gelatina ,10 8 bytes

,N⁵æiAÞḢ

Experimente online!

Explicações

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

Braquilog , 14 bytes

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

Experimente online!

Python 2 , 69 54 53 bytes

Edit: -15 bytes graças a @ Mr.Xcoder

Edit: -1 byte usando recursão

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

Experimente online!

Python 2 , 31 29 27 bytes

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

Experimente online!

Japonês , 16 9 bytes

Salvo muitos bytes graças a uma observação de @xnor

_*AÉ vU}c

Teste online! Pode demorar alguns segundos em entradas maiores.

Explicação

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

Porta da resposta JavaScrip (ES6) do @Neil , mas -2 bytes graças ao @Nevay devido ao revestimento implícito de números inteiros.

Experimente aqui.

Pyke , 12 bytes

3Q5%}5-f*hTf

Experimente aqui!

Pyth , 14 bytes

h/*x-y%QK5K2QT

Experimente aqui.

Python 2 , 44 43 bytes

( Riscado 44 ainda é 44.) Obrigado a Fireflame241 por salvar um byte!

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

Experimente online!

Existe exatamente um número entre 0e do P-1qual é inverso 10. Mas se esse inverso ufor maior que P/2, então (u-P)também será um inverso e terá um valor absoluto menor que u. Assim, verifica-se que estamos realmente olhando para o número único xentre -P/2e P/2que é o inverso da 10.

O código acima faz exatamente isso, começando em (o andar de) P/2e descendo até que um inverso seja alcançado. Isso deve acontecer para um número maior que -P/2o tempo que Pé um primo maior que 10. Mais precisamente, ele terminará se e somente se Pfor coprime para 10.

Editar: Na verdade, xé garantido que está entre -P/3e P/3, portanto, a versão atual começa em P/3e desce a partir daí. Consulte a seção Limite aprimorado para obter uma explicação sobre isso.

Explicação matemática

Não ficou imediatamente óbvio para mim por que o teste de divisibilidade funcionou. Aqui está uma explicação, caso alguém mais esteja se perguntando.

Deixei P Ser um primo, maior que 10, cujo último dígito é b. portanto

P = 10a + b

em que a > 0, e 0 <= b < 10. Na verdade bé tanto 1,3 , 7ou 9, porque uma maior nobre do que10 final must em um desses dígitos.

Agora suponha bx + a = 0 (mod P). Então

a = -bx (mod P)

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

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

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

Como Pé primo, os números inteiros mod Psão um domínio integral . Então b = 0 (mod P), ou1 - 10x = 0 (mod P) .

Nós sabemos 0 <= b < 10 < P, então se b = 0 (mod P)então b = 0. Mas nós dissemos bé ou 1, 3, 7ou 9, então isso é impossível. Portanto 1 - 10x = 0 (mod P), então10x = 1 (mod P) . Em outras palavras, xé o inverso do 10módulo P.

Agora, suponha que Nseja um número inteiro não negativo cujo último dígito seja d, portanto, N = 10c + d. temos uma cadeia de instruções equivalentes:

10c + d = 0 (mod P)

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

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

QED.

Utilidade?

Também estava me perguntando se o teste de divisibilidade (dado N = 10c + d, substituído Npor dx + c) seria realmente produtivo na prática. Ou pelo menos, ele substitui com segurança Npor um número menor que N(em valor absoluto)?

Suponha N = 10c + d, onde c >= 0e 0 <= d < 10. Portanto 10c = N - d <= N. Pela desigualdade do triângulo,

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

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

Assim se 5P <= 9N/10, então |c + dx| < N.

Em particular, se N >= 6P, então |c + dx| < N. Assim, dado Pque começamos calculando 2P, 3P, ..., 6P, juntamente com x. Então dado N, corremos o teste de divisibilidade repetidamente até chegar a um número menor ou igual a 6P, e verificar se o resultado é qualquer um dos números 0, P, 2P, ..., 6P.

(Obviamente, sempre que atingimos um número negativo, o substituímos por seu valor absoluto, o que é bom, pois qé divisível por Pse e somente se(-q) é.)

Limite melhorado

Percebi que |x|/Pnunca parecia estar perto 1/2. Na verdade, parecia que sempre foi menos do que 1/3... ou após um exame mais detalhado, sempre foi muito próximo de um 1/10ou outro 3/10. A maior já parecia ser 4/13(o que acontece quando P=13e x=4). Por que isso seria?

Seja uum número inteiro e suponha que, 10u = kP + 1para algum número inteiro k, o uinverso seja o 10módulo P. Então também sabemos que isso ké relativamente primordial 10, já que k(-P)é equivalente a 1módulo 10.

Agora, sabemos que todos os inversos do 10módulo Pdiferem por múltiplos de P, para que possamos pegar o número inteiro ue adicionar ou subtrair múltiplos Pà vontade, e o resultado sempre será um inverso do 10módulo P. Suponha que nós escolhemos para subtrair Pa partir de u: obtemos

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

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

Em outras palavras, diminuir (respectivamente, aumentar) uem Pcorresponde a diminuir (aumentar) kem 10. Queremos adicionar / múltiplos subtrair de Ppartir uaté que o lado esquerdo é minimizado em valor absoluto; mas o lado esquerdo é minimizado exatamente quando o lado direito é minimizado e, por isso, queremos adicionar / subtrair 10dek até que o lado direito seja minimizado em valor absoluto.

Mas nós sabemos que isso vai acontecer quando kestiver entre -5e 5, e, portanto, (uma vez que ké relativamente privilegiada para 10) este meio ké ou -3, -1, 1ou 3. (Este é o conteúdo do comentário de @ Neil no OP. Obrigado, Neil! )

Assim, quando |u|é minimizado (ou seja, u=x), teremos x/P = u/P = k/10 + 1/(10P), onde ké ou -3, -1, 1ou 3. Portanto |x|/P <= 3/10 + 1/(10P). Equivalentemente |x| <= (3P + 1)/10.

Além disso, essa desigualdade é estrita em P=11, porque em P=11nós temos x=-1e k=-1. O menor Ppara o qual a igualdade é válida P=13(onde x=4e k=3).

Portanto, o maior que |x|/Pjá existe é 3/10 + 1/(10*13), porque P=13é o primeiro primo para o qual temos k=3e, entre aqueles com k=3, o 1/(10P)termo é maior quando Pmenor (ou seja, em P=13). Portanto, para todos P, também temos |x|/P <= 3/10 + 1/130 = 4/13 < 1/3. Isso explica por que, no código acima, podemos inicializar em i = P/3vez de precisar começar emP/2 .

Além disso, os limites na seção Utilidade acima agora podem ser aprimorados.

Lema : Deixe N = 10c + donde c > 0e 0 <= d <= 9. Entãoc + d|x| < N/10 + 9(3P + 1)/10 . (Observe a desigualdade estrita.)

Prova de lema: por casos. Caso I:, d = 0então N = 10c. Entãoc + d|x| = c = N/10 < N/10 + 9(3P + 1)/10 .

Caso II: 0 < d <= 9. Então 10c = N - d < Nsim c < N/10. Portantoc + d|x| < N/10 + d|x| <= N/10 + 9|x| <= N/10 + 9(3P + 1)/10 . QED.

Assim, se N > 3P(e N = 10c + dcomo antes), então

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

Então, se N > 3Pentão c + d|x| < N.

Portanto, só temos de encontrar P, 2Pe 3P, juntamente com x. Dado N > 0, enquanto N > 3P, substituímos Npor |c + dx|, o que diminui N. Eventualmente nós chegaremos N <= 3P; Nesse ponto, parar e verificar se Né igual a qualquer um dos números 0, P, 2P, ou 3P.

Não podemos fazer melhor do que 3Pem geral. Por exemplo, suponha P = 13e N = 39, então x = 4. Em seguida, substituindo Npor dx + c = 9(4) + 3folhas Ninalteradas.

Espaço em branco , 92 bytes

Observe que a sintaxe desse idioma consiste apenas em espaço em branco ; portanto, cada caractere de espaço em branco foi prefixado aqui com S, T ou L (correspondente a Espaço, Tab e Alimentação de linha, respectivamente). Eles podem ser removidos sem perder a funcionalidade, mas são incluídos aqui para serem exibidos corretamente.

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
.

Experimente online!

Japonês , 14 bytes

Inspirado pela solução de Neil .

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

Teste online!

Explicação:

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

Experimente aqui!

~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

Pode ser inserido na célula como

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

para 25 bytes, mas as atualizações automáticas do Excel.