Штрих делимости

31

Мы можем определить полосу делимости kчисла n, найдя наименьшее неотрицательное целое число k, которое n+kне делится на k+1.

Вызов

На выбранном вами языке напишите программу или функцию, которая выводит или возвращает полосу делимости вашего ввода.

Примеры:

n=13:
13 is divisible by 1 
14 is divisible by 2 
15 is divisible by 3 
16 is divisible by 4 
17 is not divisible by 5

Divisibilty полоса 13IS4

n=120:
120 is divisible by 1 
121 is not divisible by 2

Divisibilty полоса 120IS1

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

n      DS
2      1
3      2
4      1
5      2
6      1
7      3
8      1
9      2
10     1
2521   10

Больше тестовых случаев можно найти здесь .

Заметки

правила

  • Вы можете предположить, что ввод больше 1.

счет

code-golf : выигрывает представление с наименьшим количеством очков.

code-golf number division Оливер
источник
Я предлагаю изменить «наименьшее положительное целое число» на «наименьшее неотрицательное целое число». Это не меняет задачи вообще, но с текущим описанием это означает, что нам не нужно проверять делимость на 1 (что нам технически не нужно). Либо так, либо вы можете удалить делимость на 1 чек из описания.
TehPers
Наименьшее положительное целое число равно 1 и k + 1равно 2, где kнаименьшее положительное целое число. Простите за придирку.
TehPers
Разве это не то же самое, что найти наименьшее, kкоторое не делит n-1?
Пауло Эберманн
@ PaŭloEbermann Возьми n=7где k=3: n-1делится на k.
Оливер
Ах, я пропустил +1.
Пажло Эберманн

Ответы:

17

Java 8, 44 42 41 39 байт

Вычеркнуто 44 все еще регулярно 44; (

n->{int r=0;for(;~-n%--r<1;);return~r;}

-2 байта благодаря @LeakyNun .
-1 байт благодаря @TheLethalCoder .
-2 байта благодаря @Nevay .

Объяснение:

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

n->{                 // Method with integer as parameter and return-type
  int r=0;           //  Result-integer (starting at 0)
  for(;~-n%--r<1;);  //  Loop as long as `n-1` is divisible by `r-1`
                     //   (after we've first decreased `r` by 1 every iteration)
  return~r;          //  Return `-r-1` as result integer
}                    // End of method
Кевин Круйссен
источник
1
42 байта
прохудившаяся монахиня
1
41 байт Только что побрил байт из предложения LeakyNun.
TheLethalCoder
2
39 байтов
Nevay
4

JavaScript (ES6), 28 байт

n=>g=(x=2)=>++n%x?--x:g(++x)

Попробуй это

o.innerText=(f=

n=>g=(x=2)=>++n%x?--x:g(++x)

)(i.value=2521)();oninput=_=>o.innerText=f(+i.value)()
<input id=i><pre id=o>
Развернуть фрагмент

мохнатый
источник
4

Mathematica, 30 27 байтов

0//.i_/;(i+1)∣(#+i):>i+1&

Безымянная функция, которая принимает целочисленный аргумент.

Попробуйте на Wolfram Sandbox

Использование:

0//.i_/;(i+1)∣(#+i):>i+1&[2521]

10

Юнг Хван Мин
источник
3

Cubix , 17 байтов

)uUqI1%?;)qUO(;/@

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

Cubified

    ) u
    U q
