Série de divisibilité

31

Nous pouvons définir la séquence de divisibilité kd'un nombre nen trouvant le plus petit entier non négatif ktel qu'il n+kn'est pas divisible par k+1.

Défi

Dans la langue de votre choix, écrivez un programme ou une fonction qui génère ou renvoie la séquence de divisibilité de votre entrée.

Exemples:

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

La Streak de Divisibilty 13est -4

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

La Streak de Divisibilty 120est -1

Cas de test:

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

Plus de cas de test peuvent être trouvés ici .

Remarques

Règles

  • Vous pouvez supposer que l'entrée est supérieure à 1.

Notation

code-golf : la soumission avec le score le plus bas gagne.

code-golf number division Oliver
la source
Je suggère de remplacer "le plus petit entier positif" par "le plus petit entier non négatif". Cela ne change pas du tout le défi, mais avec la description actuelle, cela implique que nous n'avons pas besoin de vérifier la divisibilité par 1 (ce qui, techniquement, ne devrait pas être nécessaire). Soit cela, soit vous pouvez supprimer la divisibilité par 1 contrôle de la description.
TehPers
Le plus petit entier positif est 1 et k + 1est 2, où kest le plus petit entier positif. Désolé pour le nitpick.
TehPers
N'est-ce pas la même chose que de trouver le plus petit kqui ne se divise pas n-1?
Paël Ebermann
@ PaŭloEbermann Prenez n=7où k=3: n-1est divisible par k.
Oliver
Ah, j'ai raté le +1 .
Paŭlo Ebermann

Réponses:

17

Java 8, 44 42 41 39 octets

Biffé 44 est toujours régulier 44; (

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

-2 octets grâce à @LeakyNun .
-1 octet grâce à @TheLethalCoder .
-2 octets grâce à @Nevay .

Explication:

Essayez ici.

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
la source
1
42 octets
Leaky Nun
1
41 octets Je viens de raser un octet de la suggestion de LeakyNun.
TheLethalCoder
2
39 octets
Nevay
8

Haskell , 35 octets

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

Essayez-le en ligne!

L'utilisation untilest également de 35 octets

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

JavaScript (ES6), 28 octets

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

Essaye-le

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>
Développer l'extrait

Hirsute
la source
4

Mathematica, 30 27 octets

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

Une fonction sans nom qui prend un argument entier.

Essayez-le sur Wolfram Sandbox

Usage:

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

10

JungHwan Min
la source
3

Cubix , 17 octets

)uUqI1%?;)qUO(;/@

Essayez-le en ligne!

Cubifié

    ) u
    U q
I 1 % ? ; ) q U
O ( ; / @ . . .
    . .
    . .
  • I1 configurer la pile avec entrée et diviseur
  • %? faire du mod et tester
    • ;)qU)uqUsi 0, supprimez le résultat et incrémentez l'entrée et le diviseur. Un petit détour pour revenir à%
    • /;(O@ sinon 0, baisse le résultat, décrémente le diviseur, sortie et sortie

Regardez-le courir

MickyT
la source
2

Swift 4 , 56 octets

Il s'agit d'une fonction complète f, avec un paramètre entier iqui imprime la sortie.

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

Essayez ici.

Swift 4 , 56 octets

Il s'agit d'une fonction anonyme qui renvoie le résultat.

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

Essayez ici.

Découvrez la suite de tests!

M. Xcoder
la source
2

dc , 28 octets

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

Essayez-le en ligne!

Cela semble vraiment sous-optimal, avec l'incrémentation et la décrémentation finale, mais je ne vois pas vraiment de moyen de l'améliorer. Fondamentalement, nous incrémentons simplement un compteur iet notre valeur de départ tant que la valeur mod icontinue d'être nulle, et une fois que ce n'est pas vrai, nous soustrayons un iet imprimons.

brhfl
la source
2

Gaia , 8 octets

@1Ė₌)†↺(

Essayez-le en ligne!

Explication

@         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.
Chat d'affaires
la source
2

J, 17 octets

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

Essayez-le en ligne!

Je pense qu'il y a encore de la place pour le golf ici.

Explication (non golfée)

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

Le cap ( [:) est là pour s'assurer que J ne traite pas le dernier verbe ({.@I. ) comme faisant partie d'un crochet.

La seule sorte de chose étrange à propos de cette réponse est que cela I.double en fait l'index de chaque nombre non nul autant de fois que la valeur de ce nombre. par exemple

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

Mais cela n'a pas d'importance puisque nous voulons de toute façon le premier index (et comme cela i.donne une plage ascendante, nous savons que le premier index sera la plus petite valeur).

Enfin, voici une très courte preuve qu'il est possible de vérifier la division uniquement jusqu'à n.

Nous commençons à vérifier la divisibilité avec 1 | n, donc en supposant que la séquence va aussi loin, une fois que nous aurons vérifié la divisibilité par nnous-mêmes, n | 2n - 1ce qui ne sera jamais vrai ( 2n - 1 ≡ n - 1 (mod n)). Par conséquent, la séquence se terminera là.

Cole
la source
2

Code machine x86, 16 octets

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)

La fonction ci-dessus prend un seul paramètre n, dans le ECXregistre. Il calcule sa séquence de divisibilité ket la renvoie via le EAXregistre. Il est conforme à la convention d'appel Fastcall 32 bits , il est donc facilement appelable à partir du code C à l'aide de compilateurs Microsoft ou GNU.

La logique est assez simple: il ne fait qu'un test itératif à partir de 1. Il est fonctionnellement identique à la plupart des autres réponses ici, mais optimisé à la main pour la taille. Beaucoup de belles instructions sur 1 octet, y compris INC,DEC , CDQet XCHG. Les opérandes codés en dur pour la division nous ont fait un peu mal, mais pas terriblement.

Essayez-le en ligne!

Cody Grey
la source
2

PHP , 34 octets

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

Essayez-le en ligne!

Assez simple. Vérifie le reste de la division (mod) de chaque boucle tout en incrémentant chaque valeur, sort lorsque le nombre n'est plus divisible.

Xanderhall
la source
1

SOGL V0.12 , 8 octets

]e.-ē⁴I\

