Summen aufeinanderfolgender Ganzzahlen

27

Bevor jemand etwas sagt, ähnlich und ähnlich . Aber das ist kein Betrug.


Einige positive ganze Zahlen können als die Summe von mindestens zwei aufeinanderfolgenden positiven ganzen Zahlen geschrieben werden. Zum Beispiel 9=2+3+4=4+5. Schreiben Sie eine Funktion, die eine positive Ganzzahl als Eingabe annimmt und als Ausgabe die längste Folge von aufeinanderfolgenden positiven Ganzzahlen ausgibt (jedes Format ist akzeptabel, obwohl -5 Byte, wenn die Ausgabe die aufsteigende Folge ist, die +wie oben gezeigt durch getrennt ist) Wenn es keine solche Sequenz gibt, sollte die Nummer selbst ausgedruckt werden.

Das ist Code Golf. Es gelten Standardregeln. Kürzester Code in Bytes gewinnt.


Beispiele (Beachten Sie, dass die Formatierung variiert)

Input:   9
Output:  2,3,4

Input:   8
Output:  8

Input:   25
Output:  [3,4,5,6,7]
Arcturus
quelle
2
Müssen die ausgegebenen Zahlen in einer bestimmten Reihenfolge sein (z. B. aufsteigend)?
xnor
2
Müssen die Zahlen> 0: 6 = 0 + 1 + 2 + 3 oder 6 = 1 + 2 + 3 sein
Damien
5
Wenn es eng verwandte Herausforderungen gibt, kann die Aussage "Das ist kein Betrug" die Menschen wenig davon überzeugen, wenn sie glauben, dass es ein Betrug ist. Es wäre hilfreicher, wenn Sie erklären würden, warum Sie glauben, dass dies nicht der Fall ist.
Martin Ender
1
@Damien "positiv" bedeutet normalerweise> 0. Wenn 0 enthalten wäre, würde dies als "nicht negativ" bezeichnet.
Martin Ender
3
cc @Vixen ^ (auch wenn negative Zahlen erlaubt wären, wäre die optimale Lösung immer der Bereich von -n+1bis n)
Martin Ender

Antworten:

11

Python, 67 Bytes

f=lambda n,R=[1]:n-sum(R)and f(n,[R+[R[-1]+1],R[1:]][sum(R)>n])or R

Eine seltsam einfache Strategie: Suche nach dem Intervall R mit der richtigen Summe.

  • Wenn die Summe zu klein ist, verschieben Sie den rechten Endpunkt des Intervalls um eins nach oben, indem Sie die nächsthöhere Zahl anhängen.
  • Wenn die Summe zu groß ist, verschieben Sie den linken Endpunkt nach oben, indem Sie das kleinste Element entfernen
  • Wenn die Summe korrekt ist, geben Sie R aus.

Da das untere Ende des Intervalls nur zunimmt, werden längere Intervalle vor kürzeren gefunden.

xnor
quelle
Seltsamerweise auch effizient. Der Rekursionsstapel läuft schließlich über, z. B. n = 8192.
Primo
7

Pyth, 12 10 Bytes

j\+hfqsTQ}M^SQ2

Der Code ist 15 Bytes lang und qualifiziert sich für den -5 Bytes Bonus. Versuchen Sie es online im Pyth-Compiler .

Vielen Dank an @Jakube für das Golfen mit 2 Bytes!

Wie es funktioniert

j\+hfqsTQ}M^SQ2    (implicit) Store evaluated input in Q.

            S      Compute [1, ..., Q].
           ^  2    Get all pairs of elements of [1, ..., Q].
         }M        Reduce each pair by inclusive range. Maps [a, b] to [a, ..., b].
    f              Filter; for each pair T:
      sT             Add the integers in T.
     q  Q            Check if the sum equals Q.
                   Keep the pair if it does.
   h               Retrieve the first match.
                   Since the ranges [a, ..., b] are sorted by the value of a,
                   the first will be the longest, in ascending order.
j\+                Join, using '+' as separator.
Dennis
quelle
1
Könnten Sie bitte eine Erklärung für diejenigen von uns hinzufügen, die im Gebiet von Pyth nicht aufgeklärt sind? :)
ETHproductions
Ich habe meine Antwort bearbeitet.
Dennis
Super, danke! Ich mag deine Technik.
ETHproductions
1
Eingabe 1000: 30 Minuten und Zählen ...
Primo
3

Mathematica, 73 68 65 56 43 Bytes

