Sequenziell teilbar

24

Manchmal zähle ich, um einzuschlafen, so hoch ich kann, während ich Zahlen überspringe, die nicht quadratfrei sind . Ich bekomme ein wenig Nervenkitzel, wenn ich mehrere Zahlen hintereinander überspringe - zum Beispiel 48,49,50sind alle NICHT quadratfrei (48 ist teilbar durch 2 ^ 2, 49 durch 7 ^ 2 und 50 durch 5 ^ 2).

Dies brachte mich dazu, mich über das früheste Beispiel benachbarter Zahlen zu wundern, die durch eine willkürliche Folge von Teilern teilbar sind.

Eingang

Die Eingabe ist eine geordnete Liste a = [a_0, a_1, ...]von streng positiven Ganzzahlen, die mindestens 1 Element enthalten.

Ausgabe

Die Ausgabe ist die kleinste positive Ganzzahl nmit der Eigenschaft, die a_0dividiert n, a_1dividiert n+1und allgemeiner a_kdividiert n+k. Ist dies nicht der nFall, ist das Verhalten der Funktion / des Programms nicht definiert.

Testfälle

[15] -> 15
[3,4,5] -> 3
[5,4,3] -> 55
[2,3,5,7] -> 158
[4,9,25,49] -> 29348
[11,7,5,3,2] -> 1518

Wertung

Das ist Code-Golf ; kürzestes Ergebnis (pro Sprache) gewinnt prahlerische Rechte. Die üblichen Lücken sind ausgeschlossen.

code-golf Chas Brown
quelle
Verwandte .
Alephalpha

Antworten:

6

Schale , 7 Bytes

VδΛ¦⁰ṫN

Probieren Sie es online!

Erläuterung

VδΛ¦⁰ṫN  Input is a list x.
      N  The list [1,2,3...
     ṫ   Tails: [[1,2,3...],[2,3,4...],[3,4,5...]...
V        Index of first tail y satisfying this:
  Λ       Every element
    ⁰     of x
   ¦      divides
 δ        the corresponding element of y.
Zgarb
quelle
5

MATL , 11 Bytes

`Gf@q+G\a}@

Probieren Sie es online!

`           % Do ....
 Gf         %   Convert input to [1,2,...,]
   @q+      %   Add current iteration index minus one, to get [n, n+1, ....]
      G\    %   Elementwise mod([n,n+1,...],[a_0,a_1,...])
        a   % ...while any of the modular remainders is nonzero.
         }  % Finally:
          @ %   Output the iteration index.

Nicht gerade für die Geschwindigkeit optimiert ... Der größte Testfall dauert mit MATL eine volle Minute und mit MATLAB ungefähr 0,03 Sekunden. Es gibt eine kleine Möglichkeit, dass MATL etwas mehr Overhead hat.

Sanchises
quelle
ah, ich hatte n:q`QtG\a]1)für 12 bytes doch n:offensichtlich das selbe wie fhier. Ich vergesse das immer, so dass Sie es als Alternative 11 Byte hinzufügen können.
Giuseppe
1
@ Giuseppe Schade, fq`QtG\a}@gibt eine fremde Kopie der Eingabe zurück.
Sanchises
5

JavaScript, 42 bis 40 Bytes

Gibt einen Rekursionsfehler aus, wenn es keine Lösung gibt (oder die Lösung zu groß ist).

a=>(g=y=>a.some(x=>y++%x)?g(++n):n)(n=1)

2 Bytes mit einem Zeiger von Rick Hitchcock gespeichert

Versuch es

Geben Sie eine durch Kommas getrennte Liste von Zahlen ein.

o.innerText=(f=
a=>(g=y=>a.some(x=>y++%x)?g(++n):n)(n=1)
)(i.value=[5,4,3]);oninput=_=>o.innerText=f(i.value.split`,`.map(eval))
<input id=i><pre id=o>
Erweitern Sie das Snippet

