Étant donné un nombre premier Psupérieur à 10, votre programme ou fonction doit comprendre sa règle de divisibilité x, définie comme l'entier avec la plus petite valeur absolue qui donne un multiple du nombre d'origine lorsqu'il est multiplié par le dernier chiffre du nombre premier et ajouté au reste de l'original premier.

Exemple

Étant donné une entrée 31, le dernier chiffre est 1et le reste du nombre est 3. Ainsi, votre programme doit trouver l'entier xavec une valeur absolue minimale telle qu'un 1*x + 3multiple de 31. Dans ce cas, x=-3fonctionne, donc le programme ou la fonction reviendrait -3.

Étant donné une entrée 1000003, le dernier chiffre est 3et le reste du nombre est 100000. Ainsi, votre programme trouverait x=300001car 3*300001+100000 = 1000003qui est un multiple de 1000003.

Contexte mathématique

La valeur de xpeut être utilisée comme test de divisibilité. Si un nombre Nest divisible par P, alors l'ajout de xfois le dernier chiffre de Nau reste de Ndonnera un multiple de Psi et seulement si Nest divisible par Pen premier lieu.

Pour P=11, on obtient x=-1, ce qui équivaut à la règle de divisibilité bien connue pour 11: un nombre est divisible en 11alternant la différence de ses chiffres est divisible par 11.

Règles

• La sortie peut être sous n'importe quelle forme qui code clairement à la fois le signe et la valeur de la sortie.
• L'amorce d'entrée sera comprise entre 10 et 2 ^ 30.
• Vous n'avez pas besoin de gérer si l'entrée n'est pas un nombre premier ou n'est pas dans la plage.
• Vous n'avez pas besoin de gérer si les deux xet -xsont des sorties valides (cela ne devrait pas se produire).
• La force brute est autorisée, mais des solutions plus créatives sont appréciées.
• C'est du code-golf , donc le code le plus court dans chaque langue gagne! Ne laissez pas les réponses dans les langues de golf vous décourager de poster dans d'autres langues.

Cas de test

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 octets

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)serait écrit 9/n(mod -10)si j'avais accès à une division modulo équilibrée. Edit: sauvé 2 octets grâce à @EgorSkriptunoff

Python 2 , 27 octets

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

Essayez-le en ligne!

Les opérations se font de gauche à droite: (((n%5)*2)-5)^2 .

J'ai utilisé mon forceur arithmétique pour trouver l'expression n%5*2-5^2à exécuter {1:-1,3:3,2:-3,4:1}[k], en prenant l'inverse négatif d'un résidu mod 5 dans la plage [-2..2].

Gelée ,dix 8 octets

,N⁵æiAÞḢ

Essayez-le en ligne!

Explications

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

Brachylog , 14 octets

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

Essayez-le en ligne!

Python 2 , 69 54 53 octets

Edit: -15 octets grâce à @ Mr.Xcoder

Modifier: -1 octet en utilisant la récursivité

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

Essayez-le en ligne!

Python 2 , 31 29 27 octets

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

Essayez-le en ligne!

Japt , 16 9 octets

Beaucoup trop d'octets enregistrés grâce à une observation de @xnor

_*AÉ vU}c

Testez-le en ligne!Cela peut prendre quelques secondes sur des entrées plus importantes.

Explication

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

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

Port de la réponse JavaScrip (ES6) de @Neil , mais -2 octets grâce à @Nevay raison d'un plancher implicite d'entiers.

Essayez-le ici.

Pyke , 12 octets

3Q5%}5-f*hTf

Essayez-le ici!

Pyth , 14 octets

