Если задано простое число Pбольше чем 10, ваша программа или функция должны выяснить свое правило делимости x, определяемое как целое число с наименьшим абсолютным значением, которое дает кратное первоначального простого числа, умноженное на последнюю цифру простого числа и добавленное к остальной части оригинала. премьер.

пример

Учитывая вход 31, последняя цифра 1и остальная часть числа 3. Таким образом, ваша программа должна найти целое число xс минимальным абсолютным значением, 1*x + 3кратным 31. В этом случае x=-3работает, поэтому программа или функция вернется -3.

Учитывая вход 1000003, последняя цифра 3и остальная часть числа 100000. Таким образом, ваша программа найдет, x=300001потому 3*300001+100000 = 1000003что это кратно 1000003.

Математический фон

Значение xможет использоваться в качестве теста делимости. Если число Nделится на P, то добавление xумноженного на последнюю цифру числа Nк остальному Nдаст кратное, Pесли и только если Nделится на Pв первую очередь.

Ибо P=11мы получаем x=-1, что эквивалентно известному правилу делимости для 11: число делится на 11чередующиеся разности его цифр делится на 11.

правила

• Вывод может быть в любой форме, которая четко кодирует как знак, так и значение вывода.
• Простое входное значение будет между 10 и 2 ^ 30.
• Вам не нужно обрабатывать, если вход не простое число или не находится в диапазоне.
• Вам не нужно обрабатывать, если оба xи -xявляются допустимыми выходами (не должно происходить).
• Допускается грубая сила, но ценятся более креативные решения.
• Это код-гольф , поэтому выигрывает самый короткий код на каждом языке ! Не позволяйте ответам на языках гольфа отговаривать вас от публикации на других языках.

Тестовые случаи

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 байта

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)было бы написано, 9/n(mod -10)если бы у меня был доступ к сбалансированному делению по модулю. Изменить: Сохранено 2 байта благодаря @EgorSkriptunoff

Python 2 , 27 байт

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

Попробуйте онлайн!

Операции выполняются слева направо: (((n%5)*2)-5)^2 .

Я использовал свой арифметический грубый форсер, чтобы найти выражение n%5*2-5^2для выполнения {1:-1,3:3,2:-3,4:1}[k], взяв отрицательную обратную величину остатка мод 5 в диапазон [-2..2].

Желе ,10 8 байт

,N⁵æiAÞḢ

Попробуйте онлайн!

Пояснения

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

Брахилог , 14 байт

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

Попробуйте онлайн!

Python 2 , 69 54 53 байта

Изменить: -15 байт благодаря @ Mr.Xcoder

Изменить: -1 байт с помощью рекурсии

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

Попробуйте онлайн!

Python 2 , 31 29 27 байт

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

Попробуйте онлайн!

Japt , 16 9 байт

Сохранено слишком много байтов благодаря наблюдению @xnor

_*AÉ vU}c

Проверьте это онлайн! Может потребоваться несколько секунд на больших входах.

объяснение

_  *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 байт

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

Порт ответа @Seil JavaScrip (ES6) , но -2 байта благодаря @Nevay из-за неявного выделения целых чисел.

Попробуй это здесь.

Пайк , 12 байт

3Q5%}5-f*hTf

Попробуй это здесь!

Pyth , 14 байт