Zottelig
quelle
Nizza Ansatz, aber scheitert durch Überschreiten der Rekursionsgrenzen mit z [4,9,25,49].
Chas Brown
1
@ChasBrown, für die Zwecke des Codegolfs können wir unendlichen Speicher annehmen.
Shaggy
Ich denke, das wird für 38 Bytes funktionieren: (a,y=n=0)=>a.some(x=>y++%x)?f(a,++n):n
Rick Hitchcock
Oo, nett, @ RickHitchcock - danke. Vergiss das f=aber nicht.
Shaggy
Ah, natürlich. Es sind 40 Bytes.
Rick Hitchcock
3

05AB1E , 9 Bytes

Xµā<N+sÖP

Probieren Sie es online!

Erläuterung

Xµ          # loop until counter equals 1
  ā         # push range [1 ... len(input)]
   <        # decrement
    N+      # add current iteration index N (starts at 1)
      sÖ    # elementwise evenly divisible by
        P   # product
            # if true, increase counter
            # output N
Emigna
quelle
Zerstört meine 17-Byte-Antwort, autsch.
Magic Octopus Urn
3

Sauber , 61 Bytes

import StdEnv
$l=hd[n\\n<-[1..]|and[i/e*e==i\\i<-[n..]&e<-l]]

Probieren Sie es online!

Οurous
quelle
2
Ich denke, Sie müssen [1..]anstelle der [0..]Ausgabe 0eine nicht positive Ganzzahl für Singleton-Listen vermeiden .
Laikoni
@Laikoni danke, behoben.
Freitag,
3

Pyth , 11 Bytes

f!s.e%+kTbQ

Probieren Sie es online!

f!s.e%+kTbQ         Full program - inputs list from stdin and outputs to stdout
f                   First number T such that
   .e     Q         The enumerated mapping over the Input Q
      +kT           by the function (elem_value+T)
     %   b          mod (elem_index)
 !s                 has a false sum, i.e. has all elements 0
Dave
quelle
Benötigst du das 2am Ende? Ich bin sicher, dass es hier noch mehr zu retten gibt, aber ich kenne Pyth nicht.
Shaggy
@ Shaggy und @ Giuseppe, ihr beide habt Recht, und das Löschen des Endes 2behebt das Problem
Dave
2

J , 23 Bytes

[:I.0=]+/@:|"1#]\[:i.*/

Probieren Sie es online!

Galen Ivanov
quelle
Nett. Was ist die mathematische Tatsache, mit der Sie nur das Produkt der Eingaben überprüfen können? Woher wissen wir, dass es darüber hinaus keine Lösung geben kann? Woher wissen wir, I.dass nur 1 Ergebnis zurückgegeben wird? Ist es nicht möglich, dass es mehrere gibt?
Jonah
1
@Jonah - Ich weiß nicht, ob es immer funktioniert; Alle Tests, die ich gemacht habe, waren in diesen Grenzen.
Galen Ivanov
2

R , 51 Bytes

function(l){while(any((F+1:sum(l|1))%%l))F=F+1
F+1}

Probieren Sie es online!

Die Verwendung von anyThrows kwarnt vor impliziter Konvertierung nach logical, wobei kder Rückgabewert ist.

Giuseppe
quelle
47 Bytes !
Plannapus
@plannapus habe ich mir überlegt aber es scheitert leider daran l=c(15), da seq(l)==1:lin diesem Fall. seqist so nervig!
Giuseppe
Arf in der Tat und dann zwingen seq_alongist einfach zu lang.
Plannapus
Also, aber mit, sumanstatt anydiese Warnungen loszuwerden, FYI.
Plannapus
2

APL (Dyalog Unicode) , 24 23 22 Bytes

{∨/×⍺|⍵+⍳⍴⍺:⍺∇⍵+1⋄⍵}∘1

Probieren Sie es online!

Technisch ist dies eine stillschweigende Funktion. Ich musste es so machen, da die einzige erlaubte Eingabe die Liste der ganzen Zahlen ist. Verwendet⎕IO←0 (0-Indizierung)

Es ist erwähnenswert, dass die Funktion abläuft, wenn n sie nicht existiert.

Vielen Dank an @ngn und @ H.PWiz für jeweils 1 Byte.

