Hintergrund

Beim letzten Mal haben wir Gruppen einer bestimmten Größe gezählt , was kein einfaches Problem ist.

Dieses Mal werden nur abelsche Gruppen gezählt , dh Gruppen mit einer kommutativen Operation. Formal ist eine Gruppe (G, ∗) abelsch, wenn x ∗ y = y ∗ x für alle x, y in G ist .

Auf diese Weise wird das Problem viel einfacher, und wir werden sie effizient zählen.

Aufgabe

Schreiben Sie ein Programm oder eine Funktion, die eine nicht negative ganze Zahl n als Eingabe akzeptiert und die Anzahl der nicht isomorphen abelschen Gruppen der Ordnung n ausgibt oder zurückgibt .

Eine Möglichkeit, die Anzahl der Gruppen zu berechnen, die wir mit A (n) bezeichnen, besteht darin, Folgendes zu beachten:

• A (0) = 0

• Wenn p eine Primzahl ist, ist A (p ^k ) gleich der Anzahl von ganzzahligen Partitionen von k . (vgl. OEIS A000041 )

• Wenn n = mk und m und k Co-Primer sind, ist A (n) = A (m) A (k) .

Sie können diese oder eine andere Methode zur Berechnung von A (n) verwenden .

Testfälle

Input               Output
0                   0
1                   1
2                   1
3                   1
4                   2
5                   1
6                   1
7                   1
8                   3
9                   2
10                  1
11                  1
12                  2
13                  1
14                  1
15                  1
16                  5
17                  1
18                  2
19                  1
20                  2
4611686018427387904 1300156
5587736968198167552 155232
9223371994482243049 2

(entnommen aus OEIS A000688 )

Zusätzliche Regeln

• Bei genügend Zeit, RAM und einer Registergröße, die die Eingabe aufnehmen kann, sollte Ihr Code (theoretisch) für beliebig große ganze Zahlen funktionieren.

• Ihr Code muss für alle Ganzzahlen zwischen 0 und 2 ⁶³ - 1 funktionieren und auf meinem Computer (Intel i7-3770, 16 GiB RAM, Fedora 21) in weniger als 10 Minuten fertig sein.

  Stellen Sie sicher, dass Sie Ihren Code für die letzten drei Testfälle zeitlich festgelegt haben, bevor Sie Ihre Antwort senden.

• Integrierte Funktionen, die diese Aufgabe banalisieren, wie z. B. die von Mathema- tica FiniteAbelianGroupCount, sind nicht zulässig.

• Integrierte Funktionen, die die ganzzahligen Partitionen einer Zahl oder die Partitionen einer Liste zurückgeben oder zählen, sind nicht zulässig.

• Es gelten die Standardregeln für Code-Golf .

CJam ( 39 38 Bytes)

qimF{~M\{_ee{~\)<1b}%1+a\+}*0=1be&}%:*

Online-Demo

Dies folgt der vorgeschlagenen Linie, um eine Primfaktorisierung zu finden (mF ) und dann die Partitionen jeder Potenz zu berechnen und ihr Produkt zu nehmen.

Es gibt zwei Sonderfälle für mF: es Faktoren 0als 0^1und 1als1^1 . Letzteres erfordert keine spezielle Behandlung: Es gibt eine abelsche Gruppe der Größe 1 und eine Partition von 1. Für Null ist jedoch ein Sonderfall erforderlich.

Die Partitionszählung verwendet eine Wiederholung für A008284(n, k)die Anzahl der Partitionen nin kTeile. In OEIS ist es gegeben als

T(n, k) = Sum_{i=1..k} T(n-k, i), for 1<=k<=n-1; T(n, n) = 1 for n >= 1.

aber ich denke, es ist sinnvoller, die Summe als von 1bis zu zu betrachten min(k, n-k).

Präparation

q~              e# Parse input into an integer
mF              e# Factorise it
{               e# For each factor p^a
  ~             e#   Split the array [p a]
                e#   The following lines count partitions of a
                e#   (Note: they would be buggy if a were ever 0, but it isn't)
  M\{           e#   Starting with a table of zero rows, repeat a times
    _ee         e#     Copy table and pair each row with its index
    {~\)<1b}%   e#     Extract that prepended index and use it to sum for each j
                e#     the first jth items of row j
    1+          e#     Append a 1 for P(i, i)
    a\+         e#     Prepend the new row to the table (which is stored in reverse)
  }*
  0=1b          e#   Sum the elements in the latest (first) row

  e&            e#   If p was 0 then replace with 0
}%
:*              e# Take the product

