Możemy zdefiniować pasmo podzielności kliczby n, znajdując najmniejszą nieujemną liczbę całkowitą ktaką, przez którą n+knie można podzielić k+1.

Wyzwanie

W wybranym języku napisz program lub funkcję, która generuje lub zwraca pasmo podzielności wprowadzonych danych.

Przykłady:

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

Odmiana Divisibilty 13jest4

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

Odmiana Divisibilty 120jest1

Przypadki testowe:

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

Więcej przypadków testowych można znaleźć tutaj .

Notatki

• Na podstawie projektu Euler Problem 601
• Sekwencję tę można znaleźć w OEIS , zmniejszoną o 1.

Zasady

• Możesz założyć, że wartość wejściowa jest większa niż 1.

Punktacja

code-golf : Zgłoszenie z najniższą liczbą punktów wygrywa.

Pyth , 6 5 bajtów

f%tQh

Wypróbuj online!

Java 8, 44 42 41 39 bajtów

^{Przekreślone 44 jest nadal regularne 44; (}

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

-2 bajty dzięki @LeakyNun .
-1 bajt dzięki @TheLethalCoder .
-2 bajty dzięki @Nevay .

Wyjaśnienie:

Wypróbuj tutaj.

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

Haskell , 35 bajtów

f n=[k|k<-[1..],rem(n+k)(k+1)>0]!!0

Wypróbuj online!

Wykorzystanie untilzajmuje również 35 bajtów

f n=until(\k->rem(n+k)(k+1)>0)(+1)1

Łuska , 7 bajtów

ḟ§%→+⁰N

Wypróbuj online!

05AB1E , 7 6 bajtów

Ý+āÖ0k

Wypróbuj online!

Alternatywne rozwiązania 7-bajtowe:
<DLÖγнg
Ls<ÑKн<

JavaScript (ES6), 28 bajtów

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

Sprawdź to

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>

Mathematica, 30 27 bajtów

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

Funkcja bez nazwy, która przyjmuje argument liczby całkowitej.

Wypróbuj na Wolfram Sandbox

Stosowanie:

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

10

Perl 5 , 23 21 + 1 (-p) = 22 bajtów

1until$_++%++$\}{$\--

Wypróbuj online!

Python 2 , 35 bajtów

f=lambda n,x=1:n%x<1and-~f(n+1,x+1)

Wypróbuj online!

Cubix , 17 bajtów

)uUqI1%?;)qUO(;/@

Wypróbuj online!

Cubified

    ) u
    U q
