Antecedentes

La última vez, contamos grupos de un tamaño determinado , lo cual es un problema no trivial.

Esta vez, solo contaremos grupos abelianos , es decir, grupos con una operación conmutativa. Formalmente, un grupo (G, *) es abeliano si x * y = y * x para para todo x, y en G .

El problema se vuelve mucho más simple de esta manera, por lo que vamos a contarlos de manera eficiente.

Tarea

Escriba un programa o función que acepte un número entero no negativo n como entrada e imprima o devuelva el número de grupos abelianos no isomórficos de orden n .

Una forma de calcular el número de grupos, que denotaremos con A (n) , es observando lo siguiente:

• A (0) = 0

• Si p es primo, A (p ^k ) es igual al número de particiones enteras de k . (cfr. OEIS A000041 )

• Si n = mk , y m y k son co-primos, A (n) = A (m) A (k) .

Puede usar este o cualquier otro método para calcular A (n) .

Casos de prueba

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

(tomado de OEIS A000688 )

Reglas adicionales

• Dado el tiempo suficiente, RAM y un tamaño de registro que puede contener la entrada, su código debería funcionar (en teoría) para enteros arbitrariamente grandes.

• El código debe funcionar para todos los números enteros entre 0 y 2 ⁶³ - 1 y el acabado en menos de 10 minutos en mi máquina (Intel i7-3770, 16 GiB de RAM, Fedora 21).

  Asegúrese de cronometrar su código para los últimos tres casos de prueba antes de enviar su respuesta.

• FiniteAbelianGroupCountNo se permiten las funciones integradas que trivializan esta tarea, como las de Mathematica .

• No se permiten los elementos integrados que devuelven o cuentan las particiones enteras de un número o las particiones de una lista.

• Se aplican reglas estándar de código de golf .

CJam ( 39 38 bytes)

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

Demostración en línea

Esto sigue la línea sugerida de encontrar una factorización prima ( mF) y luego calcular las particiones de cada potencia y tomar su producto.

Hay dos casos especiales para mF: factoriza 0como 0^1y 1como1^1 . Este último no requiere un tratamiento especial: hay un grupo abeliano de tamaño 1 y una partición de 1. Sin embargo, cero requiere un caso especial.

El recuento de particiones usa una recurrencia para A008284(n, k)el número de particiones nen kpartes. En OEIS se da como

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

pero creo que es más útil pensar que la suma va de 1a min(k, n-k).

Disección

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&

Utiliza la mFfactorización integrada de CJam y un puerto memorizado de esta función de número de partición de Python:

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

o sin golf:

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)

Al igual que la respuesta de @ RetoKoradi, el último caso tarda unos 17 segundos en el intérprete fuera de línea porque eso es lo que le toma a CJam factorizar el número. Por lo tanto, lo he dejado fuera de este conjunto de pruebas en línea .

Explicación completa

[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@#&

No soy tan competente con Mathematica, pero pensé en intentarlo. Gracias a @ MartinBüttner por -6 bytes.

Esto usa la fórmula de la función generadora para particiones enteras.

CJam, 58 bytes

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

Pruébalo en línea

El último ejemplo de prueba lleva una eternidad (o al menos más de lo que estaba dispuesto a esperar) en el intérprete en línea, pero termina en 17 segundos con la versión fuera de línea de CJam en mi computadora portátil. Todos los demás ejemplos de prueba son casi instantáneos.

Esto usa el CJam mF operador , que proporciona la factorización prima con exponentes. El resultado es entonces el producto de los recuentos de partición para cada exponente.

La parte principal del código es calcular los recuentos de particiones. Implementé el algoritmo recursivo en la página de wikipedia , utilizando el joperador que admite la recursividad con la memorización.

Explicación:

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.