CJam, 50 49 47 43 Bytes

ri_mF{1=_L{1$0>{,f{):X-Xj}:+}{;!}?}2j}%:*e&

Verwendet die eingebaute mFFaktorisierung von CJam und einen gespeicherten Port dieser Python-Partitionsnummernfunktion:

p=lambda n,x:n==0 or n>0and sum(p(n+~a,a+1)for a in range(x))

oder ungolfed:

def p(n, x): # Call like p(n, n). n is number remaining, x is max part size
  if n > 0:
    return sum(p(n-a-1,a+1)for a in range(x))
  else:
    return (n==0)

Wie bei der Antwort von @ RetoKoradi dauert der letzte Fall im Offline-Interpreter ungefähr 17 Sekunden, da CJam so lange braucht, um die Zahl zu faktorisieren. Daher habe ich es aus dieser Online-Testsuite herausgelassen .

Vollständige Erklärung

[Main body]
ri                                Read input and convert to int
  _          e&                   Logical AND input with final result to special case 0 
   mF                             Factorise input into [base, exponent] pairs
     {...}%                       Map, converting each pair to a partition number
           :*                     Take product

[Pair -> partition]
1=_                               Get exponent and copy (n,x in above Python)
   L                              Initialise empty cache
    {                       }2j   Memoise with 2 arguments
     1$0>                         Check if n > 0
         {            }{  }?      Execute first block if yes, else second block
                        ;!        Return (n == 0)
          ,f{      }              For each a in range(x) ...
             ):X-Xj               Call p(n-a-1,a+1) recursively
                    :+            Sum the results

Mathematica, 96 94 88 Bytes

f=1##&@@#&;f[SeriesCoefficient[1/f[1-x^Range@#],{x,0,#}]&/@Last/@FactorInteger@#]Sign@#&

Ich beherrsche Mathematica nicht so gut, aber ich dachte, ich würde es versuchen. Danke an @ MartinBüttner für -6 Bytes.

Hierbei wird die Formel für die Generierungsfunktion für ganzzahlige Partitionen verwendet.

CJam, 58 Bytes

li_mF{1=_L{_1>{_2$<{\;_j}{\,f{)_@\-j}:+}?}{;;1}?}2j}%:*\g*

Probieren Sie es online aus

Das allerletzte Testbeispiel dauert im Online-Interpreter ewig (oder zumindest länger als ich gewartet habe), ist aber mit der Offline-Version von CJam auf meinem Laptop in 17 Sekunden abgeschlossen. Alle anderen Testbeispiele sind ziemlich augenblicklich.

Dies verwendet den CJam mF Operator, der die Primfaktorisierung mit Exponenten liefert. Das Ergebnis ist dann das Produkt der Partitionszählung für jeden Exponenten.

Der Hauptteil des Codes berechnet die Anzahl der Partitionen. Ich habe den rekursiven Algorithmus auf der Wikipedia-Seite mit dem jOperator implementiert, der Rekursion mit Memoisierung unterstützt.

Erläuterung:

li    Get input and convert to int.
_     Make a copy to handle 0 special case at the end.
mF    Factorization with exponents.
{     Loop over factors.
  1=    Take exponent from [factor exponent] pair.
  _     Repeat it, recursive calls are initiated with p(n, n).
  L     Empty list as start point of memoization state.
  {     Start recursive block. Argument order is (m, n), opposite of Wikipedia.
    _1>   Check for n > 1.
    {     Start n > 1 case.
      _2$   Copy both m and n.
      <     Check for n < m.
      {     n < m case.
        \;    Pop m.
        _     Copy n.
        j     Make the p(n, n) recursive call.
      }     End n < m case.
      {     Main part of algorithm that makes recursive calls in loop.
        \,    Generate [0 1 ... m-1] range for k.
        f{    Start loop over k.
          )     Increment, since k goes from 1 to m.
          _     Copy k.
          @\    Rotate n to top, and swap. Now have k n k at top of stack.
          -     Subtract, now have k n-k at top of stack.
          j     Make the p(n-k, k) recursive call.
        }     End loop over k.
        :+    Sum up all the values.
      }?    Ternaray operator for n < m condition.
    }     End n > 1 case.
    {     n <= 1 case.
      ;;1   Pop m, n values, and produce 1 as result.
    }?    Ternary operator for n > 1 condition.
  }2j   Recursive call with memoization, using 2 values.
}%    End loop over factors.
:*    Multiply all values.
\     Swap original input to top.
g     Signum.
*     Multiply to get 0 output for 0 input.