Seria podzielności

31

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

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.

code-golf  number  division 
— Oliver
źródło
Sugeruję zmianę „najmniejszej dodatniej liczby całkowitej” na „najmniejszą nieujemną liczbę całkowitą”. To wcale nie zmienia wyzwania, ale przy obecnym opisie oznacza, że ​​nie musimy sprawdzać podzielności przez 1 (co technicznie nie powinno być konieczne). Albo to, albo możesz usunąć podzielność przez 1 czeków z opisu.
— TehPers
Najmniejszą dodatnią liczbą całkowitą jest 1, a k + 12, gdzie kjest najmniejszą dodatnią liczbą całkowitą. Przepraszam za nitpick.
— TehPers
Czy to nie to samo, co znalezienie najmniejszego, kktóry się nie dzieli n-1?
— Paŭlo Ebermann
@ PaŭloEbermann Weź n=7gdzie k=3: n-1jest podzielny przez k.
— Oliver,
Ach, tęskniłem za +1.
— Paŭlo Ebermann

Odpowiedzi:

17

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
— Kevin Cruijssen
źródło
1
— Leaky Nun
1
41 bajtów Właśnie ogoliłem bajt z sugestii LeakyNun.
— TheLethalCoder
2
— Nevay
4

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>
Rozwiń fragment kodu

— Kudłaty
źródło
3

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

— MickyT
źródło
2

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.

— brhfl
źródło
2

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.
— Business Cat
źródło
2

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.

— kapusta
źródło
2

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!

— Cody Gray
źródło
2

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.

— Xanderhall
źródło
1

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`
— dzaima
źródło
1

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.

— użytkownik202729
źródło
Dlaczego captcha pojawia się, gdy używam przesyłania z tio?
— user202729,
1
Ponieważ wpisałeś (skopiowałeś i wkleiłeś) zbyt szybko. Tu nie chodzi o TIO.
— Leaky Nun
1

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

— Goysa
źródło
2
Zwykle link „Wypróbuj online” umożliwia użytkownikom wypróbowanie kodu poprzez zdefiniowanie kombinacji nagłówka, stopki i argumentów, co oznacza, że ​​naciśnięcie przycisku odtwarzania daje wynik.
— Peter Taylor
@PeterTaylor Zgadując, próbowałem uruchomić go jako taki i ku mojemu zaskoczeniu zadziałało. Polecam OP do edycji w wersji testowalnej.
— Pan Xcoder
46 bajtów (usuwając jedną spację):n->(i=1;while isinteger(n/i) i+=1;n+=1end;i-1)
— Mr. Xcoder
Kolejnym czystym przypuszczeniem jest gra w golfa do 38 bajtów:n->(i=1;while n%i<1 i+=1;n+=1end;i-1)
— Pan Xcoder
@PeterTaylor Przepraszamy, zapomniałem!
— Goysa
1

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.

— Neil
źródło
1

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
— L3viathan
źródło
1

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!

— Yytsi
źródło
1

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

— Vladislav Khapin
źródło
Witamy w PPCG! Czy twój program ma standardowe wejście? Możesz użyć TIO , który ma internetowy tłumacz F #. Czy można również usunąć białe znaki w r = if?
— Oliver,
1
@Oliver Dziękuję, zmieniłem link na TIO, więc teraz możesz przekazać argument, aby go przetestować. :)
— Vladislav Khapin
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.