Reducción del divisor

21

Un divisor de un número n es cualquier número que divida uniformemente n , incluidos 1 yn . El número de divisores d (n) es cuántos divisores tiene un número. Aquí está d (n) para la primera pareja n:

n    divisors    d(n)
1    1           1
2    1, 2        2
3    1, 3        2
4    1, 2, 4     3
5    1, 5        2
6    1, 2, 3, 6  4

Podemos restar repetidamente el número de divisores de un número. Por ejemplo:

16                  = 16
16 - d(16) = 16 - 5 = 11
11 - d(11) = 11 - 2 = 9
 9 - d( 9) =  9 - 3 = 6
 6 - d( 6) =  6 - 4 = 2
 2 - d( 2) =  2 - 2 = 0

En este caso, tomó 5 pasos para llegar a 0.


Escriba un programa o función que, dado un número no negativo n, devuelva el número de pasos necesarios para reducirlo a 0 mediante la resta repetida del número de divisores.

Ejemplos:

0, 0
1, 1
6, 2
16, 5
100, 19
100000, 7534
orlp
fuente
55
Enlace OEIS obligatorio: A155043
Sp3000
Relacionado.
Martin Ender

Respuestas:

1

Jalea, 10 9 bytes

1 byte gracias a Dennis ♦ .

Puerto de mi respuesta en Pyth .

ÆDLạµÐĿL’

Pruébalo en línea!

Banco de pruebas.

Explicación

_ÆDL$$ÐĿL’
      ÐĿ    Repeat the following until result no longer unique:
 ÆD             Yield the array of the divisors
   L            Yield the length of the array
_               Subtract that from the number
        L   Number of iterations
         ’  Minus one.
Monja permeable
fuente
6

Python, 49 bytes

f=lambda n:n and-~f(sum(n%~x<0for x in range(n)))

¡orlp ayudó a salvar un byte! Y Sp3000 salvó dos más. ¡Gracias!

Lynn
fuente
1
Debería poder acortar las cosas moviendo el -~interior n%-~ky eliminando el límite inferior del rango.
orlp
5

C, 52 bytes

g,o;l(f){for(g=o=f;o;f%o--||--g);return f?1+l(g):0;}
Lynn
fuente
4

Pyth, 10 bytes

tl.ulf%NTS

Banco de pruebas.

Explicación

tl.ulf%NTS
tl.ulf%NTSNQ  implicit variables at the end
           Q  obtain the input number
  .u      N   repeat the following until result no longer unique:
         S        generate range from 1 to N
     f            filter for:
      %NT             T in that range, which N%T is truthy (not zero)
    l             length of that list
                  that means, we found the number of "non-divisors" of N
tl            number of iterations, minus 1.
Monja permeable
fuente
3

Julia, 31 bytes

f(n)=n<1?0:f(sum(n%(1:n).>0))+1

Implementación recursiva directa.

Sp3000
fuente
2

MATL , 14 bytes

`t~?x@q.]t:\zT

Pruébalo en línea!

Explicación

`            T  % Infinite loop
 t~?    ]       % Duplicate number. Is it non-zero?
    x@q.        % If so: delete number, push iteration index minus 1, break loop
         t:\    % Duplicate, range, modulo (remainder). Divisors give a 0 remainder
            z   % Number of non-zero elements; that is, of non-divisors
Luis Mendo
fuente
2

JavaScript (ES6), 64 51 bytes

f=n=>n&&[...Array(m=n)].map((_,i)=>m-=n%++i<1)|f(m)+1

No me preguntes por qué estaba usando innecesariamente la recursión de cola.

Neil
fuente
2

Java, 147 93

a->{int k,i,n=new Integer(a),l=0;for(;n!=0;n-=k)for(l+=k=i=1;i<n;)if(n%i++==0)++k;return l;}
Con suerte
fuente
3
¿Por qué en n=new Integer(100000)lugar de n=100000?
user8397947
1

05AB1E, 12 10 bytes

Código:

[Ð>#Ñg-¼]¾

Explicación:

[           # start infinite loop
 Ð          # triplicate current number
  >#        # increase by 1 and break if true
    Ñg      # get number of divisors
      -     # subtract number of divisors from number
       ¼    # increase counter
        ]   # end loop
         ¾  # print counter

Pruébalo en línea

Editar: 2 bytes guardados y un error con la entrada 0 corregida gracias a @Adnan

Emigna
fuente
¡Muy agradable! Traté de campo un poco, y lo consiguió hasta 10 bytes: [Ð>#Ñg-¼]¾. Sin embargo, tiene que haber una manera de acortarlo ...
Adnan
@LuisMendo Sí, es porque la D0Q#parte es después del incremento del contador. El [Ð>#Ñg-¼]¾código debe trabajar para 0aunque :).
Adnan
@Adnan: probé una versión basada en generar todos los recuentos hasta n e ir de índice a valor en el índice y contar, pero no pude acortarlo de esa manera.
Emigna
1

R, 50 bytes

Implementación bastante simple. Pruébalo en línea

z=scan();i=0;while(z>0){z=z-sum(z%%1:z<1);i=i+1};i
bola hinchable
fuente
1

Mathcad, [tbd] bytes

ingrese la descripción de la imagen aquí


El esquema de equivalencia de bytes de Mathcad aún no se ha determinado. Usando una equivalencia aproximada de teclas, el programa usa alrededor de 39 "bytes". Tenga en cuenta que los operadores while y para programación solo requieren una operación de teclado cada uno para ingresar (ctl-] y ctl-shft- #, respectivamente); de hecho, solo se pueden ingresar de esta manera desde el teclado.

Lo que ve es exactamente lo que se anota en una hoja de trabajo de Mathcad. Mathcad evalúa las ecuaciones / programas y coloca la salida en la misma hoja (p. Ej., Después del operador de evaluación '=' o en la gráfica).

Stuart Bruff
fuente
1

MATL, 13 bytes

tX`t:\ztt]Nq&

Pruébalo en línea

Explicación:

t               % Duplicate input
 X`      ]      % while loop, consumes 1 input
   t:\z         % calculates n-d(n), by counting number non-divisors
       tt       % dupe twice, for while loop condition, next iteration and to keep in stack
          Nq&   % get stack size, decrement, display that value
David
fuente
1

Mathematica, 35 bytes

If[#<1,0,#0[#-0~DivisorSigma~#]+1]&

Haciendo uso de los buenos viejos DivisorSigma. @ MartinBüttner señala las siguientes alternativas:

If[#<1,0,#0[#-DivisorSum[#,1&]]+1]&
f@0=0;f@n_:=f[n-DivisorSum[n,1&]]+1
Sp3000
fuente
1

Hoon , 93 76 bytes

|=
r/@
?~
r
0
+($(r (sub r (lent (skim (gulf 1^r) |=(@ =(0 (mod r +<))))))))

Sin golf:

|=  r/@
?~  r
  0
=+  (skim (gulf 1^r) |=(@ =(0 (mod r +<))))
+($(r (sub r (lent -))))

Devuelve una función que toma un átomo, r. Cree un valor intermedio que contenga todos los dispositivos der (Haga la lista [1..n], mantenga solo los elementos donde (mod ri) ​​== 0). Si res cero, devuelve cero; de lo contrario, devuelve el valor incrementado de recurrencia con r igual r- (divisores de longitud).

El código tal como está toma una estúpida cantidad de tiempo para evaluar n = 100.000, completamente porque encontrar los inventores para grandes números hace una lista gigante y mapas sobre él. Memorizar los divisores obtiene la salida correcta para n = 10.000, pero no me molesté en esperar 100.000

RenderSettings
fuente
1

Haskell, 43 40 39 bytes

g 0=0;g n=1+g(sum$min 1.mod n<$>[1..n])

Enfoque recursivo simple. Ejemplo de uso: g 16->5 .

Editar: @Lynn guardó 3 4 bytes. ¡Gracias!

nimi
fuente
¿Qué tal g(sum$signum.mod n<$>[1..n])?
Lynn
Ah, y en min 1realidad es un byte más corto que signum, incluso
Lynn
1

PowerShell v2 +, 74 67 bytes

param($n)for($o=0;$n-gt0){$a=0;1..$n|%{$a+=!($n%$_)};$n-=$a;$o++}$o

Parece bastante largo en comparación con algunas de las otras respuestas ...

Toma entrada $n, entra en un forbucle con la condición que $nes mayor que 0. En cada iteración de bucle establecemos ayudante $a, luego recorremos cada número desde 1hasta $n. Cada ciclo interno lo comprobamos contra cada número para ver si es un divisor, y si es así, incrementamos nuestro auxiliar $a(usando la negación booleana y la conversión implícita a int). Luego, restamos cuántos divisores hemos encontrado $n-=$ae incrementamos nuestro contador $o++. Finalmente, sacamos $o.

Lleva mucho tiempo ejecutarlo, ya que es una construcción significativa de bucle for. Por ejemplo, ejecutar n = 10,000en mi máquina (1 año de edad Core i5) toma casi 3 minutos.

AdmBorkBork
fuente
1

Raqueta - 126 bytes Hasta 98 ​​bytes 91 bytes

Una solución extremadamente ingenua: probablemente podría reducirse mucho con un algoritmo decente y algunos trucos de ceceo que no conozco

(define(g x[c 0][d 0][i 2])(cond[(= x 0)c][(= i x)(g d(+ 1 c))][(=(modulo x i)0)(g x c d(+ 1 i))][else(g x c(+ 1 d)(+ 1 i))]))

Editar: explicación por solicitud. Como dije, esta es una solución recursiva extremadamente ingenua y puede ser mucho más corta.

(define (g x [c 0] [d 0] [i 2]) ;g is the name of the function - arguments are x (input), c (counter for steps), d (non-divisor counter), i (iterator)
  (cond
    [(= x 0) c] ;once x gets to 0 c is outputted
    [(= i x) (g d (+ 1 c))] ;if iterator reaches x then we recurse with d as input and add 1 to c
    [(= (modulo x i) 0) (g x c d (+ 1 i))] ;checks if iterator is non divisor, then adds it to d and increments iterator
    [else(g x c (+ 1 d) (+ 1 i))])) ;otherwise just increments iterator

Edición 2: versión de 98 bytes con un algoritmo menos tonto (aunque sigue siendo bastante tonto y puede ser más corto)

(define(g x)(if(< x 1)0(+ 1(g(length(filter(λ(y)(>(modulo x y)0))(cdr(build-list x values))))))))

Explicación:

(define (g x) ;function name g, input x
  (if (< x 1)
      0 ;returns 0 if x < 1 (base case)
      (+ 1 ;simple recursion - adds 1 to output for each time we're looping
         (g (length ;the input we're passing is the length of... 
              (filter (λ (y) (> (modulo x y) 0)) ;the list where all numbers which are 0 modulo x are 0 are filtered out from...
                             (cdr (build-list x values)))))))) ;the list of all integers up to x, not including 0

Edición 3: guardado 7 bytes reemplazando (cdr(build-list x values))con(build-list x add1)

(define(g x)(if(< x 1)0(+ 1(g(length(filter(λ(y)(>(modulo x y)0))(build-list x add1)))))))
kronicmage
fuente
Hola y bienvenidos a PPCG! ¡Buena publicación! ¿Puedes explicar tu solución por favor? (PD: ¡Amo a Lisp!)
NoOneIsHere
@NoOneIsHere Editado en
kronicmage
0

> <> , 52 + 2 = 54 bytes

El número de entrada debe estar presente en la pila al inicio del programa, por lo que hay +2 bytes para el -vindicador. Pruébalo en línea!

:0)?v~ln;>~$-]
03[}\::
@@:$<    v?=0:-1}+{~$?@@01%@:

4 bytes molestos desperdiciados en problemas de alineación. Bah.

Este funciona construyendo la secuencia de na 0en la pila. Una vez que se ha alcanzado 0, explótelo y supere la longitud de la pila restante.

Por cierto, corre a O(n^2)tiempo, así que no lo intentaría n = 100000...

Sok
fuente
-ves un byte, no dos.
NoOneIsHere
0

> <> , 36 + 3 = 39 bytes

:?v~ln; >~&
:}\0&
+&>1-:?!^:{:}$%0)&

