Divisibilidade Streak

31

Podemos definir a Sequência kde Divisibilidade de um número n, encontrando o menor número inteiro não negativo, de kmodo que n+knão seja divisível por k+1.

Desafio

No seu idioma de escolha, escreva um programa ou função que produza ou retorne a sequência de divisibilidade de sua entrada.

Exemplos:

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

A série de divisibilidade 13é4

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

A série de divisibilidade 120é1

Casos de teste:

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

Mais casos de teste podem ser encontrados aqui .

Notas

Regras

  • Você pode assumir que a entrada é maior que 1.

Pontuação

: A finalização com a menor pontuação vence.

Oliver
fonte
Sugiro alterar "menor número inteiro positivo" para "menor número inteiro não negativo". Isso não muda o desafio, mas com a descrição atual, isso implica que não precisamos verificar a divisibilidade por 1 (o que tecnicamente não devemos). Ou isso, ou você pode remover a divisibilidade em 1 verificação da descrição.
TehPers
O menor número inteiro positivo é 1 e k + 1é 2, onde ké o menor número inteiro positivo. Desculpe pelo nitpick.
TehPers
Não é o mesmo que encontrar o menor kque não se divide n-1?
Pa Elo Ebermann
@ PaŭloEbermann Tome n=7onde k=3: n-1é divisível por k.
Oliver Oliver
Ah, eu senti falta do +1.
Paŭlo Ebermann 15/08

Respostas:

17

Java 8, 44 42 41 39 bytes

O riscado 44 ainda é regular 44;

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

-2 bytes graças a @LeakyNun .
-1 byte graças a @TheLethalCoder .
-2 bytes graças a @Nevay .

Explicação:

Experimente aqui.

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
fonte
1
42 bytes
Freira vazada
1
41 bytes Just shaved a byte from LeakyNun's suggestion.
TheLethalCoder
2
39 bytes
Nevay
8

Haskell, 35 bytes

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

Try it online!

Using until is also 35 bytes

f n=until(\k->rem(n+k)(k+1)>0)(+1)1
H.PWiz
fonte
4

JavaScript (ES6), 28 bytes

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

Test it

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>

Shaggy
fonte
4

Mathematica, 30 27 bytes

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

An unnamed function that takes an integer argument.

Try it on Wolfram Sandbox

Usage:

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

10

JungHwan Min
fonte
4

Perl 5, 23 21 + 1 (-p) = 22 bytes

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

Try it online!

Xcali
fonte
3

Cubix, 17 bytes

)uUqI1%?;)qUO(;/@

Try it online!

Cubified

    ) u
    U q