I 1 % ? ; ) q U
O ( ; / @ . . .
    . .
    . .

• I1 ustaw stos za pomocą wejścia i dzielnika
• %? zrób mod i przetestuj
  • ;)qU)uqUjeśli 0 usuń wynik i przyrost danych wejściowych i dzielnik. Trochę okrągła ścieżka, do której można wrócić%
  • /;(O@ jeśli nie 0, upuść wynik, dzielnik dekrementacji, wyjdź i wyjdź

Zobacz, jak biegnie

Python 2 , 43 41 bajtów

Zaoszczędź 2 bajty dzięki Dziurawej Zakonnicy !

i=input();k=1
while~-i%-~k<1:k+=1
print k

Wypróbuj online!

Python 2 , 40 bajtów

f=lambda i,k=1:~-i%-~k<1and f(i,k+1)or k

Wypróbuj online!

Python 2 , 44 40 bajtów

-4 bajty dzięki Dziurawej Zakonnicy.

f=lambda n,x=1:~-n%-~x and x or f(n,x+1)

Wypróbuj online!

Szybki 4 , 56 bajtów

Jest to pełna funkcja fz parametrem liczby całkowitej, iktóry wypisuje dane wyjściowe.

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

Wypróbuj tutaj.

Szybki 4 , 56 bajtów

Jest to anonimowa funkcja, która zwraca wynik.

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

Wypróbuj tutaj.

Sprawdź pakiet testowy!

C # (mono) , 41 39 bajtów

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

Zasadniczo port odpowiedzi Java 8 @Kevina Cruijssena z dalszą grą w golfa.

Wypróbuj online!

dc , 28 bajtów

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

Wypróbuj online!

Wydaje mi się to naprawdę nieoptymalne, z przyrostem i ostatecznym zmniejszeniem, ale tak naprawdę nie widzę sposobu, aby to poprawić. Zasadniczo po prostu zwiększamy licznik ii naszą wartość początkową, o ile mod wartości inadal wynosi zero, a gdy to nieprawda, odejmujemy jeden ii drukujemy.

Gaia , 8 bajtów

@1Ė₌)†↺(

Wypróbuj online!

Wyjaśnienie

@         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.

J, 17 bajtów

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

Wypróbuj online!

Myślę, że wciąż jest tu miejsce na grę w golfa.

Wyjaśnienie (bez golfa)

[: {.@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 ( [:) ma za zadanie upewnić się, że J nie traktuje ostatniego czasownika ({.@I. ) jako części haka.

Jedyną dziwną rzeczą w tej odpowiedzi jest to, że I.faktycznie powiela indeks każdej niezerowej liczby tyle razy, ile wynosi wartość tej liczby. na przykład

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

Ale to nie ma znaczenia, ponieważ i tak chcemy pierwszego indeksu (a ponieważ i.daje zakres rosnący, wiemy, że pierwszy indeks będzie najmniejszą wartością).

Na koniec, oto bardzo krótki dowód na to, że sprawdzanie podziału można sprawdzić tylko do n.

Zaczynamy sprawdzać podzielność za pomocą 1 | n, więc zakładając, że pasmo posuwa się tak daleko, jak tylko przejdziemy do sprawdzania podzielności przez nnas, n | 2n - 1co nigdy nie będzie prawdziwe ( 2n - 1 ≡ n - 1 (mod n)). Dlatego pasmo na tym się skończy.

Japt , 7 bajtów

õ b!%UÉ

Przetestuj online!

Kod maszynowy x86, 16 bajtów

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)

Powyższa funkcja przyjmuje nw ECXrejestrze pojedynczy parametr . Oblicza pasmo podzielności ki zwraca to za pośrednictwem EAXrejestru. Jest zgodny z 32-bitową konwencją szybkich wywołań , dzięki czemu można go łatwo wywołać z kodu C przy użyciu kompilatorów Microsoft lub Gnu.

Logika jest dość prosta: wykonuje tylko iteracyjny test rozpoczynający się od 1. Jest funkcjonalnie identyczny z większością innych odpowiedzi tutaj, ale ręcznie zoptymalizowany pod kątem wielkości. Wiele miłych instrukcjami 1-bajtowych tam, w tym INC, DEC,CDQ , i XCHG. Zaszyfrowane argumenty podziału dzielą nas trochę, ale nie strasznie.

Wypróbuj online!

PHP , 34 bajty

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

Wypróbuj online!

Wystarczająco proste. Sprawdza pozostałą część podziału (mod) przy każdej pętli, zwiększając każdą wartość, wypisuje, gdy liczba nie jest już podzielna.

SOGL V0.12 , 8 bajtów

]e.-ē⁴I\

Wypróbuj tutaj!

Nieźle jak na język, który jest stworzony do zupełnie innego rodzaju wyzwań.

Wyjaśnienie:

]         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`

Mathematica, 40 bajtów

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

Wypróbuj online! (Matematyka)

Podejście matematyczne, n + k jest podzielne przez k + 1 wtedy i tylko wtedy, gdy n-1 jest podzielne przez k + 1. A n-1 nie jest podzielne przez n, więcRange@# jest wystarczająca liczba.

Pierwotnie zamierzam używać Min@Complement[Range@#,Divisors[#-1]]-1&, ale to też działa.

Julia 0.6.0 (47 bajtów) (38 bajtów)

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)

Wypróbuj online!

9 bajtów zostało obciętych dzięki Mr.Xcoder

C (gcc) , 34 bajty

i;f(n){for(i=1;++n%++i<1;);n=i-1;}

Wypróbuj online!

Partia, 70 bajtów

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

To wszystko polega na znalezieniu największego i, który LCM(1..i)dzieli n-1.

R , 43 bajty

function(n,k=0:n)which((n+k)%%(k+1)>0)[1]-1

Funkcja anonimowa.

Sprawdź wszystkie przypadki testowe!

Aceto , 28 27 bajtów

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

Mógłbym zapisać jeden bajt, jeśli nie muszę wychodzić.

Wyjaśnienie:

Używamy trzech stosów: lewy stos zawiera licznik rozpoczynający się od 2, prawy zawiera określoną liczbę (lub jej przyrosty), stos środkowy służy do wykonywania operacji modulo. Oczywiście moglibyśmy zrobić wszystko w jednym stosie, ale w ten sposób możemy ustawić zewnętrzne stosy jako „lepkie” (wartości, które są wyświetlane, tak naprawdę nie są usuwane) i zaoszczędzić sobie wielu operacji duplikacji. Oto szczegółowa metoda:

Przeczytaj liczbę całkowitą, zwiększ ją, spraw, aby bieżący stos był lepki, i „przenieś” go (i nas samych) na stos po lewej stronie:

iI
rk[

Idź jeszcze jeden stos w lewo, wciśnij dosłowne 2, uczyń ten stos również lepkim. Zapamiętaj tę pozycję w code ( @) i ponownie „przenieś” wartość i siebie na środkowy stos.

  @]
  k2
   (

Teraz testujemy: czy moduł dwóch pierwszych liczb nie jest równy 0? Jeśli tak, przeskocz na koniec, w przeciwnym razie przejdź o jeden stos w prawo, zwiększaj i przesuwaj wartość i nas na środek. Następnie przejdź do lewego stosu, zwiększ go również i wskocz z powrotem do znaku, który ustaliliśmy wcześniej.

[;`%
I)
    I(
    &

Kiedy wynik modulo nie był równy zero, odwracamy pozycję, w której porusza się IP, przesuwamy jeden stos w lewo (tam, gdzie mieszka nasz licznik), zmniejszamy go i wypisujemy wartość, a następnie wychodzimy.

      D(
     Xpu

Rubinowy, 34 32 31 bajtów

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

Rekurencyjna lambda. Wciąż nowy w Ruby, więc sugestie są mile widziane!

Wypróbuj online!

F #, 86 bajtów 84 bajtów

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

Wypróbuj online!

Edycja: -2 postacie z Olivera

Befunge , 19 bajtów

#v_1+::&+1-\%
1<@.-

Wypróbuj online!