Cases[Range~Array~{#,#},i_/;Tr@i==#,{2},1]&
Alephalpha
quelle
1
+1 Letzte Nacht hatte ich eine ähnliche Lösung, aber mein Internet ging kaputt. Sie können auch Tupleseinen Infix-Ausdruck erstellen.
LegionMammal978
3

Haskell, 49 48 Bytes

f n=[[a..b]|a<-[1..n],b<-[a..n],sum[a..b]==n]!!0
Damien
quelle
1
1 Byte zu speichern: Verwenden Sie [...]!!0anstelle von head[...].
nimi
2

MATLAB, 87 79 Bytes

Ich weiß, dass es bereits eine MATLAB-Antwort gibt, diese unterscheidet sich jedoch in der Herangehensweise erheblich.

x=input('');m=1:x;n=.5-m/2+x./m;l=max(find(~mod(n(n>0),1)));disp(m(1:l)+n(l)-1)

Dies funktioniert auch bei Octave . Sie können es hier online versuchen . Ich habe den Code bereits consecutiveSum.min den verknüpften Arbeitsbereich eingefügt. Geben Sie ihn consecutiveSuman der Eingabeaufforderung ein und geben Sie den Wert ein (z. B. 25).

Ich arbeite immer noch daran, es zu reduzieren (möglicherweise wird die verwendete Gleichung ein wenig angepasst), aber im Grunde findet es den größten Wert, nfür den meine ganze Zahl ist, und zeigt dann die ersten mZahlen an, die mit beginnen n.

Warum funktioniert das? Nun, im Grunde gibt es eine mathematische Gleichung, die all diese Zahlen regelt. Wenn Sie davon ausgehen, dass sie alle aufeinander folgen und irgendwann beginnen, können Sie im Grunde sagen:

n+(n+1)+(n+2)+(n+3)+...+(n+p)=x

Daraus wird nun ersichtlich, dass die Sequenz im Grunde genommen nur die ersten pDreieckszahlen (einschließlich der 0.) sind, die zu p+1vielen addiert werden n. Wenn wir jetzt lassen m=p+1, können wir sagen:

m*(n+(m-1)/2)==x

Das ist eigentlich ziemlich lösbar. Ich bin immer noch auf der Suche nach dem kürzesten Code. Ich habe einige Ideen, um den obigen Code zu reduzieren.


Bei einer Eingabe von 25 wäre die Ausgabe:

3     4     5     6     7
Tom Carpenter
quelle
2
In Bezug auf Ihren Punkt bezüglich der Dreieckszahlen versucht diese Herausforderung im Wesentlichen, Dreieckszahlen mit einer positiven Differenz der Eingabe zu finden, sodass die Indizes der Dreieckszahlen in der Sequenz 1,3,6,10,...maximiert werden.
Arcturus
1

Python 2, 94 Bytes

n=input()
r=int((2*n)**.5)
while r:
 if~r%2*r/2==n%r:print range(n/r-~-r/2,n/r-~r/2);r=1
 r-=1

Die Eingabe erfolgt aus stdin. Diese Lösung eignet sich für sehr große Eingaben.

Dies iteriert über die möglichen Lösungslängen r mit r ≤ √ (2n) und prüft explizit auf eine Lösung. Um eine Lösung zu bestehen, wenn R ungerade ist, n mod r muss Null sein , und wenn R gerade ist, n mod r muss r / 2 .


Beispielnutzung

$ echo 8192 | python sum-con-int.py
[8192]

$ echo 1000002 | python sum-con-int.py
[83328, 83329, 83330, 83331, 83332, 83333, 83334, 83335, 83336, 83337, 83338, 83339]

$ echo 1000000006 | python sum-con-int.py
[250000000, 250000001, 250000002, 250000003]

Ich habe bewusst Beispiele mit relativ kleinen Leistungen ausgewählt.

primo
quelle
1

Oktave, 89 Bytes

Das ist das Beste, was ich in Octave machen kann. Der Algorithmus ist der gleiche wie bei xnor.

x=input('');k=i=1;while x;s=sum(k:i);if s<x;i++;elseif s>x;k++;else;x=0;end;end;disp(k:1)

In MATLAB wären dies 95 Bytes:

x=input('');k=1;i=1;while x;s=sum(k:i);if s<x;i=i+1;elseif s>x;k=k+1;else x=0;end;end;disp(k:i)

In MATLAB dauert dies ca. 0,1 Sekunden für die Eingabe 2000000und 1 Sekunde für die Eingabe 1000002.

Stewie Griffin
quelle
1

awk, 51 bytes

{while($0!=s+=s<$0?++j:-++i);while(++i-j)r=r i"+"}$0=r j

Der Code ist 56 Bytes minus 5 Bytes für das Ausgabeformat. Ich musste 4 zusätzliche Bytes verwenden, um dieses Format zu erzeugen, also habe ich tatsächlich 1 Byte gespeichert. Hurra! ;)

Tatsächlich ist es die harte Arbeit, ab 1 zu summieren, bis die Summe größer als die Eingabe ist. Dann beginnt die Subtraktion von Zahlen ab 1, bis die Zahl kleiner als die Eingabe ist. Auf diese Weise werden Start- und Endnummer so lange geändert, bis ein Ergebnis gefunden wurde, das dann gedruckt wird.

Anwendungsbeispiel

echo 303 | awk '{while($0!=s+=s<$0?++j:-++i);while(++i-j)r=r i"+"}$0=r j'

Ausgabe des Beispiels

48 + 49 + 50 + 51 + 52 + 53

Ich habe dies für eine Eingabe von versucht 1e12und es gab 464562+...+1488562fast sofort das richtige Ergebnis ( ). Obwohl es natürlich eine Weile gedauert hat ...

Cabbie407
quelle
Ich liebe den Awk-Ansatz. Ich habe Probleme, die Rangfolge der Bindungen zu ermitteln. Würde es Ihnen etwas ausmachen, eine Version mit mehr Klammern beizufügen, um es ein bisschen offensichtlicher zu machen? :)
Wildcard
1
{while($0!=s)s+=(s<$0) ? (++j) : -(++i); while(++i<j)r=r i"+"}$0=r j Ich hoffe, das hilft: i ist immer die letzte Ganzzahl, die vom Beginn der Kette abgezogen wurde, j ist immer die letzte Ganzzahl, die am Ende der Kette hinzugefügt wurde
Cabbie407
0