I 1 % ? ; ) q U
O ( ; / @ . . .
    . .
    . .
  • I1 setup the stack with input and divisor
  • %? do mod and test
    • ;)qU)uqU if 0 remove result and increment input and divisor. Bit of a round about path to get back to %
    • /;(O@ if not 0, drop result, decrement divisor, output and exit

Watch it run

MickyT
fonte
2

Python 2, 44 40 bytes

-4 bytes thanks to Leaky Nun.

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

Try it online!

totallyhuman
fonte
1
40 bytes
Leaky Nun
2

Swift 4, 56 bytes

This is a full function f, with an integer parameter i that prints the output.

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

Try it here.

Swift 4, 56 bytes

This is an anonymous function, that returns the result.

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

Try it here.

Check out the Test Suite!

Mr. Xcoder
fonte
2

dc, 28 bytes

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

Try it online!

This feels really suboptimal, with the incrementing and the final decrement, but I can't really see a way to improve on it. Basically we just increment a counter i and our starting value as long as value mod i continues to be zero, and once that's not true we subtract one from i and print.

brhfl
fonte
2

Gaia, 8 bytes

@1Ė₌)†↺(

Try it online!

Explanation

@         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
fonte
2

J, 17 bytes

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

Try it online!

I think there's still room for golfing here.

Explanation (ungolfed)

[: {.@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

The cap ([:) is there to make sure that J doesn't treat the last verb ({.@I.) as part of a hook.

The only sort of weird thing about this answer is that I. actually duplicates the index of each non-zero number as many times as that number's value. e.g.

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

But it doesn't matter since we want the first index anyways (and since i. gives an ascending range, we know the first index will be the smallest value).

Finally, here's a very short proof that it is valid to check division only up to n.

We start checking divisibility with 1 | n, so assuming the streak goes that far, once we get to checking divisibility by n we have n | 2n - 1 which will never be true (2n - 1 ≡ n - 1 (mod n)). Therefore, the streak will end there.

cole
fonte
2

x86 Machine Code, 16 bytes

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)

The above function takes a single parameter, n, in the ECX register. It computes its divisibility streak, k, and returns that via the EAX register. It conforms to the 32-bit fastcall calling convention, so it is easily callable from C code using either Microsoft or Gnu compilers.

The logic is pretty simple: it just does an iterative test starting from 1. It's functionally identical to most of the other answers here, but hand-optimized for size. Lots of nice 1-byte instructions there, including INC, DEC, CDQ, and XCHG. The hard-coded operands for division hurt us a bit, but not terribly so.

Try it online!

Cody Gray
fonte
2

PHP, 34 bytes

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

Try it online!

Simple enough. Checks the remainder of division (mod) each loop while incrementing each value, outputs when the number isn't divisible anymore.

Xanderhall
fonte
1

SOGL V0.12, 8 bytes

]e.-ē⁴I\

Try it Here!

Not bad for a language which is made for a completely different type of challenges.

Explanation:

]         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
fonte
1

Mathematica, 40 bytes

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

Try it online! (Mathics)

Mathematical approach, n+k is divisible by k+1 if and only if n-1 is divisible by k+1. And n-1 is not divisible by n, so Range@# is enough numbers.

Originally I intend to use Min@Complement[Range@#,Divisors[#-1]]-1&, but this also work.

user202729
fonte
Why does the captcha appear when I use the submission from tio?
user202729
1
Because you typed (copied-and-pasted) it too quickly. It isn't about TIO.
Leaky Nun
1

Julia 0.6.0 (47 bytes) (38 bytes)

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)

Try it online!

9 bytes were cut thanks to Mr.Xcoder

Goysa
fonte
2
Normally a "Try it online" link allows people to actually try the code by defining some combination of header, footer, and arguments which mean that pressing the play button gives output.
Peter Taylor
@PeterTaylor By a pure guess, I tried running it as such, and to my surprise it worked. I recommend the OP to edit in with the testable version.
Mr. Xcoder
46 bytes (removing one space): n->(i=1;while isinteger(n/i) i+=1;n+=1end;i-1)
Mr. Xcoder
Another pure guess allowed be to golf it down to 38 bytes: n->(i=1;while n%i<1 i+=1;n+=1end;i-1)
Mr. Xcoder
@PeterTaylor Sorry forgot it!
Goysa
1

Batch, 70 bytes

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

All this is doing is finding the largest i such that LCM(1..i) divides n-1.

Neil
fonte
1

Aceto, 28 27 bytes

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

I could save one byte if I don't have to exit.

Explanation:

We use three stacks: The left stack holds a counter starting at 2, the right one holds the given number (or its increments), the center stack is used for doing the modulo operations. We could, of course, do everything in one stack, but this way we can set the outer stacks to be "sticky" (values that are popped aren't really removed) and save ourselves many duplication operations. Here's the method in detail:

Read an integer, increment it, make the current stack sticky, and "move" it (and ourselves) to the stack to the left:

iI
rk[

Go one more stack to the left, push a literal 2, make this stack sticky, too. Remember this position in the code (@), and "move" a value and ourselves to the center stack again.

  @]
  k2
   (

Now we test: Is the modulo of the top two numbers not 0? If so, jump to the end, otherwise go one stack to the right, increment, and push the value and us to the middle. Then go to the left stack, increment it, too, and jump back to the mark that we set before.

[;`%
I)
    I(
    &

When the result of the modulo was not zero, we invert the position the IP is moving, go one stack to the left (where our counter lives), decrement it, and print the value, then exit.

      D(
     Xpu
L3viathan
fonte
1

Ruby, 34 32 31 bytes

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

A recursive lambda. Still new to Ruby, so suggestions are welcome!

Try it online!

Yytsi
fonte
1

F#, 86 bytes 84 bytes

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

Try it online!

Edit: -2 characters from Oliver

Vladislav Khapin
fonte
Welcome to PPCG! Does your program take stdin? You can use TIO, which has an online F# interpreter. Also, can remove the whitespace in r = if?
Oliver
1
@Oliver Thank you, I changed the link to TIO, so now you can actually pass the argument to test it. :)
Vladislav Khapin