h/*x-y%QK5K2QT

Попробуй это здесь.

Python 2 , 44 43 байта

(Вычеркнуто 44 все еще 44.) Спасибо Fireflame241 за сохранение байта!

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

Попробуйте онлайн!

Существует ровно один номер между 0и P-1который является обратным 10. Но если этот обратный uслучай больше, чем P/2, то (u-P)он также обратный, и имеет меньшее абсолютное значение, чем u. Вот и получается, что мы действительно ищем уникальный номерx между -P/2и P/2который является обратным к 10.

Код выше делает именно это, начиная с (этажа) P/2и спускаясь вниз, пока не будет достигнут обратный. Это должно произойти для некоторого числа больше, чем -P/2до тех пор, Pпока простое число больше, чем 10. Точнее, оно прекратится тогда и только тогда, когдаP это взаимно 10.

Изменить: На самом деле оказывается, что xгарантированно находится между -P/3и P/3, поэтому текущая версия начинается сP/3 и оттуда вниз. См. Раздел « Улучшенная граница» для объяснения этого.

Математическое объяснение

Для меня не сразу было очевидно, почему тест делимости работает. Вот объяснение, на случай, если кому-то еще будет интересно.

Позвольте Pбыть простое число, больше, чем 10, чья последняя цифра b. таким образом

P = 10a + b

где a > 0и 0 <= b < 10. На самом деле bлибо 1, 3, 7, или 9, так как простое число , большее 10должно заканчиваться в одной из этих цифр.

Теперь предположим bx + a = 0 (mod P). потом

a = -bx (mod P)

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

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

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

Поскольку Pпростое число, целые числа mod Pявляются интегральной областью . Так что либоb = 0 (mod P) , либо 1 - 10x = 0 (mod P).

Мы знаем 0 <= b < 10 < P, так что если b = 0 (mod P)тогда b = 0. Но мы сказали , bлибо 1, 3, 7, или 9, так что это невозможно. Поэтому 1 - 10x = 0 (mod P)так 10x = 1 (mod P). Другими словами, xэто обратное 10, по модулюP .

Теперь предположим, что Nэто неотрицательное целое число, последняя цифра которого d, поэтому у N = 10c + d. нас есть цепочка эквивалентных утверждений:

10c + d = 0 (mod P)

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

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

QED.

Полезность?

Мне также было интересно, будет ли тест делимости (задан N = 10c + d, заменен Nна dx + c) действительно продуктивным на практике. Или, по крайней мере, надежно ли заменить Nна число меньше, чемN (в абсолютном значении)?

Предположим N = 10c + d, где c >= 0и 0 <= d < 10. Поэтому 10c = N - d <= N. По неравенству треугольника,

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

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

Таким образом, если 5P <= 9N/10, тогда |c + dx| < N.

В частности, если N >= 6P, то |c + dx| < N. Таким образом, учитывая , Pмы начнем с расчета 2P, 3P..., 6Pнаряду с x. Затем дается N, мы проводим тест делимостных несколько раз , пока мы не достигнем числа меньше или равно 6P, и проверить , является ли результат любой из чисел 0, P, 2P..., 6P.

(Конечно, всякий раз, когда мы достигаем отрицательного числа, мы заменяем его его абсолютным значением, что хорошо, так qкак делится на Pто и только если (-q)есть.)

Улучшенная граница

Я заметил, что |x|/Pникогда не казалось близким 1/2. На самом деле казалось, что это всегда было меньше 1/3... или, при ближайшем рассмотрении, это всегда было очень близко к 1/10или 3/10. Самым большим, что он когда-либо получал 4/13(что случается, когда P=13и x=4). С чего бы это?

Позвольте uбыть целым числом и предположим, что 10u = kP + 1для некоторого целого k, так uчто обратное 10, по модулю P. Тогда мы также знаем, что kэто относительно простое число 10, так k(-P)как эквивалентно по 1модулю 10.

Теперь мы знаем, что все обратные по 10модулю Pотличаются на кратные P, поэтому мы можем взять целое число uи либо добавить, либо вычесть кратные Pпо желанию, и результат всегда будет обратным к 10модулю P. Предположим, мы решили вычесть Pиз u: мы получаем

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

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

Другими словами, уменьшение (соответственно увеличение) uна Pсоответствует уменьшению (увеличению) kна 10. Мы хотим добавить / вычесть кратные Pот uдо тех пор, пока левая часть не будет минимизирована по абсолютной величине; но левая сторона минимизируется именно тогда, когда правая сторона минимизирована, и поэтому мы хотим добавить / вычесть 10изk пока правая рука не сворачивается в абсолютной величине.

Но мы знаем , что это произойдет , когда kмежду -5и 5, и , следовательно , (так как kвзаимно простое с 10) это означает , что kлибо -3, -1, 1или 3. (Это содержание комментария @ Neil к OP. Спасибо, Neil! )

Таким образом , когда |u|минимизируется (т.е. u=x), мы будем иметь x/P = u/P = k/10 + 1/(10P), где kлибо -3, -1, 1или 3. Поэтому |x|/P <= 3/10 + 1/(10P). Эквивалентно |x| <= (3P + 1)/10.

Далее, это неравенство строгое P=11, потому что у P=11нас есть x=-1и k=-1. Наименьшее, Pдля которого выполняется равенство P=13(где x=4и k=3).

Поэтому самое большое, что |x|/Pкогда-либо получается 3/10 + 1/(10*13), это потому, что P=13это первое простое число, для которого мы имеем k=3, и среди тех, у кого k=3этот 1/(10P)термин самый большой, когда Pон наименьший (т. Е. At P=13). Поэтому для всех Pу нас тоже есть |x|/P <= 3/10 + 1/130 = 4/13 < 1/3. Это объясняет, почему в приведенном выше коде мы можем инициализировать, i = P/3а не начинать с P/2.

Кроме того, теперь можно улучшить границы в разделе « Полезность » выше.

Лемма : давай N = 10c + dгде c > 0и 0 <= d <= 9. Потом c + d|x| < N/10 + 9(3P + 1)/10. (Обратите внимание на строгое неравенство.)

Доказательство леммы: по случаям. Дело I: d = 0так N = 10c. Потом c + d|x| = c = N/10 < N/10 + 9(3P + 1)/10.

Случай II 0 < d <= 9. Тогда 10c = N - d < Nтак c < N/10. Следовательноc + d|x| < N/10 + d|x| <= N/10 + 9|x| <= N/10 + 9(3P + 1)/10 . QED.

Таким образом, если N > 3P(и N = 10c + dкак прежде), то

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

Так что, если N > 3Pтогда c + d|x| < N.

Таким образом, мы имеем только , чтобы найти P, 2Pи 3P, наряду с x. Учитывая N > 0, в то время как N > 3Pмы заменим Nна |c + dx|, который уменьшается N. В конце концов мы получим N <= 3P; в этой точке мы останавливаемся и проверить , является ли Nравно ни одному из чисел 0, P, 2P, или 3P.

Мы не можем сделать лучше, чем 3Pв целом. Например, предположим, P = 13и N = 39так x = 4. Затем замена Nна dx + c = 9(4) + 3листья Nбез изменений.

Пробел , 92 байта

Обратите внимание, что синтаксис этого языка состоит из только из пробелов , поэтому каждый символ пробела здесь имеет префикс S, T или L (соответствующий пробелу, табуляции и переводу строки соответственно). Они могут быть удалены без потери функциональности, но они включены здесь для правильного отображения.

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
.

Попробуйте онлайн!

Japt , 14 байт

Вдохновленный решением Нейла .

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

Проверьте это онлайн!

Объяснение:

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

Пайк , 10 байт

~IIT*tR%)h

Попробуй это здесь!

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

Excel, 27 байт

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

Может быть введен в ячейку как

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

для 25 байтов, но Excel автообновления.