Podemos definir a Sequência k
de Divisibilidade de um número n
, encontrando o menor número inteiro não negativo, de k
modo que n+k
nã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
- Baseado no problema do projeto Euler 601
- Essa sequência pode ser encontrada no OEIS , deslocada para 1.
Regras
- Você pode assumir que a entrada é maior que 1.
Pontuação
code-golf : A finalização com a menor pontuação vence.
k + 1
é 2, ondek
é o menor número inteiro positivo. Desculpe pelo nitpick.k
que não se dividen-1
?n=7
ondek=3
:n-1
é divisível pork
.+1
.Respostas:
Pitão ,
65 bytesExperimente online!
fonte
Java 8,
44424139 bytesO riscado 44 ainda é regular 44;
-2 bytes graças a @LeakyNun .
-1 byte graças a @TheLethalCoder .
-2 bytes graças a @Nevay .
Explicação:
Experimente aqui.
fonte
Haskell, 35 bytes
Try it online!
Using
until
is also 35 bytesfonte
Husk, 7 bytes
Try it online!
fonte
05AB1E,
76 bytesTry it online!
Alternate 7 byte solutions:
<DLÖγнg
Ls<ÑKн<
fonte
JavaScript (ES6), 28 bytes
Test it
fonte
Mathematica,
3027 bytesAn unnamed function that takes an integer argument.
Try it on Wolfram Sandbox
Usage:
fonte
Perl 5,
2321 + 1 (-p) = 22 bytesTry it online!
fonte
Python 2, 35 bytes
Try it online!
fonte
Cubix, 17 bytes
Try it online!
Cubified
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 exitWatch it run
fonte
Python 2,
4341 bytesSaved 2 bytes thanks to Leaky Nun!
Try it online!
Python 2, 40 bytes
Try it online!
fonte
Python 2,
4440 bytes-4 bytes thanks to Leaky Nun.
Try it online!
fonte
Swift 4, 56 bytes
This is a full function
f
, with an integer parameteri
that prints the output.Try it here.
Swift 4, 56 bytes
This is an anonymous function, that returns the result.
Try it here.
Check out the Test Suite!
fonte
C# (Mono),
4139 bytesEssentially a port of @Kevin Cruijssen's Java 8 answer with further golfing.
Try it online!
fonte
dc, 28 bytes
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 modi
continues to be zero, and once that's not true we subtract one fromi
and print.fonte
Gaia, 8 bytes
Try it online!
Explanation
fonte
J, 17 bytes
Try it online!
I think there's still room for golfing here.
Explanation (ungolfed)
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.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 byn
we haven | 2n - 1
which will never be true (2n - 1 ≡ n - 1 (mod n)
). Therefore, the streak will end there.fonte
Japt, 7 bytes
Test it online!
fonte
x86 Machine Code, 16 bytes
The above function takes a single parameter,
n
, in theECX
register. It computes its divisibility streak,k
, and returns that via theEAX
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
, andXCHG
. The hard-coded operands for division hurt us a bit, but not terribly so.Try it online!
fonte
PHP, 34 bytes
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.
fonte
SOGL V0.12, 8 bytes
Try it Here!
Not bad for a language which is made for a completely different type of challenges.
Explanation:
fonte
Mathematica, 40 bytes
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.fonte
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
fonte
n->(i=1;while isinteger(n/i) i+=1;n+=1end;i-1)
n->(i=1;while n%i<1 i+=1;n+=1end;i-1)
C (gcc), 34 bytes
Try it online!
fonte
i--
instead ofn=i-1
Batch, 70 bytes
All this is doing is finding the largest
i
such thatLCM(1..i)
dividesn-1
.fonte
R, 43 bytes
Anonymous function.
Verify all test cases!
fonte
Aceto,
2827 bytesI 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:
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.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.
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.
fonte
Ruby,
343231 bytesA recursive lambda. Still new to Ruby, so suggestions are welcome!
Try it online!
fonte
F#,
86 bytes84 bytesTry it online!
Edit: -2 characters from Oliver
fonte
r = if
?Befunge, 19 bytes
Try it online!
fonte