Japt , 33 Bytes

Dies verwendet Dennis 'Pyth-Technik , obwohl es erheblich länger ist ...

1oU à2 £W=Xg o1+Xg1¹x ¥U©W} rª ªU

Probieren Sie es online! Warnung: Bei größeren Eingaben (<= 20) dauert es eine Weile, bis der Browser zum Stillstand gekommen ist.

Ungolfed und Erklärung

1oU à2 £    W=Xg o1+Xg1¹ x ¥ U© W} rª  ª U
1oU à2 mXYZ{W=Xg o1+Xg1) x ==U&&W} r|| ||U

          // Implicit: U = input integer
1oU à2    // Generate a range from 1 to U, and take all combinations of length 2.
mXYZ{     // Map each item X in this range to:
W=Xg o    //  Set variable W to the range of integers starting at the first item in X,
1+Xg1)    //  and ending at 1 + the second item in X.
x ==U&&W  //  If the sum of this range equals U, return W; otherwise, return false.
r||       // Reduce the result with the || operator, returning the first non-false value.
||U       // If this is still false, there are no consecutive ranges that sum to U,
          // so resort to U itself.
          // Implicit: output last expression

Bonusverdienende Version: (38 Bytes - 5 = 33)

1oU à2 £W=Xg o1+Xg1¹x ¥U©W} rª ªU² q'+
ETHproductions
quelle
0

Julia, 92 Bytes

x->(t=filter(i->all(j->j==1,diff(sort(i))),partitions(x));collect(t)[indmax(map(length,t))])

Dies ist eine anonyme Funktion, die eine Ganzzahl akzeptiert und ein Array zurückgibt. Um es zu nennen, geben Sie ihm einen Namen, z f=x->....

Ungolfed:

function f(x::Integer)
    # Get all arrays of integers that sum to x
    p = partitions(x)

    # Filter these down to only consecutive runs by checking whether
    # all differences are 1
    t = filter(i -> all(j -> j == 1, diff(sort(i))), p)

    # Find the index of the longest element of t
    i = indmax(map(length, t))

    return collect(t)[i]
end
Alex A.
quelle
0

Ruby, 94 Bytes

->n{([*1..n].permutation(2).map{|i,j|[*i..j]if(i..j).reduce(:+)==n}-[p]).max_by{|k|k.size}||n}

Ungolfed:

-> n {
  ([*1..n].permutation(2).map { |i,j|   # Finds all the possible sets of size 2
     [*i..j] if(i..j).reduce(:+) == n   # Adds a set to an array if sum of the set is n.
   }-[p]                                # Removes nil from the array
  ).max_by { |k|                        # Finds the longest sequence
    k.size
  } || n                                # Returns n if no sequence found.
}

Verwendung:

->n{([*1..n].permutation(2).map{|i,j|[*i..j]if(i..j).reduce(:+)==n}-[p]).max_by{|k|k.size}||n}[25]
=> [3, 4, 5, 6, 7]
Vasu Adari
quelle
0

Im Ernst, 53 - 5 = 48 Bytes