I 1 % ? ; ) q U
O ( ; / @ . . .
    . .
    . .
  • I1 установить стек с вводом и делителем
  • %? сделать мод и протестировать
    • ;)qU)uqUесли 0 удалить результат и увеличить вход и делитель. Немного о пути, чтобы вернуться к%
    • /;(O@ если не 0, отбросьте результат, уменьшите делитель, выведите и выйдите

Смотреть это беги

MickyT
источник
2

Swift 4 , 56 байт

Это полная функция fс целочисленным параметром, iкоторый печатает выходные данные.

func f(i:Int){var k=0;while(i-1)%(k+1)<1{k+=1};print(k)}

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

Swift 4 , 56 байт

Это анонимная функция, которая возвращает результат.

{var k=0;while($0-1)%(k+1)<1{k+=1};return k}as(Int)->Int

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

Проверьте набор тестов!

Мистер Xcoder
источник
2

постоянный ток , 28 байт

1si[1+dli1+dsi%0=M]dsMxli1-p

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

Это кажется действительно неоптимальным, с увеличением и окончательным уменьшением, но я не могу найти способ улучшить это. По сути, мы просто увеличиваем счетчик iи наше начальное значение до тех пор, пока значение mod iостается равным нулю, а если это не так, мы вычитаем один из iи печатаем.

brhfl
источник
2

Gaia , 8 байт

@1Ė₌)†↺(

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

объяснение

@         Push input (call it n).
 1        Push 1 (call it i).
      ↺   While...
  Ė₌       n is divisible by i:
    )†     Increment both n and i.
       (  Decrement the value of i that failed this test and print.
Бизнес Кот
источник
2

J, 17 байт

[:{.@I.>:@i.|i.+]

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

Я думаю, что здесь еще есть место для игры в гольф.

Объяснение (без золота)

[: {.@I. >:@i. | i. + ]
                 i. + ]  Range [n,2n)
                 i.       Range [0,n)
                    +     Added to each
                      ]   n
         >:@i. | i. + ]  Divisibility test
         >:@i.            Range [1,n+1)
               |          Modulo (in J, the arguments are reversed)
                 i. + ]   Range [n,2n)
    {.@I.                Get the index of the first non-divisible
       I.                 Indices of non-zero values
    {.                    Head

Функция cap ( [:) предназначена для того, чтобы J не воспринимал последний глагол ( {.@I.) как часть ловушки.

Единственная странная вещь в этом ответе состоит в том, что I.фактически дублирует индекс каждого ненулевого числа столько раз, сколько его значение. например

   I. 0 1 0 2 3
1 3 3 4 4 4

Но это не имеет значения, так как мы все равно хотим получить первый индекс (и, поскольку он i.дает возрастающий диапазон, мы знаем, что первый индекс будет наименьшим значением).

Наконец, вот очень короткое доказательство того, что допустимо проверять деление только до n.

Мы начинаем проверять делимость с 1 | n, поэтому, предполагая, что полоса зашла так далеко, как только мы доберемся до проверки делимости, которая у nнас есть, n | 2n - 1которая никогда не будет истинной ( 2n - 1 ≡ n - 1 (mod n)). Поэтому полоса на этом закончится.

капуста
источник
2

Машинный код x86, 16 байт

49                 dec    ecx        ; decrement argument
31 FF              xor    edi, edi   ; zero counter

                Loop:
47                 inc    edi        ; increment counter
89 C8              mov    eax, ecx   ; copy argument to EAX for division
99                 cdq               ; use 1-byte CDQ with unsigned to zero EDX
F7 FF              idiv   edi        ; EDX:EAX / counter
85 D2              test   edx, edx   ; test remainder
74 F6              jz     Loop       ; keep looping if remainder == 0

4F                 dec    edi        ; decrement counter
97                 xchg   eax, edi   ; move counter into EAX for return
C3                 ret               ;  (use 1-byte XCHG instead of 2-byte MOV)

Вышеуказанная функция принимает один параметр nв ECXрегистре. Он вычисляет свою полосу делимости kи возвращает ее через EAXрегистр. Соответствует 32-битному соглашению о вызовах fastcall , поэтому его легко вызывать из кода C с использованием компиляторов Microsoft или Gnu.

Логика довольно проста: он просто выполняет итеративный тест, начиная с 1. Он функционально идентичен большинству других ответов, но оптимизирован вручную по размеру. Много хороших инструкции 1 байт там, в том числе INC, DEC, CDQ, и XCHG. Жестко запрограммированные операнды для деления нас немного ранили, но не сильно.

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

Коди Грей
источник
2

PHP , 34 байта

for(;$argv[1]++%++$r<1;);echo$r-1;

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

Достаточно просто. Проверяет остаток от деления (мода) каждого цикла при увеличении каждого значения, выводит, когда число больше не делится.

Xanderhall
источник
1

SOGL V0.12 , 8 байт

]e.-ē⁴I\

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

Неплохо для языка, созданного для совершенно другого типа задач.

Объяснение:

]         do .. while top of the stack is truthy
 e          push the variable E contents, by default user input
  .-        subtract the input from it
    ē       push the value of the variable E and then increase the variable
     ⁴      duplicate the item below one in the stack
      I     increase it
       \    test if divides
            if it does divide, then the loop restarts, if not, outputs POP which is `e-input`
dzaima
источник
1

Mathematica, 40 байт

Min@Complement[Range@#,Divisors[#-1]-1]&

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

Математический подход: n + k делится на k + 1 тогда и только тогда, когда n-1 делится на k + 1. И n-1 не делится на n, поэтому Range@#достаточно чисел.

Первоначально я намерен использовать Min@Complement[Range@#,Divisors[#-1]]-1&, но это также работает.

user202729
источник
Почему появляется капча, когда я использую представление от tio?
user202729
1
Потому что вы напечатали (скопировали и вставили) это слишком быстро. Это не о ТИО.
Утренняя монахиня
1

Юлия 0.6.0 (47 байт) (38 байт)

n->(i=1;while isinteger(n/i) i+=1;n+=1 end;i-1)

n->(i=1;while n%i<1 i+=1;n+=1end;i-1)

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

9 байтов было сокращено благодаря Mr.Xcoder

Goysa
источник
2
Обычно ссылка «Попробуйте онлайн» позволяет людям на самом деле попробовать код, определив некоторую комбинацию заголовка, нижнего колонтитула и аргументов, что означает, что нажатие кнопки воспроизведения дает результат.
Питер Тейлор
@PeterTaylor По чистой догадке, я попытался запустить его как таковой , и, к моему удивлению, это сработало. Я рекомендую ОП редактировать в тестируемой версии.
Мистер Кскодер
46 байтов (удаляя один пробел):n->(i=1;while isinteger(n/i) i+=1;n+=1end;i-1)
г-н Xcoder
Еще одно простое предположение позволило сделать гольф n->(i=1;while n%i<1 i+=1;n+=1end;i-1)
размером
@PeterTaylor К сожалению забыл это!
Гойса
1

Пакетная, 70 байт

@set/an=%1-1,i=0
:l
@set/ai+=1,r=n%%~i
@if %r%==0 goto l
@echo %i%

Все, что он делает, - это находит самое большое i, что LCM(1..i)делит n-1.

Нил
источник
1

Aceto , 28 27 байтов

[;`%
I)@]
iIk2I(D(
rk[(&Xpu

Я мог бы сохранить один байт, если мне не нужно выходить.

Объяснение:

Мы используем три стека: левый стек содержит счетчик, начинающийся с 2, правый - заданное число (или его приращения), центральный стек используется для выполнения операций по модулю. Мы могли бы, конечно, делать все в одном стеке, но таким образом мы можем установить внешние стеки как «липкие» (извлекаемые значения на самом деле не удаляются) и избавить себя от множества операций дублирования. Вот метод в деталях:

Прочитайте целое число, увеличьте его, сделайте текущий стек закрепленным и «переместите» его (и нас самих) в стек слева:

iI
rk[

Идите еще на один стек влево, вставьте литерал 2, сделайте этот стек тоже липким. Запомните эту позицию в коде ( @) и снова «переместите» значение и себя в центральный стек.

  @]
  k2
   (

Теперь мы проверяем: не по модулю ли два верхних числа 0? Если это так, перейдите к концу, в противном случае перейдите на одну стопку вправо, увеличьте значение и сдвиньте значение и нас в середину. Затем перейдите к левому стеку, увеличьте его тоже и вернитесь к отметке, которую мы установили ранее.

[;`%
I)
    I(
    &

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

      D(
     Xpu
L3viathan
источник
1

Рубин, 34 32 31 байт

f=->n,d=1{n%d<1?1+f[n+1,d+1]:0}

Рекурсивная лямбда. Все еще новичок в Ruby, поэтому предложения приветствуются!

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

Yytsi
источник
1

F #, 86 байтов 84 байта

let s n = 
    let rec c n1 d r=if n1%d=0 then c(n1+1)(d+1)(r+1)else r
    c n 1 0

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

Редактировать: -2 персонажа от Оливера

Владислав Хапин
источник
Добро пожаловать в PPCG! Ваша программа принимает стандартный ввод? Вы можете использовать TIO , у которого есть онлайн-переводчик F #. Кроме того, можно удалить пробелы в r = if?
Оливер
1
@Oliver Спасибо, я изменил ссылку на TIO, так что теперь вы можете передать аргумент для его проверки. :)
Владислав Хапин