Números altamente compuestos

23

Un número altamente compuesto es un número entero positivo que tiene más divisores que cualquier número entero positivo más pequeño. Esta es la secuencia OEIS A002182 . Sus primeros 20 términos son

1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, 7560

Por ejemplo, 4 está en la secuencia porque tiene 3 divisores (es decir, 1, 2, 4), mientras que 3 solo tiene 2 divisores, 2 también tiene 2 divisores y 1 tiene 1 divisores.

Reto

Dada una entrada entera positiva n , emite el n -ésimo número altamente compuesto o los primeros n números altamente compuestos, a su elección (pero la elección debe ser la misma para cada entrada n ).

Reglas

El programa o función debería funcionar teóricamente para entradas arbitrariamente grandes con tiempo y memoria infinitos, y sin tener en cuenta las limitaciones del tipo de datos. Esencialmente, esto significa que no hay que codificar un número finito de valores.

En la práctica, el programa o función debe ejecutarse en un período de tiempo razonable, digamos menos de 1 minuto, para n hasta 20. La entrada o salida máxima puede estar limitada por el tipo de datos estándar de su idioma (pero nuevamente, el algoritmo debería funcionar teóricamente para números arbitrariamente grandes).

Se permite cualquier formato de entrada y salida razonable, incluido el unario.

Código de golf. Pocos bytes ganan.

Luis Mendo
fuente
Esta conversación se ha movido al chat .
Dennis
¿Puede el n -ésimo índice estar indexado a cero o debe estar 1 indexado?
Adnan
@AndN No había pensado en eso, así que digamos que ambos son aceptados. (Me parece recordar una meta publicación que propone que tanto el 1 como el 0 están permitidos, pero no puedo encontrarlo. ¿Alguien?)
Luis Mendo

Respuestas:

4

05AB1E , 15 14 bytes

La entrada en cero indexado. Eso significa que n = 0da 1, n = 1da 2, etc. Código:

$µ>DÑgD®›i©¼}\

Explicación:

$               # Pushes 1 and input
 µ              # Counting loop, executes until the counting variable is equal to input
  >             # Increment (n + 1)
   DÑ           # Duplicate and calculate all divisors
     gD         # Get the length of the array and duplicate
       ®        # Retrieve element, standardized to zero
        ›i  }   # If greater than, do...
          ©     #   Copy value into the register
           ¼    #   Increment on the counting variable
             \  # Pop the last element in the stack

Calcula n = 19 , que debería dar 7560en unos 10 segundos.

Pruébalo en línea!

Utiliza la codificación CP-1252 .

Adnan
fuente
5

Jalea, 15 bytes

,®ÆDL€ṛ©0>/?µƓ#

Para la entrada n , imprime el primer n números altamente compuestos.

Para n = 20 , lleva menos de dos segundos probarlo en línea.

Cómo funciona

,®ÆDL€ṛ©0>/?µƓ#  Main link. No implicit input.

            µ    Push the chain to the left on the local link stack.
             Ɠ   Read an integer n from STDIN.
              #  Execute the chain for k = 0, 1, 2, ..., until it returned a truthy
                 value n times. Return the list of matches.

,®               Pair k with the value in the register (initially 0).
  ÆD             Compute the divisors of k and the register value.
    L€           Count both lists of divisors.
           ?     If
         >/        k has more divisors than the register value:
      ṛ©             Save k in the register and return k.
        0          Else: Return 0.

Versión alternativa, 13 bytes (no competitiva)

Si bien el código siguiente funcionó en la última versión de Jelly que precede a este desafío, la implementación Mfue muy lenta y no cumplió con el límite de tiempo. Esto ha sido arreglado.

ÆDL®;©MḢ’>µƓ#

Pruébalo en línea!

Cómo funciona

ÆDL®;©MḢ’>µƓ#  Main link. No implicit input.

          µ    Push the chain to the left on the local link stack.
           Ɠ   Read an integer n from STDIN.
            #  Execute the chain for k = 0, 1, 2, ..., until it returned a truthy
               value n times. Return the list of matches.

ÆD             Compute the divisors of k.
  L            Count them.
   ®;          Append the count to the list in the register (initially 0 / [0]).
     ©         Save the updated list in the register.
      M        Obtain all indices the correspond to maximal elements.
       Ḣ       Retrieve the first result.
        ’>     Subtract 1 and compare with k.
               This essentially checks if the first maximal index is k + 2, where
               the "plus 2" accounts for two leading zeroes (initial value of the
               register and result for k = 0).
Dennis
fuente
1
También hay RÆDL€MḢ=µƓ#(11 bytes), pero tarda 44 minutos en mi máquina ...
Dennis
3

MATL , 26 24 bytes

~XKx`K@@:\~s<?@5MXKx]NG<

Pruébalo en línea!

El mayor número actual de divisores encontrados se mantiene en el portapapeles K. Los números altamente compuestos (HCN) se guardan directamente en la pila. Un bucle sigue probando candidatos para HCN. Cuando se encuentra uno, se deja en la pila y se actualiza el portapapeles K. El ciclo sale cuando se ha encontrado el número deseado de HCN.

~         % take input implicitly (gets stored in clipboard G). Transform into a 0 
          % by means of logical negation
XKx       % copy that 0 into clipboard K, and delete
`         % do...while
  K       %   push largest number of divisors found up to now
  @       %   push iteration index, i: current candidate to HCN
  @:      %   range [1,...,i]
  \       %   modulo operation
  ~s      %   number of zeros. This is the number of divisors of current candidate
  <       %   is it larger than previous largest number of divisors?
  ?       %   if so: a new HCN has been found
    @     %     push that number
    5M    %     push the number of divisors that was found
    XKx   %     update clipboard K, and delete
  ]       %   end if
  N       %   number of elements in stack
  G<      %   is it less than input? This the loop condition: exit when false
          % end do...while implicitly
          % display all numbers implicitly