h/*x-y%QK5K2QT

Essayez-le ici.

Python 2 , 44 43 octets

(44 barré est toujours 44.) Merci à Fireflame241 pour avoir sauvé un octet!

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

Essayez-le en ligne!

Il y a exactement un nombre entre 0et P-1qui est l'inverse de 10. Mais si cet inverse use trouve être supérieur à P/2, il (u-P)est également un inverse et a une valeur absolue inférieure à u. Il s'avère donc que nous recherchons vraiment le nombre unique xentre -P/2et P/2qui est l'inverse de 10.

Le code ci-dessus fait exactement cela, en commençant à (l'étage de) P/2et en descendant jusqu'à ce qu'un inverse soit atteint. Cela doit se produire pour un certain nombre supérieur à -P/2tant Pqu'un nombre premier supérieur à 10. Plus précisément, il se terminera si et seulement si Pest coprime à 10.

Edit: Il s'avère que cela xest garanti entre -P/3et P/3, donc la version actuelle commence à P/3et descend de là. Voir la section intitulée Amélioré lié pour une explication à ce sujet.

Explication mathématique

Il n'était pas immédiatement évident pour moi pourquoi le test de divisibilité fonctionnait. Voici une explication, au cas où quelqu'un d'autre se demanderait.

Soit Pun nombre premier supérieur à 10dont le dernier chiffre est b. Donc

P = 10a + b

où a > 0, et 0 <= b < 10. En fait best soit 1, 3, 7ou 9, parce qu'une prime supérieure à la 10fin de l' indispensable dans l' un de ces chiffres.

Supposons maintenant bx + a = 0 (mod P). alors

a = -bx (mod P)

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

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

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

Puisque Pest premier, les entiers mod Psont un domaine intégral . Alors soit b = 0 (mod P), soit 1 - 10x = 0 (mod P).

Nous savons 0 <= b < 10 < P, donc si b = 0 (mod P)alors b = 0. Mais nous avons dit best soit 1, 3, 7ou 9, il en est ainsi impossible. Donc 1 - 10x = 0 (mod P), donc 10x = 1 (mod P). En d'autres termes, xest l'inverse de 10, moduloP .

Supposons maintenant que Nc'est un entier non négatif dont le dernier chiffre est d, N = 10c + d. Nous avons donc une chaîne d'instructions équivalentes:

10c + d = 0 (mod P)

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

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

QED.

Utilité?

Je me demandais également si le test de divisibilité (donné N = 10c + d, remplacé Npar dx + c) serait réellement productif dans la pratique. Ou du moins, est-il remplacé de manière fiable Npar un nombre inférieur à N(en valeur absolue)?

Supposons N = 10c + doù c >= 0et 0 <= d < 10. Par conséquent 10c = N - d <= N. Par l'inégalité du triangle,

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

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

Donc si 5P <= 9N/10, alors |c + dx| < N.

En particulier, si N >= 6P, alors |c + dx| < N. Ainsi, étant donné que Pnous commençons par le calcul 2P, 3P..., 6Painsi que x. Ensuite , étant donné N, nous courons le test de divisibilité à plusieurs reprises jusqu'à ce qu'on atteigne un nombre inférieur ou égal à 6P, et vérifier si le résultat est l' un des numéros 0, P, 2P, ..., 6P.

(Bien sûr, chaque fois que nous atteignons un nombre négatif, nous le remplaçons par sa valeur absolue, ce qui est bien car qest divisible par Psi et seulement si (-q)est.)

Limite améliorée

J'ai remarqué que cela |x|/Pne semblait jamais être proche 1/2. En fait, il semblait que c'était toujours moins que 1/3... ou à y regarder de plus près, c'était toujours très proche de l'un 1/10ou de l' autre 3/10. Le plus gros jamais obtenu semblait être 4/13(ce qui arrive quand P=13etx=4 ). Pourquoi serait-ce?

Soit uun entier et supposons que 10u = kP + 1pour un entier k, il en usoit de l'inverse de 10, modulo P. Ensuite, nous savons également que kc'est relativement premier 10, car k(-P)est équivalent à 1modulo 10.

Maintenant, nous savons que les inverses de 10modulo Pdiffèrent tous par des multiples de P, nous pouvons donc prendre l'entier uet soit ajouter ou soustraire des multiples de Pà volonté, et le résultat sera toujours toujours un inverse de 10modulo P. Supposons que nous choisissons de soustraire Pde u: nous obtenons

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

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

En d'autres termes, une diminution (respectivement une augmentation) ude Pcorrespond à une diminution (une augmentation) kde 10. Nous souhaitons ajouter / soustraire des multiples de Pde ujusqu'à ce que le côté gauche soit minimisé en valeur absolue; mais le côté gauche est minimisé exactement lorsque le côté droit est minimisé, et nous voulons donc ajouter / soustraire 10de kjusqu'à ce que le côté droit soit minimisé en valeur absolue.

Mais nous savons que cela se produira quand kest entre -5et 5, et donc (depuis kest relativement premier 10) ce moyen kest soit -3, -1, 1ou 3. (C'est le contenu du commentaire de @ Neil sous le PO. Merci, Neil! )

Ainsi , quand |u|est réduite au minimum (c. -à u=x), nous aurons x/P = u/P = k/10 + 1/(10P), où kest soit -3, -1, 1ou 3. Par conséquent |x|/P <= 3/10 + 1/(10P). De manière équivalente, |x| <= (3P + 1)/10.

De plus, cette inégalité est stricte chez P=11, car chez P=11nous nous avons x=-1et k=-1. Le plus petit Ppour lequel l'égalité est valable est P=13(où x=4et k=3).

Par conséquent, le plus grand |x|/Pjamais obtenu est 3/10 + 1/(10*13), parce que P=13c'est le premier nombre premier pour lequel nous avons k=3, et parmi ceux avec k=3, le 1/(10P)terme est le plus grand quand il Pest le plus petit (c'est-à-dire, à P=13). Par conséquent, pour tous P, nous avons aussi |x|/P <= 3/10 + 1/130 = 4/13 < 1/3. Cela explique pourquoi dans le code ci-dessus, nous pouvons initialiser à i = P/3plutôt que d'avoir à commencer par P/2.

De plus, les limites de la section Utilité ci-dessus peuvent maintenant être améliorées.

Lemme : Soit N = 10c + doù c > 0et 0 <= d <= 9. Alors c + d|x| < N/10 + 9(3P + 1)/10. (Notez l'inégalité stricte.)

Preuve de lemme: par cas. Cas I: d = 0oui N = 10c. Alors c + d|x| = c = N/10 < N/10 + 9(3P + 1)/10.

Cas II: 0 < d <= 9. Alors 10c = N - d < N, alors c < N/10. Par conséquent c + d|x| < N/10 + d|x| <= N/10 + 9|x| <= N/10 + 9(3P + 1)/10. QED.

Ainsi, si N > 3P(et N = 10c + dcomme précédemment), alors

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

Alors, si N > 3Palors c + d|x| < N.

Par conséquent, nous n'avons qu'à trouver P, 2Pet 3P, avec x. Étant donné N > 0que N > 3P, nous remplaçons Npar |c + dx|, ce qui diminue N. Finalement, nous aurons N <= 3P; à ce moment - là nous nous arrêtons et vérifier si Nest égal à l' un des numéros 0, P, 2Pou 3P.

Nous ne pouvons pas faire mieux qu'en 3Pgénéral. Par exemple, supposons que P = 13et N = 39ainsi x = 4. Puis remplaçant Npar des dx + c = 9(4) + 3feuilles Ninchangées.

Espace , 92 octets

Notez que la syntaxe de ce langage se compose uniquement d'espaces , donc chaque caractère d'espaces a été préfixé ici avec S, T ou L (correspondant respectivement à Space, Tab et Linefeed). Ceux-ci peuvent être supprimés sans perte de fonctionnalité, mais ils sont inclus ici afin de l'afficher correctement.

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
.

Essayez-le en ligne!

Japt , 14 octets

Inspiré par la solution de Neil .

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

Testez-le en ligne!

Explication:

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

~IIT*tR%)h

Essayez-le ici!

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

Excel, 27 octets

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

Peut être entré dans la cellule en tant que

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

pour 25 octets, mais les mises à jour automatiques d'Excel.