,;;;╝`;u@n╟(D;)`n(XXk`iu@u@x;Σ╛=[])Ii`╗`ñ╜M`M;░p@X'+j

Hex Dump

2c3b3b3bbc603b75406ec728443b29606e2858586b60697540754
0783be4be3d5b5d29496960bb60a4bd4d604d3bb0704058272b6a

Probieren Sie es online!

Es ist der Brute-Force-Ansatz, ähnlich wie bei Dennis 'Pyth.

Alles bis auf den kgerade gelesenen Eingang nin Register 1 und erstellt dann die Liste [[1],[2,2],[3,3,3],[4,4,4,4],...]bis auf n nden.

Das nächste Bit bis ist eine in Register 0 gespeicherte Funktion, die ein Paar nimmt, beide Elemente inkrementiert, sie in einen Bereich umwandelt, die Summe des Bereichs findet und prüft, ob diese Summe der Wert in Register 1 ist. es gibt den entsprechenden Bereich zurück und wenn dies nicht der Fall ist, wird eine leere Liste zurückgegeben.

Der Teil bis zum letzten Auftreten von Mordnet eine Funktion über der oben beschriebenen ausgefallenen Liste von Listen zu, wobei enumerateauf jeder Liste die gespeicherte Funktion zugeordnet wird. Wenn es fertig ist, haben wir eine Liste von Listen, von denen jede leer ist oder einen Bereich, der sich summiert n.

;░Entfernt die leeren Listen. p@Xnimmt die erste liste die bleibt ( 0@Ewürde auch funktionieren). '+jsetzt +zwischen jede Zahl, während es die Liste in eine Zeichenkette für den Bonus umwandelt.

Quintopie
quelle
0

ES6, 72 Bytes

n=>{for(l=u=1;n;)n>0?n-=u++:n+=l++;return[...Array(u).keys()].slice(l);}

Gerade Portierung der awk-Lösung von @ Cabbie407, aber ohne den Formatierungsbonus, da es hier eine Strafe ist.

Neil
quelle
0

Python 3, 239 236 215 203 Bytes

Das ist etwas umständlich. Ich muss später Golf spielen.

def x(n):
 r=[n]
 for i in range(2,n):
  t=[]
  if i%2*(n%i<1):t=[j+n//i-i//2for j in range(i)]
  elif i%2<1and n%i==i//2:t=[j+n//i-i//2+1for j in range(i)]
  if t[:1]>[0]*(sum(t)==n):r+=t,
 return r[-1]

Dies kliegt daran , dass Python unhöfliche Geräusche von sich gibt, wenn Sie t[0]nach einem leeren tsuchen. Auch dies ist Golfen erforderlich. Dank t[:1], keine unhöflichen Geräusche mehr! Sie müssen nur gegen ein anderes Array prüfen.

Sherlock9
quelle
0

Gelee , 8 Bytes (nicht konkurrierend)

ẆS⁼¥Ðf⁸Ṫ

Probieren Sie es online!

Wenn ich das richtig verstehe, könnte dies eine (11-5 = 6) -byte Version sein:

ẆS⁼¥Ðf⁸Ṫj”+
Erik der Outgolfer
quelle
Aus Gründen des Interesses gibt es 12 ähnliche Lösungen (einschließlich dieser), indem die nicht vektorisierenden Gleichungen gegen die vektorisierenden Gleichungen ausgetauscht werden, das linke Argument gegen das erste Argument oder gegen die Identität ausgetauscht wird und Gleichungen gegen Nichtgleichungen ausgetauscht werden und nach gefiltert werden Filter-Out für Vektorisierung und Nicht-Vektorisierung. : O
HyperNeutrino
Nehmen wir an, ich habe das veröffentlicht, das am sinnvollsten ist, aber mit Geschwindigkeitsoptimierung.
Erik der Outgolfer
0

05AB1E , 11 - 5 = 6 Bytes (nicht konkurrierend)

Diesen Bonus natürlich nehmen :)

LŒʒOQ}é¤'+ý

Probieren Sie es online!

LŒʒOQ}é¤'+ý  Argument: n
LŒ           Sublists of range 1 to n
  ʒOQ}       Filter by total sum equals n
      é¤     Get longest element
        '+ý  Join on '+'
kalsowerus
quelle
0

PHP, 70 Bytes

while(fmod($q=sqrt(2*$argn+(++$p-.5)**2)-.5,1));print_r(range($p,$q));

Laufen Sie als Pipe mit -nRoder versuchen Sie es online .

erhöht sich, pbis eine ganzzahlige Lösung für gefunden wird argument==(p+q)*(q-p+1)/2, und gibt
dann den Bereich von pbis aus q.

Titus
quelle
0

Excel VBA, 119 - 5 = 114 Bytes

SubRoutine, die die Eingabe neiner Ganzzahl vom erwarteten Typ annimmt und die längste Folge aufeinanderfolgender Zahlen, die sich daraus ergeben, an die Zelle ausgibt[A1]

Sub a(n)
For i=1To n
s=0
For j=i To n
s=s+j
If s=n Then:For k=i To j-1:r=r &k &"+":Next:[A1]=r &j:End
Next
Next
End Sub
Taylor Scott
quelle