Luis Mendo
fuente
3

Perl, 60 57 + 1 = 58 bytes

$,++;$==grep$,%$_<1,1..$,;$_--,$m=$=if$=>$m;$_?redo:say$,

Requiere -ny el libre -M5.010| -E:

$ perl -nE'$,++;$==grep$,%$_<1,1..$,;$_--,$m=$=if$=>$m;$_?redo:say$,' <<< 10 
120

Cómo funciona:

$,++;
     $==grep$,%$_<1,1..$,;                                # Calculate total numbers of divisors for `$,`
                          $_--,$m=$=if$=>$m;              # Set `$m`ax divisors to `$=`ivisors if `$m>$=`
                                            $_?redo:say$, # Repeat or print
andlrc
fuente
2

JavaScript (ES6) 72

Implementación directa. Tiempo cercano a 20 segundos para la entrada 20

x=>{for(i=e=n=0;i<x;d>e&&(++i,e=d))for(d=1,j=++n;--j;)n%j||++d;return n}

El truco eval podría ahorrar un byte duplicando el tiempo de ejecución

x=>eval("for(i=e=n=0;i<x;d>e&&(++i,e=d))for(d=1,j=++n;--j;)n%j||++d;n")

Menos golf

x=>{
  for(i = e = 0, n = 1; i < x; n++)
  {
    for(d = 1, j = n; --j; )
    {
      if (n%j == 0) 
        ++d;
    }
    if (d > e)
      ++i,
      e = d;
  }
  return n;
}
edc65
fuente
2

Pyth, 17 16 bytes

1 byte gracias a Jakube

uf<Fml{yPd,GTGQ1

Banco de pruebas

Toma un n indexado por 0 y devuelve el enésimo número altamente compuesto.

Explicación:

uf<Fml{yPd,GThGQ1
                     Input: Q = eval(input())
u              Q1    Apply the following function Q times, starting with 1.
                     Then output the result. lambda G.
 f           hG      Count up from G+1 until the following is truthy, lambda T.
          ,GT        Start with [G, T] (current highly comp., next number).
    m                Map over those two, lambda d.
        Pd           Take the prime factorization of d, with multiplicity.
       y             Take all subsets of those primes.
      {              Deduplicate. At this point, we have a list of lists of primes.
                     Each list is the prime factorization of a different factor.
     l               Take the length, the number of factors.
  <F                 Check whether the number of factors of the previous highly
                     composite number is smaller than that of the current number.
isaacg
fuente
1

Rubí, 70 69 67 66 64 62

->n{r=k=0
0until(r<t=(1..k+=1).count{|d|k%d<1})&&1>n-=t/r=t
k}

Implementación directa.

Mitch Schwartz
fuente
1

C, 98 bytes

f,i,n,j;main(m){for(scanf("%d",&n);n--;printf("%d ",i))for(m=f;f<=m;)for(j=++i,f=0;j;)i%j--||f++;}

Probarlo aquí .

Sin golf

f,i,n,j;

main(m)
{
    for(scanf("%d",&n); /* Get input */
            n--; /* Loop while still HCN's to calculate... */
            printf("%d ",i)) /* Print out the last calculated HCN */
        for(m=f;f<=m;) /* Loop until an HCN is found... */
            for(j=++i,f=0;j;) /* Count the number of factors */
                i%j--||f++;
}
Cole Cameron
fuente
1

Python 3, 97 bytes

i=p=q=0;n=int(input())
while q<n:
 c=j=0;i+=1
 while j<i:j+=1;c+=i%j==0
 if c>p:p=c;q+=1
print(i)

Un programa completo que toma la entrada de STDIN e imprime la salida a STDOUT. Esto devuelve el nnúmero 1 altamente compuesto indexado.

Cómo funciona

Esta es una implementación sencilla. La entradan es el índice numérico altamente compuesto.

El programa itera sobre los enteros i. Para cada número entero jmenor que i, i mod jse toma; si es así 0, jdebe ser un factor de iy el contador cse incrementa, dando el número de divisores de idespués del bucle. pes el número más alto anterior de divisores, por lo que si c > pse ha encontrado un nuevo número altamente compuesto y el contador qse incrementa. Una vez q = n, idebe ser el nnúmero altamente compuesto, y esto se imprime.

Pruébalo en Ideone

(Esto lleva unos 15 segundos n = 20, lo que excede el límite de tiempo para Ideone. Por lo tanto, el ejemplo dado es para n = 18).

TheBikingViking
fuente
0

Python 2, 207 bytes

n,i,r,o=input(),1,[],[]
while len(o)<n:
 r+=[(lambda n:len(set(reduce(list.__add__,([i,n//i]for i in range(1,int(n**0.5)+1)if n%i==0)))))(i)];h=max(r)
 if r.index(h)>i-2 and r.count(h)<2:o+=[i]
 i+=1
print o

Utiliza el mismo método que Dennis 'Jelly answer. Calcula los primeros 20 términos en <2segundos.

Puertas de Zach
fuente