Nächste Partitionsnummern

12

Die Anzahl der Partitionen einer Ganzzahl gibt an, auf welche Weise eine Ganzzahl als Summe positiver Ganzzahlen dargestellt werden kann.

Beispielsweise:

5
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

Es gibt 7 Möglichkeiten, die Zahl 5 darzustellen, daher ist 7 die Partitionsnummer, die der Zahl 5 entspricht.

Partitionsnummern: OEIS: # A000041

Richtungen

Schreiben Sie ein Programm, das eine positive Ganzzahl als Eingabe annimmt und die beiden Zahlen ausgibt, die die beiden der Eingabenummer am nächsten liegenden Partitionsnummern erzeugen .

  • Die Eingabe muss eine positive Ganzzahl sein.
  • Wenn es sich bei der Eingabe nicht um eine Partitionsnummer handelt, muss es sich bei der Ausgabe um die 2 verschiedenen positiven Ganzzahlen handeln, die die beiden Partitionsnummern erzeugen, die der Eingabenummer am nächsten kommen. (Wenn zwei Partitionsnummern für eine der Ausgangsnummern gleich sind, spielt es keine Rolle, welche Sie auswählen.)
  • Wenn es sich bei der Eingabe um eine Partitionsnummer handelt, muss die Ausgabe eine positive Ganzzahl sein, die die Eingabenummer generiert.
  • Eingabe und Ausgabe können in jedem vernünftigen Format erfolgen.
  • Sie können davon ausgehen, dass die Eingabe nicht größer als 100 Millionen sein wird (z. B. wird die Ausgabe niemals größer als 95 sein).
  • Integrierte Funktionen zur Berechnung von Partitionsnummern sowie andere Standard-Regelungslücken sind nicht zulässig .
  • Das ist Code-Golf , also gewinnt die geringste Anzahl von Bytes.

Partitionsnummern: OEIS: # A000041

Beispiele

Input: 66
Output: 11, 12

(Die Partitionsnummern, die den Nummern 11 und 12 entsprechen, sind 56 und 77, die zwei Partitionsnummern, die 66 am nächsten kommen.)

Input: 42
Output: 10

(Die Nummer 42 ist bereits eine Partitionsnummer. Geben Sie einfach die Nummer aus, die der Partitionsnummer entspricht.)

Input: 136
Output: 13, 14

(Die beiden nächsten Partitionsnummern zu 136 sind tatsächlich beide WENIGER als 136 (z. B. 101 und 135), daher ist die Ausgabe 13 und 14 im Gegensatz zu 14 und 15.)

Input: 1
Output: 0   or   1

(Sowohl 0 als auch 1 sind in diesem speziellen Fall gültige Ausgaben.)

Input: 2484
Output: 26, 25   or   26, 27

(Diese beiden Ausgänge sind gültig, weil 2484 ist gleich d i Haltung von 1958 und 3010)

Input: 4
Output: 3, 4

(Jep)

code-golf number-theory integer-partitions kukac67
quelle
Sie haben nicht definiert, was eine Partitionsnummer ist
stolzer Haskeller
@proudhaskeller Partitionsnummern sind die Nummern, die in der OEIS-Sequenz verknüpft sind. Die Erklärung für die Partitionsnummer 5befindet sich oben. (Ich werde Klarstellung hinzufügen, wenn Sie denken, dass es nicht klar genug ist.)
Kukac67
1
Dies ist sehr nahe daran, ein Betrüger dieser früheren Partitionsfrage zu sein .
Peter Taylor

Antworten:

2

Pyth , 53

L?!b<b1sm&d*^_1tdy-b/*dt*3d2r_bhbJo^-QyN2U99<J-2qQyhJ

Erklärung und mehr Golf zu folgen.

isaacg
quelle
4

Python 2, 179 Bytes

Z=range(1,99)
R=Z+[1]
for i in Z:R[i]=sum(-(-1)**k*(3*k*k-k<=i*2and R[i-k*(3*k-1)/2])for k in range(-i,i+1)if k)
f=lambda n:zip(*sorted((abs(n-R[i]),i)for i in Z))[1][:2-(n in R)]

Verwendet die rekursive Formel aus dem fünfeckigen Satz von Euler .

Mit anrufen f(2484). Die Ausgabe ist ein Tupel mit einer oder zwei Zahlen.

Sp3000
quelle
2

Mathematica, 124 123 Bytes

f@n_:=(p=SeriesCoefficient[1/Product[1-x^k,{k,#}],{x,0,#}]&;s=SortBy[Range@95,Abs[n-p@#]&];If[p@s[[1]]==n,s[[1]],s~Take~2])

Formel für Partitionsnummern aus der OEIS-Seite . (Kann oder kann nicht betrügen ... Ich konnte mich nicht entscheiden.)

Verwendung:

In: f[136]

Out: {14, 13}

Ich antworte nicht, um zu gewinnen. Und ich bin mir sicher, dass dies weiter golfen werden könnte.

kukac67
quelle