¿Cuántos pasos toma de n a 1 restando el máximo divisor?

50

Inspirado por esta pregunta en Mathematics .


El problema

Dejar nser un número natural ≥ 2. Tome el divisor más grande de n, que es diferente de nsí mismo, y restarlo n. Repita hasta que llegue 1.

La pregunta

¿Cuántos pasos se necesitan para alcanzar 1un número dado n ≥ 2?

Ejemplo detallado

Dejar n = 30.

El mayor divisor de:

1.   30 is 15  -->  30 - 15 = 15
2.   15 is  5  -->  15 -  5 = 10
3.   10 is  5  -->  10 -  5 =  5
4.    5 is  1  -->   5 -  1 =  4
5.    4 is  2  -->   4 -  2 =  2
6.    2 is  1  -->   2 -  1 =  1

Se necesitan 6 pasos para llegar 1.

Entrada

  • La entrada es un número entero n, donde n ≥ 2.
  • Su programa debe admitir la entrada hasta el valor entero máximo del idioma.

Salida

  • Simplemente envíe el número de pasos, como 6.
  • Los espacios en blanco iniciales o finales o las nuevas líneas están bien.

Ejemplos

f(5)        --> 3
f(30)       --> 6
f(31)       --> 7
f(32)       --> 5
f(100)      --> 8
f(200)      --> 9
f(2016^155) --> 2015

Requisitos

  • Puede obtener información de STDIN, argumentos de línea de comando, como parámetros de función o del equivalente más cercano.
  • Puedes escribir un programa o una función. Si es una función anónima, incluya un ejemplo de cómo invocarla.
  • Este es el por lo que la respuesta más corta en bytes gana.
  • Las lagunas estándar no están permitidas.

Esta serie también se puede encontrar en OEIS: A064097

Un cuasi-logaritmo definido inductivamente por a(1) = 0y a(p) = 1 + a(p-1)si pes primo y a(n*m) = a(n) + a(m)si m,n > 1.

insertusernamehere
fuente
¿Clarifica el requisito de entrada en idiomas con enteros de precisión arbitrarios nativos?
Sparr
@Sparr Yo diría que al menos deberías apoyar hasta 2^32 - 1. El resto depende de usted y su sistema. Espero, esto es lo que quisiste decir con tu pregunta.
insertusernamehere
3
Me gusta cómo lo resume todo el título
Luis Mendo

Respuestas:

20

Jalea , 9 bytes

ÆṪÐĿÆFL€S

Pruébalo en línea! o verificar todos los casos de prueba .

Antecedentes

La definición de secuencia A064097 implica que

definición

Por la fórmula del producto de Euler

Fórmula del producto de Euler

donde φ denota la función totient de Euler y p varía solo sobre los números primos.

Combinando ambos, deducimos la propiedad

primera propiedad

donde ω denota el número de factores primos distintos de n .

Aplicando la fórmula resultante k + 1 veces, donde k es lo suficientemente grande como para que φ k + 1 (n) = 1 , obtenemos

segunda propiedad

De esta propiedad, obtenemos la fórmula

fórmula

donde se mantiene la última igualdad porque ω (1) = 0 .

Cómo funciona

ÆṪÐĿÆFL€S  Main link. Argument: n

  ÐĿ       Repeatedly apply the link to the left until the results are no longer
           unique, and return the list of unique results.
ÆṪ           Apply Euler's totient function.
           Since φ(1) = 1, This computes φ-towers until 1 is reached.
    ÆF     Break each resulting integer into [prime, exponent] pairs.
      L€   Compute the length of each list.
           This counts the number of distinct prime factors.
        S  Add the results.
Dennis
fuente
¡Ahora ese es un enfoque súper inteligente!
Abr001am
15

05AB1E , 13 11 bytes

Código:

[DÒ¦P-¼D#]¾

Explicación:

[        ]   # An infinite loop and...
       D#        break out of the loop when the value is equal to 1.
 D           # Duplicate top of the stack (or in the beginning: duplicate input).
  Ò          # Get the prime factors, in the form [2, 3, 5]
   ¦         # Remove the first prime factor (the smallest one), in order to get 
               the largest product.
    P        # Take the product, [3, 5] -> 15, [] -> 1.
     -       # Substract from the current value.
      ¼      # Add one to the counting variable.
          ¾  # Push the counting variable and implicitly print that value.

Utiliza la codificación CP-1252 . Pruébalo en línea! .

Adnan
fuente
13
Elimine el primer factor primo (el más pequeño) para obtener el producto más grande ¡ Qué inteligente! :-)
Luis Mendo
Ya veo, usted es el desarrollador del lenguaje
Sarge Borsch
@SargeBorsch Sí, eso es correcto :)
Adnan
[¼Ñü-¤ÄD#]¾- Estaba cerca de afeitarme un byte con pares, oh bueno ...
Urna mágica de pulpo
-1 byte: [Ð#Ò¦P-¼]¾. Ðes mejor que DD.
Grimmy
11

Pyth, 11 bytes

fq1=-Q/QhPQ

Banco de pruebas

Un bucle sencillo de repetir hasta que sea verdadero.

Explicación:

fq1=-Q/QhPQ
               Implicit: Q = eval(input())
f              Apply the following function until it is truthy,
               incrementing T each time starting at 1:
         PQ    Take the prime factorization of Q
        h      Take its first element, the smallest factor of Q
      /Q       Divide Q by that, giving Q's largest factor
    -Q         Subtract the result from Q
   =           Assign Q to that value
 q1            Check if Q is now 1.
isaacg
fuente
Es un buen truco con fIlter.
Maltysen
3
No entiendo por qué esto genera la cantidad de veces que se ejecutó la función. ¿Es esta una característica indocumentada de f?
corsiKa
@corsiKa fsin un segundo argumento itera sobre todos los enteros positivos a partir de 1y devuelve el primer valor que da verdadero en la declaración interna. Este valor no se utiliza en este programa, por lo que devuelve el número de veces que se ejecutó. No indocumentado, simplemente no ortodoxo :) Si ayuda, puede pensar en esto como un forbucle como:for(int i=1; some_condition_unrelated_to_i; i++) { change_stuff_that_affects_condition_but_not_i;}
FryAmTheEggman
@corsiKa Está documentado en la referencia del personaje en el lado derecho del intérprete en línea. Con solo un argumento ( f <l:T> <none>), fes la primera entrada donde A(_)termina la verdad[1, 2, 3, 4...] .
Dennis
Ah lo entiendo ahora. Utiliza esa entrada pero nunca usa la entrada en el cálculo . Eso explica el comentario de @Maltysen de "es un truco muy bueno" porque solo te importa que el recuento de iteraciones no use ese recuento en ninguna parte del filtro. ¡Me encantan esos momentos ah-ha !
:)
7

Python 2, 50 49 bytes

f=lambda n,k=1:2/n or n%(n-k)and f(n,k+1)or-~f(k)

Esto no va a terminar ese último caso de prueba en el corto plazo ...

Alternativamente, aquí hay un byte de 48 que devuelve en Truelugar de 1para n=2:

f=lambda n,k=1:n<3or n%(n-k)and f(n,k+1)or-~f(k)
Sp3000
fuente
6

Jalea , 10 bytes

ÆfḊPạµÐĿi2

Pruébalo en línea! o verificar la mayoría de los casos de prueba . Los últimos casos de prueba finalizan rápidamente localmente.

Cómo funciona

ÆfḊPạµÐĿi2  Main link. Argument: n (integer)

Æf          Factorize n, yielding a list of primes, [] for 1, or [0] for 0.
  Ḋ         Dequeue; remove the first (smallest) element.
   P        Take the product.
            This yields the largest proper divisor if n > 1, 1 if n < 2.
    ạ       Yield the abs. value of the difference of the divisor (or 1) and n.
     µ      Convert the chain to the left into a link.
      ÐĿ    Repeatedly execute the link until the results are no longer unique.
            Collect all intermediate results in a list.
            For each starting value of n, the last results are 2 -> 1 -> 0 (-> 1).
        i2  Compute the 1-based index of 2.
Dennis
fuente
5

Retina , 12

  • 14 bytes guardados gracias a @ MartinBüttner
(1 +) (? = \ 1 + $)

Esto supone la entrada dada en unario y la salida dada en decimal. Si esto no es aceptable, podemos hacer esto por 6 bytes más:

Retina , 18

  • 8 bytes guardados gracias a @ MartinBüttner