Essayez-le ici!

Pas mal pour une langue qui est faite pour un type de défis complètement différent.

Explication:

]         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
la source
1

Mathematica, 40 octets

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

Essayez-le en ligne! (Mathématiques)

Approche mathématique, n + k est divisible par k + 1 si et seulement si n-1 est divisible par k + 1. Et n-1 n'est pas divisible par n, donc Range@#c'est assez de nombres.

À l'origine, j'ai l'intention d'utiliser Min@Complement[Range@#,Divisors[#-1]]-1&, mais cela fonctionne aussi.

utilisateur202729
la source
Pourquoi le captcha apparaît-il lorsque j'utilise la soumission de tio?
user202729
1
Parce que vous l'avez tapé (copié-collé) trop rapidement. Il ne s'agit pas de TIO.
Leaky Nun
1

Julia 0.6.0 (47 octets) (38 octets)

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)

Essayez-le en ligne!

9 octets ont été coupés grâce à Mr.Xcoder

Goysa
la source
2
Normalement, un lien "Essayez-le en ligne" permet aux utilisateurs d' essayer le code en définissant une combinaison d'en-tête, de pied de page et d'arguments, ce qui signifie qu'en appuyant sur le bouton de lecture, vous obtenez une sortie.
Peter Taylor
@PeterTaylor Par pure supposition, j'ai essayé de le faire fonctionner comme tel , et à ma grande surprise, cela a fonctionné. Je recommande l'OP à éditer avec la version testable.
M. Xcoder
46 octets (en supprimant un espace):n->(i=1;while isinteger(n/i) i+=1;n+=1end;i-1)
M. Xcoder
Une autre pure supposition a permis de jouer au golf à 38 octets:n->(i=1;while n%i<1 i+=1;n+=1end;i-1)
M. Xcoder
@PeterTaylor Désolé, je l'ai oublié!
Goysa
1

Lot, 70 octets

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

Tout ce qu'il y a à faire, c'est de trouver le plus grand iqui LCM(1..i)divise n-1.

Neil
la source
1

Aceto , 28 27 octets

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

Je pourrais économiser un octet si je n'ai pas à quitter.

Explication:

Nous utilisons trois piles: la pile de gauche contient un compteur commençant à 2, celle de droite contient le nombre donné (ou ses incréments), la pile centrale est utilisée pour effectuer les opérations modulo. Nous pourrions, bien sûr, tout faire dans une seule pile, mais de cette façon, nous pouvons définir les piles externes comme «collantes» (les valeurs qui sont sautées ne sont pas vraiment supprimées) et nous éviter de nombreuses opérations de duplication. Voici la méthode en détail:

Lisez un entier, incrémentez-le, rendez la pile courante collante et "déplacez-la" (et nous-mêmes) vers la pile de gauche:

iI
rk[

Allez encore une pile vers la gauche, poussez un littéral 2, rendez cette pile collante aussi. Rappelez-vous cette position dans le code ( @) et "déplacez" une valeur et nous-mêmes vers la pile centrale.

  @]
  k2
   (

Maintenant, nous testons: le modulo des deux premiers nombres n'est-il pas 0? Si c'est le cas, passez à la fin, sinon allez une pile vers la droite, incrémentez et poussez la valeur et nous au milieu. Ensuite, allez dans la pile de gauche, incrémentez-la également et revenez à la marque que nous avons définie auparavant.

[;`%
I)
    I(
    &

Lorsque le résultat du modulo n'était pas nul, nous inversons la position de l'IP, allons d'une pile vers la gauche (où réside notre compteur), décrémentons-la et imprimons la valeur, puis sortons.

      D(
     Xpu
L3viathan
la source
1

Rubis, 34 32 31 octets

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

Une lambda récursive. Encore nouveau pour Ruby, les suggestions sont donc les bienvenues!

Essayez-le en ligne!

Yytsi
la source
1

F #, 86 octets 84 octets

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

Essayez-le en ligne!

Edit: -2 personnages d'Oliver

Vladislav Khapin
la source
Bienvenue chez PPCG! Votre programme prend-il stdin? Vous pouvez utiliser TIO , qui dispose d'un interpréteur F # en ligne. En outre, peut supprimer l'espace blanc dans r = if?
Oliver
1
@Oliver Merci, j'ai changé le lien vers TIO, alors maintenant vous pouvez réellement passer l'argument pour le tester. :)
Vladislav Khapin