La implementación es relativamente sencilla, siendo cada iteración sum(n%k>0 for k in range(1,n-1)). +3 bytes para la -vbandera, por meta .

Pruébalo en línea!

Sp3000
fuente
0

Ruby, 42 bytes

f=->n{n<1?0:1+f[n-(1..n).count{|i|n%i<1}]}

Hay un error de desbordamiento de pila en el caso de prueba más grande 100000, así que aquí hay una versión iterativa dentro de 49 bytes . Sin embargo, toma un tiempo, considerando la O(N^2)complejidad.

->n{c=0;c+=1 while 0<n-=(1..n).count{|i|n%i<1};c}
Tinta de valor
fuente
0

Perl 5, 40 bytes

sub f{@_?(1,f((1)x grep@_%$_,1..@_)):()}

La entrada y salida son como listas del número requerido de copias de 1.

msh210
fuente
0

C #, 63 bytes

int F(int n)=>n<1?0:F(Enumerable.Range(1,n).Count(i=>n%i>0))+1;
RedLaser
fuente
0

En realidad, 17 bytes

";╗R`╜%`░l;"£╬klD

Pruébalo en línea! (nota: el último caso de prueba expira en TIO)

Explicación:

";╗R`╜%`░l;"£╬klD
"          "£╬     while top of stack is truthy, call the function:
 ;╗                  push a copy of n to reg0
   R                 range(1,n+1) ([1,n])
    `  `░l             push the number of values where the following is truthy:
     ╜%                  k mod n
                       (this computes the number of non-divisors of n)
          ;            make a copy
              klD  push entire stack as list, count number of items, subtract 1
                   (the result is the number of times the function was called)
Mego
fuente