. +
PS
(1 +) (? = \ 1 + $)

Pruébelo en línea: se agregó la primera línea para ejecutar todos los casos de prueba de una vez.

Lamentablemente, esto utiliza unario para los cálculos, por lo que la entrada de 2016 155 no es práctica.

  • La primera etapa (2 líneas) simplemente convierte la entrada decimal a unaria como una cadena de 1s
  • La segunda etapa (1 línea) calcula el factor más grande de n usando grupos de coincidencia de expresiones regulares y mira hacia atrás y lo resta efectivamente de n. Esta expresión regular coincidirá tantas veces como sea necesario para reducir el número lo más posible. El número de coincidencias de expresiones regulares será el número de pasos, y se muestra en esta etapa.
Trauma digital
fuente
No creo que necesites el \b.
Martin Ender
Sin embargo, puede ahorrar mucho más así y técnicamente tampoco necesita la primera etapa .
Martin Ender
@ MartinBüttner ¡Fantástico! Muy elegante, gracias!
Trauma digital
5

Pyth - 15 14 13 bytes

La carcasa especial 1realmente me está matando.

tl.u-N/Nh+PN2

Pruébelo en línea aquí .

tl                One minus the length of
 .u               Cumulative fixed point operator implicitly on input
  -N              N -
   /N             N /
    h             Smallest prime factor
     +PN2         Prime factorization of lambda var, with two added to work with 1
Maltysen
fuente
1
Una cosa que siempre olvido ... la fuerza bruta es a menudo el enfoque más golfista
Leaky Nun
¿Qué quieres decir con carcasa especial 1?
Adnan
1
@Adnan la factorización principal de 1is [], que causa un error cuando tomo el primer elemento. Tengo que ponerlo en un caso especial para que vuelva de 1nuevo para que .utermine el punto fijo. Encontré una mejor manera que .xtry, excepto que es lo que me ahorró esos 2 bytes.
Maltysen
Solo necesita aceptar números> = 2 (> 1).
Solomon Ucko
@SolomonUcko estás malinterpretando, el .upunto fijo eventualmente alcanzará 1todas las entradas, en cuyo punto tendrá que estar en una carcasa especial.
Maltysen
5

JavaScript (ES6), * 44 38

Editar 6 bytes guardados gracias @ l4m2

(* 4 marcado sigue siendo 4)

Función recursiva

f=(n,d=n)=>n>1?n%--d?f(n,d):f(n-d)+1:0

Menos golf

f=(n, d=n-1)=>{
  if (n>1)
    if(n % d != 0)
      return f(n, d-1) // same number, try a smaller divisor
    else
      return f(n-d)+1  // reduce number, increment step, repeat
  else
    return 0
}

Prueba

f=(n,d=n)=>n>1?n%--d?f(n,d):f(n-d)+1:0

console.log=x=>O.textContent+=x+'\n';

[5,30,31,32,100,200].forEach(x=>console.log(x+' -> '+f(x)))
<pre id=O></pre>

edc65
fuente
Bien, pero creo que deberías gastar los dos bytes necesarios para hacer f (1) == 0.
Neil
@Neil pensando de nuevo: no. "Sea n un número natural ≥ 2 ..."
edc65
Necesito lentes nuevos.
Neil
¿Por qué no f=(n,d=n)=>n>1?n%--d?f(n,d):f(n-d)+1:0?
l4m2
@ l4m2 bien, ¿por qué no? Gracias
edc65
4

Mathematica, 36 bytes

f@1=0;f@n_:=f[n-Divisors[n][[-2]]]+1

Una función sin nombre toma los mismos bytes:

If[#<2,0,#0[#-Divisors[#][[-2]]]+1]&

Esta es una implementación muy sencilla de la definición como una función recursiva.

Martin Ender
fuente
4

Octava, 59 58 55 bytes

function r=f(x)r=0;while(x-=x/factor(x)(1));r++;end;end

Actualizado gracias a Stewie Griffin, ahorrando 1 byte

Actualización adicional, ahorrando tres bytes más utilizando el resultado de la factorización en while-check.

Ejecuciones de muestra:

octave:41> f(5)
ans =  3
octave:42> f(30)
ans =  6
octave:43> f(31)
ans =  7
octave:44> f(32)
ans =  5
octave:45> f(100)
ans =  8
octave:46> f(200)
ans =  9
dcsohl
fuente
¿Es el último endnecesario en octava?
Abr001am
Está. Noté que no estaba en matlab por sus respuestas, pero Octave lo espera (como aprendí al probar la suya en Octave).
dcsohl
4

Haskell, 59 bytes

f 1=0;f n=1+(f$n-(last$filter(\x->n`mod`x==0)[1..n`div`2]))

Uso:

Prelude> f 30
Prelude> 6

Puede ser un poco ineficiente para grandes números debido a la generación de la lista.

Alexandru Dinu
fuente
1
Lista de comprensión y en <1lugar de ==0guardar unos pocos bytes: f 1=0;f n=1+f(n-last[a|a<-[1..ndiv2],mod n a<1])
Angs
4

Julia, 56 50 45 39 bytes

f(n)=n>1&&f(n-n÷first(factor(n))[1])+1

Esta es una función recursiva que acepta un entero y devuelve un entero.

Sin golf:

function f(n)
    if n < 2
        # No decrementing necessary
        return 0
    else
        # As Dennis showed in his Jelly answer, we don't need to
        # divide by the smallest prime factor; any prime factor
        # will do. Since `factor` returns a `Dict` which isn't
        # sorted, `first` doesn't always get the smallest, and
        # that's okay.
        return f(n - n ÷ first(factor(n))[1]) + 1
    end
end

Pruébalo en línea! (incluye todos los casos de prueba)

¡Ahorré 6 bytes gracias a Martin Büttner y 11 gracias a Dennis!

Alex A.
fuente
3

PowerShell v2 +, 81 bytes

param($a)for(;$a-gt1){for($i=$a-1;$i-gt0;$i--){if(!($a%$i)){$j++;$a-=$i;$i=0}}}$j

La más brutal de las fuerzas brutas.

Toma entrada $a, ingresa un forbucle hasta que $asea ​​menor o igual que 1. Cada ciclo pasamos por otro forciclo que cuenta hacia atrás $ahasta que encontremos un divisor ( !($a%$i). En el peor de los casos, lo encontraremos $i=1como divisor. Cuando lo hagamos, incremente nuestro contador $j, reste nuestro divisor $a-=$iy prepárese $i=0para salir del bucle interno. Eventualmente, llegaremos a una condición en la que el bucle externo es falso (es decir, $aha alcanzado 1), por lo que sale $jy sale.

Precaución : esto llevará mucho tiempo en números más grandes, especialmente en números primos. La entrada de 100,000,000 toma ~ 35 segundos en mi computadora portátil Core i5. Editar : solo probé con [int]::MaxValue(2 ^ 32-1), y tardó ~ 27 minutos. No es demasiado mala, supongo.

AdmBorkBork
fuente
3

Matlab, 58 bytes

function p=l(a),p=0;if(a-1),p=1+l(a-a/min(factor(a)));end
Abr001am
fuente
3

Japt , 12 bytes (no competidor)

@!(UµUk Å×}a

¡Pruébelo en línea! No compite porque usa un montón de características que se agregaron mucho después de que se publicó el desafío.

Cómo funciona

@   !(Uµ Uk Å  ×   }a
XYZ{!(U-=Uk s1 r*1 }a
                       // Implicit: U = input integer
XYZ{               }a  // Return the smallest non-negative integer X which returns
                       // a truthy value when run through this function:
         Uk            //   Take the prime factorization of U.
            s1         //   Slice off the first item.
                       //   Now we have all but the smallest prime factor of U.
               r*1     //   Reduce the result by multiplication, starting at 1.
                       //   This takes the product of the array, which is the
                       //   largest divisor of U.
      U-=              //   Subtract the result from U.
    !(                 //   Return !U (which is basically U == 0).
                       //   Since we started at 0, U == 1 after 1 less iteration than
                       //   the desired result. U == 0 works because the smallest
                       //   divisor of 1 is 1, so the next term after 1 is 0.
                       // Implicit: output result of last expression

Esta técnica se inspiró en la respuesta 05AB1E . Se usó una versión anterior ²¤(empuje un 2, corte los dos primeros elementos) en lugar de Åporque es un byte más corto que s1 (espacio final de la nota); Solo me di cuenta después del hecho de que debido a que esto agrega un 2 al final de la matriz y los segmentos desde el principio , de hecho falla en cualquier número compuesto impar, aunque funciona en todos los casos de prueba dados.

ETHproducciones
fuente
2

Python 3, 75, 70 , 67 bytes.

g=lambda x,y=0:y*(x<2)or[g(x-z,y+1)for z in range(1,x)if x%z<1][-1]

Esta es una solución recursiva bastante sencilla. Lleva mucho tiempo para los casos de prueba de gran número.

Morgan Thrapp
fuente
2

> <>, 32 bytes

<\?=2:-$@:$/:
1-$:@@:@%?!\
;/ln

Espera el número de entrada,, nen la pila.

Este programa construye la secuencia completa en la pila. Como el único número que puede conducir 1es 2, la construcción de la secuencia se detiene cuando 2se alcanza. Esto también hace que el tamaño de la pila sea igual al número de pasos, en lugar del número de pasos +1.

Sok
fuente
2

Ruby, 43 bytes

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

Encuentre el número más pequeño de imanera que se xdivida x-iy se repita hasta que alcancemos 1.

histocrat
fuente
2

Haskell, 67 bytes

Aquí está el código:

a&b|b<2=0|a==b=1+2&(b-1)|mod b a<1=1+2&(b-div b a)|1<2=(a+1)&b
(2&)

Y aquí hay una razón por la que Haskell es increíble:

f = (2&)

(-->) :: Eq a => a -> a -> Bool
(-->) = (==)

h=[f(5)        --> 3
  ,f(30)       --> 6
  ,f(31)       --> 7
  ,f(32)       --> 5
  ,f(100)      --> 8
  ,f(200)      --> 9
  ,f(2016^155) --> 2015
  ]

Sí, en Haskell puedes definir -->ser equivalente a ==.

Michael Klein
fuente
2

Matlab, 107 bytes

a=input('');b=factor(a-isprime(a));c=log2(a);while(max(b)>1),b=max(factor(max(b)-1));c=c+1;end,disp(fix(c))
  • Sin competencia, esta no es la traducción iterativa de mi última presentación, solo otro método algerbraico directo, resume todos los registros binarios de todos los factores primos, algo ambiguo para ilustrar.
  • Jugaré más golf cuando tenga tiempo.
Abr001am
fuente
2

MATL, 17 16 bytes

`tttYfl)/-tq]vnq

Pruébalo en línea

Explicación

        % Implicitly grab input
`       % Do while loop
    ttt % Make three copies of top stack element
    Yf  % Compute all prime factors
    l)  % Grab the smallest one
    /   % Divide by this to get the biggest divisor
    -   % Subtract the biggest divisor
    t   % Duplicate the result
    q   % Subtract one (causes loop to terminate when the value is 1). This
        % is functionally equivalent to doing 1> (since the input will always be positive) 
        % with fewer bytes
]       % End do...while loop
v       % Vertically concatenate stack contents (consumes entire stack)
n       % Determine length of the result
q       % Subtract 1 from the length
        % Implicitly display result
Suever
fuente
2

C99, 62 61 bytes

1 byte jugado por @Alchymist.

f(a,c,b)long*c,a,b;{for(*c=0,b=a;a^1;a%--b||(++*c,b=a-=b));}  

Llame como f (x, & y), donde x es la entrada e y es la salida.

milIbyte
fuente
Si prueba un% - b, entonces puede evitar el b-- al final. Todo un byte de ahorro.
Alchymist
2

Clojure, 116104 bytes

(fn[n](loop[m n t 1](let[s(- m(last(filter #(=(rem m %)0)(range 1 m))))](if(< s 2)t(recur s (inc t))))))

-12 bytes filtrando un rango para encontrar múltiplos, luego usando lastuno para obtener el mayor

Solución ingenua que básicamente solo resuelve el problema tal como lo describe el OP. Desafortunadamente, encontrar el divisor más grande solo ocupa la mitad de los bytes utilizados. Al menos debería tener mucho espacio para jugar golf desde aquí.

Pregolfed y prueba:

(defn great-divider [n]
  ; Filter a range to find multiples, then take the last one to get the largest
  (last
     (filter #(= (rem n %) 0)
             (range 1 n))))

(defn sub-great-divide [n]
  (loop [m n
         step 1]
    (let [g-d (great-divider m) ; Find greatest divisor of m
          diff (- m g-d)] ; Find the difference
      (println m " is " g-d " --> " m " - " g-d " = " diff)
      (if (< diff 2)
        step
        (recur diff (inc step))))))

(sub-great-divide 30)

30  is  15  -->  30  -  15  =  15
15  is  5  -->  15  -  5  =  10
10  is  5  -->  10  -  5  =  5
5  is  1  -->  5  -  1  =  4
4  is  2  -->  4  -  2  =  2
2  is  1  -->  2  -  1  =  1
6
Carcigenicate
fuente
1
@insertusernamehereNo, desafortunadamente, porque todos son identificadores válidos. He eliminado todos los espacios en blanco posibles. Si quiero seguir jugando al golf, necesitaré volver a trabajar el algoritmo.
Carcigenicate
2

Perl 6 , 35 bytes

{+({$_ -first $_%%*,[R,] ^$_}...1)}

Pruébalo en línea!

Cómo funciona

{                                 }   # A bare block lambda.
                    [R,] ^$_          # Construct range from arg minus 1, down to 0.
        first $_%%*,                  # Get first element that is a divisor of the arg.
    $_ -                              # Subtract it from the arg.
   {                        }...1     # Do this iteratively, until 1 is reached.
 +(                              )    # Return the number of values generated this way.
smls
fuente
1

Pyth, 17 16 bytes

L?tbhy-b*F+1tPb0

Pruébalo en línea! (El y.vfinal es para llamadas a funciones)


Original de 17 bytes:

L?tb+1y-b*F+1tPb0

Pruébalo en línea! (El y.vfinal es para llamadas a funciones)

(De hecho, respondí esa pregunta con este programa Pyth).

Monja permeable
fuente
En realidad no me molesté en revisar su programa, pero si está utilizando la definición recursiva en el OP, uprobablemente sea más corta que la recursividad real.
Maltysen
1

Pyke, 11 bytes (sin competencia)

D3Phf-oRr;o

Esto utiliza un nuevo comportamiento en el que si se produce una excepción después de un goto, restaura el estado anterior al goto (excepto las definiciones de variables) y continúa. En este caso es equivalente al siguiente código de Python:

# Implicit input and variable setup
inp = input()
o = 0
# End implicit
try:
    while 1:
        inp -= factors(inp)[0] # If factors is called on the value 1, it returns an empty
                               # list which when the first element tries to be accessed
                               # raises an exception
        o += 1 # Using `o` returns the current value of `o` and increments it
except:
    print o # This in effect gets the number of times the loop went

Todo esto es posible usando Pyke sin una construcción de bucle while - ¡yay goto!

Pruébalo aquí!

Azul
fuente
1

JavaScript (ES6), 70 54 bytes

f=(n,i=2)=>n<i?0:n%i?f(n,i+1):n>i?f(i)+f(n/i):1+f(n-1)

Implementación de la fórmula recursiva proporcionada, pero ahora actualizada para usar la recursividad para encontrar el divisor también.

Neil
fuente
1

Perl, 57 + 1 ( -pbandera) = 58 bytes

$n=$_;$n-=$n/(grep!($n%$_),2..$n/2,$n)[0],$\++while$n>1}{

Uso:

> echo 31 | perl -pe '$n=$_;$n-=$n/(grep!($n%$_),2..$n/2,$n)[0],$\++while$n>1}{'

Sin golf:

while (<>) {
# code above added by -p
    # $_ has input value
    # $\ has undef (or 0)
    my $n = $_;
    while ($n > 1) {
        my $d = 1;
        for (2 .. ($n / 2)) {
            if ($n % $_ == 0) {
                $d = $n / $_;
                last;
            }
        }
        $n -= $d;
        $\++;
    }
} {
# code below added by -p
    print;  # prints $_ (undef here) and $\
}
Denis Ibaev
fuente
1

Clojure, 98 96 bytes

#(loop[n % i -1](if n(recur(first(for[j(range(dec n)0 -1):when(=(mod n j)0)](- n j)))(inc i))i))

utiliza for :whenpara encontrar el divisor más grande, bucles hasta que no se encuentre dicho valor mayor que uno.

NikoNyrh
fuente