Wie?

{∨/×⍺|⍵+⍳≢⍺:⍺∇⍵+1⋄⍵}∘1 ⍝ Main function. ⍺=input; ⍵=1.
{                   }∘1 ⍝ Using 1 as right argument and input as left argument:
           :            ⍝ If
        ⍳≢⍺             ⍝ The range [0..length(⍺)]
      ⍵+                ⍝ +⍵ (this generates the vector ⍵+0, ⍵+1,..., ⍵+length(⍺))
    ⍺|                  ⍝ Modulo ⍺
   ×                    ⍝ Signum; returns 1 for positive integers, ¯1 for negative and 0 for 0.
 ∨/                     ⍝ Logical OR reduction. Yields falsy iff the elements of the previous vector are all falsy.
            ⍺∇⍵+1       ⍝ Call the function recursively with ⍵+1.
                 ⋄⍵     ⍝ Else return ⍵.
J. Sallé
quelle
1

Japt, 10 Bytes

Wird irgendwann ausgegeben, undefinedwenn keine Lösung existiert, wenn Ihr Browser nicht zuerst abstürzt.

@e_X°vZÃ}a

Versuch es

Erläuterung

               :Implicit input of array U
@       }a     :Loop and output the first integer X that returns true.
 e_    Ã       :For every element Z in U
   X°          :X, postfix increcemnted
     vZ        :Is it divisible by Z?
Zottelig
quelle
1

Standard-ML (MLton) , 96 Bytes

open List;fun$n% =if all hd(tabulate(length%,fn i=>[1>(n+i)mod nth(%,i)]))then n else$(n+1)%;$1;

Probieren Sie es online!

Ungolfed:

open List
fun f n l = 
    if all (fn x=>x)
           (tabulate ( length l
                     , fn i => (n+i) mod nth(l,i) = 0))
    then n 
    else f (n+1) l
val g = f 1

Probieren Sie es online! Beginnend mit inkrementiert n=1die Funktion, bis die Bedingung erfüllt ist. In diesem Fallfnalln wird zurückgegeben.

tabulate(m,g)mit einer ganzen Zahl mund Funktion wird gdie Liste erstellt [g 0, g 1, ..., g m]. In unserer Bedingung tabulateheißt das mit der Länge der Eingabeliste lund einer Funktion, die prüft, ob das iElement von ldividiert n+i. Dies ergibt eine Liste von Booleschen Werten, so dass allmit der Identitätsfunktion fn x=>xgeprüft wird, ob alle Elemente wahr sind.

Ich habe einen netten Golf-Trick gefunden, um die Identitätsfunktion in diesem Fall um vier Bytes zu verkürzen: Anstelle des Lambda (fn x=>x)wird die hdeingebaute Funktion verwendet, die das erste Element einer Liste zurückgibt, und die resultierenden Bools in tabulatewerden in [und ]to eingeschlossen Erstellen Sie Singleton-Listen.

Laikoni
quelle
1

PowerShell , 65 62 Byte

for(){$o=1;$i=++$j;$args[0]|%{$o*=!($i++%$_)};if($o){$j;exit}}

Probieren Sie es online!

PowerShell hat nicht das Äquivalent eines anyodersome oder ähnlichem, daher benötigen wir einen etwas anderen Ansatz.

Dies nimmt die Eingabe $args[0]als Array und tritt dann in eine forEndlosschleife ein. Jede Iteration, die wir setzen $o, um 1(später erklärt) zu sein, und setzen $i, um zu sein ++$j. Das Inkrementieren $jüberwacht die erste Nummer der vorgeschlagenen Lösung, während die$i Inkrementieren über den Rest der vorgeschlagenen Lösung erfolgt.

Wir senden dann jedes Element der Eingabe $args[0]in eine ForEach-ObjectSchleife. Innerhalb der inneren Schleife multiplizieren wir Boolesch mit $odem Ergebnis einer Berechnung. Dies wird es so machen, dass, wenn die Berechnung für einen Wert fehlschlägt, sich der $ozuwendet 0. Die Berechnung ist !($i++%$_)oder das Boolesche nicht der Modulo-Operation. Da jeder Wert ungleich Null truthy in Powershell ist, wird dies keine Reste in einen Falsey Wert, so dreht $oin0 .

Außerhalb der inneren Schleife, if $odie ungleich Null ist, haben wir eine inkrementelle Lösung gefunden, die funktioniert, also geben wir aus$j und aus exit.

AdmBorkBork
quelle
1

tinylisp , 108 bytes

(load library
(d ?(q((L N)(i L(i(mod N(h L))0(?(t L)(inc N)))1
(d S(q((L N)(i(? L N)N(S L(inc N
(q((L)(S L 1

Die letzte Zeile ist eine unbenannte Lambda-Funktion, die eine Liste aufnimmt und eine Ganzzahl zurückgibt. Probieren Sie es online!

Ungolfed

(load library)

(comment Function to check a candidate n)
(def sequentially-divisible?
 (lambda (divisors start-num)
  (if divisors
   (if (divides? (head divisors) start-num)
    (sequentially-divisible? (tail divisors) (inc start-num))
    0)
   1)))

(comment Function to check successive candidates for n until one works)
(def search
 (lambda (divisors start-num)
  (if (sequentially-divisible? divisors start-num)
   start-num
   (search divisors (inc start-num)))))

(comment Solution function: search for candidates for n starting from 1)
(def f
 (lambda (divisors)
  (search divisors 1)))
DLosc
quelle
1

Julia 0,6 , 79 Bytes

f(s,l=length(s),n=s[])=(while !all(mod.(collect(0:l-1).+n,s).==0);n+=s[];end;n)

Probieren Sie es online!

Eingaben ohne gültige Lösung führen zu Endlosschleifen ... :)

niczky12
quelle
1

Python 2, 78 Bytes

def f(a,c=0):
 while [j for i,j in enumerate(a) if(c+i)%j<1]!=a:c+=1
 return c

EDIT: -26 danke an @Chas Brown

sonrad10
quelle
Nett! Ich habe Ihre Loop-Exit-Bedingung umgedreht, und Ihre Idee kann verbessert werden, um 78 Bytes zu erhalten .
Chas Brown
@ChasBrown danke, ich habe nicht daran gedacht, es so zu machen. Geändert!
sonrad10
0

APL NARS, 140 Byte, 70 Zeichen

r←f w;i;k
i←r←1⊃,w⋄k←¯1+⍴w⋄→0×⍳k=0
A:→0×⍳0=+/(1↓w)∣(k⍴r)+⍳k⋄r+←i⋄→A

Prüfung

  f 15
15
  f 3 4 5
3
  f 5 4 3
55
  f 2 3 5 7
158
  f 4 9 25 49
29348
  f 11 7 5 3 2 
1518
RosLuP
quelle
0

Java 8, 82 75 Bytes

a->{for(int r=1,i,f;;r++){i=f=0;for(int b:a)f+=(r+i++)%b;if(f<1)return r;}}

Erläuterung:

Probieren Sie es online aus.

a->{                 // Method with integer-array parameter and integer return-type
  for(int r=1,       //  Return-integer, starting at 1
          i,         //  Index-integer
          f;         //  Flag-integer
      ;r++){         //  Loop indefinitely, increasing `r` by 1 after every iteration
    i=f=0;           //   Reset both `i` and `f` to 0
    for(int b:a)     //   Inner loop over the input-array
      f+=(r+i++)%b;  //    Increase the flag-integer by `r+i` modulo the current item
    if(f<1)          //   If the flag-integer is still 0 at the end of the inner loop
      return r;}}    //    Return `r` as result
Kevin Cruijssen
quelle
0

Ruby , 47 46 43 42 Bytes

->a{(1..).find{|i|a.all?{|v|i%v<1&&i+=1}}}

Probieren Sie es online!

NB: Die (1..)Syntax wird nur in Ruby 2.6 unterstützt, im Moment unterstützt TIO nur 2.5, so dass der Link zu einer älteren Version (43 Bytes) ist.

Asone Tuhid
quelle