¿Qué tan pequeño puede ser?

42

Comenzando con un número entero positivo N , encuentre el número entero más pequeño N ' que se puede calcular dividiendo repetidamente N por uno de sus dígitos (en base-10). Cada dígito seleccionado debe ser un divisor de N mayor que 1 .

Ejemplo 1

La salida esperada para N = 230 es N '= 23 :

230/2 = 115, 115/5 = 23

Ejemplo # 2

La salida esperada para N = 129528 es N '= 257 :

129528/8 = 16191, 16191/9 = 1799, 1799/7 = 257

¡Cuidado con los caminos no óptimos!

Podríamos comenzar con 129528/9 = 14392 , pero eso no llevaría al resultado más pequeño posible. Lo mejor que podemos hacer si primero dividimos entre 9 es:

129528/9 = 14392, 14392/2 = 7196, 7196/7 = 1028, 1028/2 = 514 -> ¡mal!

Reglas

  • La entrada se puede tomar en cualquier formato razonable (entero, cadena, matriz de dígitos, ...).
  • Este es el , por lo que gana la respuesta más corta en bytes.

Casos de prueba

1         --> 1
7         --> 1
10        --> 10
24        --> 1
230       --> 23
234       --> 78
10800     --> 1
10801     --> 10801
50976     --> 118
129500    --> 37
129528    --> 257
8377128   --> 38783
655294464 --> 1111
Arnauld
fuente
1
Me pregunto si esta serie (1, 1, ..., 10, 11, 1, 13, ..., 1, ...) tiene una entrada OEIS
Draco18s
No lo hace (todavía), AFAICS.
GNiklasch

Respuestas:

11

Haskell , 67 61 bytes

f n=minimum$n:[f$div n d|d<-read.pure<$>show n,d>1,mod n d<1]

Pruébalo en línea!

Explicación:

  • read.pure<$>show ntransforma el entero de entrada nen una lista de dígitos.
  • Para cada dígito dde esta lista, verificamos d>1y mod n d<1, es decir, si se ddivide n.
  • Si las comprobaciones tienen éxito, dividimos npor dy aplicar de forma recursiva f: f$div n d.
  • En total, esto produce una lista de los enteros mínimos de todos los subárboles de n.
  • Como la lista puede estar vacía, la agregamos ny le devolvemos minimumla lista.
Laikoni
fuente
11

Jalea , 8 bytes

÷DfḶ߀Ṃo

Pruébalo en línea!

Versión alternativa, mucho más rápida, 9 bytes.

÷DfÆḌ߀Ṃo

Pruébalo en línea!

Cómo funciona

÷DfḶ߀Ṃo  Main link. Argument: n

 D        Decimal; yield the digits of n.
÷         Divide n by each of its digits.
   Ḷ      Unlength; yield [0, ..., n-1].
  f       Filter; keep quotients that belong to the range.
    ߀    Recursively map this link over the resulting list.
      Ṃ   Take the minimum. This yields 0 if the list is empty.
       o  Logical OR; replace 0 with n.
Dennis
fuente
5

rubí ,52 47 bytes

¡Compitiendo por el grupo de idiomas no exóticos! (Nota: una buena idea, si no es golf, es agregar .uniqdespués .digitsporque todas las ramas similares tienen resultados similares)

f=->n{n.digits.map{|x|x>1&&n%x<1?f[n/x]:n}.min}

Pruébalo en línea!

Explicación

f=->n{      # Function "f" n ->
   n.digits # n's digits (in reverse order (<- doesn't matter))
            # fun fact: all numbers always have at least one digit
    .map{|x|# Map function for every digit "x" ->
       x>1&&    # x is 2-9 and
       n%x<1    # n mod x == 0, or, "n is divisible by x"
       ? f[n/x] # then recursively find smallest of f[n/x]
       : n      # otherwise: n (no shortest path in tree)
     }.min  # Smallest option out of the above
            # if we reach a dead end, we should get n in this step
}
Unihedron
fuente
¿Se puede usar x<2|n%x?n:f[n/x]para guardar dos o tres bytes (dependiendo de si necesita uno |o dos)?
Neil
@Neil Desafortunadamente, ruby ​​trata la value%zerodivisión por cero, por lo que el cortocircuito no funcionará. Además, 0es un valor verdadero en ruby ​​(los únicos valores falsey son falso y nulo).
Unihedron
Entonces, ¿funcionaría con dos ||s?
Neil
No, porque 0 se considera verdadero, sería con >0, pero es el mismo recuento de caracteres.
Unihedron
Lo siento, no veo de dónde 0viene si no lo estás usando |.
Neil
5

Lisp común , 136 bytes

(defun f(n)(apply 'min(or(loop for z in(map'list #'digit-char-p(write-to-string n))if(and(> z 1)(<(mod n z)1))collect(f(/ n z)))`(,n))))

Pruébalo en línea!

Versión legible:

(defun f (n)
  (apply 'min
         (or (loop for z in (map 'list
                                 #'digit-char-p
                                 (write-to-string n))
                   if (and (> z 1)
                           (< (mod n z) 1))
                   collect (f (/ n z)))
             `(,n))))
Traut
fuente
3
Bienvenido a PPCG!
Laikoni
@Laikoni gracias! No es la presentación más pequeña pero sigue siendo bastante divertida
Traut
@Laikoni mi error, solucionado. ¡gracias!
Traut
@Arnauld gracias por notarlo! Arreglé el fragmento y cambié el enlace.
Traut
@Laikoni de hecho! Lo bajé a 205b.
Traut
4

Wolfram Language (Mathematica) , 44 bytes

-7 bytes gracias a Misha Lavrov.

Min[#0/@(#/IntegerDigits@#⋂Range[#-1]),#]&

Pruébalo en línea!

alephalpha
fuente
1
Algo más elegante es esta solución de 44 bytes basada en el uso del carácter Intersection. Pero hay casos grandes que ya no puede manejar porque se queda sin generación de memoria Range[#-1].
Misha Lavrov
1
Podemos usar en Most@Divisors@#lugar de Range[#-1]evitar el problema de memoria, pero el resultado es 49 bytes .
Misha Lavrov
4

JavaScript (Firefox 30-57), 49 bytes

f=n=>Math.min(...(for(c of''+n)c<2|n%c?n:f(n/c)))

Versión compatible con ES6, 52 bytes:

f=n=>Math.min(...[...''+n].map(c=>c<2|n%c?n:f(n/c)))
<input type=number oninput=o.textContent=f(this.value)><pre id=o>

Originalmente intenté filtrar dígitos irrelevantes, pero resulta ser un poco más largo a 54 bytes:

f=n=>Math.min(n,...(for(c of''+n)if(c>1&n%c<1)f(n/c)))
Neil
fuente
3

Kotlin , 100 99 bytes

fun f(i:Int):Int{return i.toString().map{it.toInt()-48}.filter{it>1&&i%it<1}.map{f(i/it)}.min()?:i}

Embellecido

fun f(i:Int):Int{
    return i.toString()
        .map { it.toInt()-48 }
        .filter { it >1 && i % it < 1}
        .map { f(i/it) }
        .min() ?: i
}

Prueba

fun f(i:Int):Int{return i.toString().map{it.toInt()-48}.filter{it>1&&i%it<1}.map{f(i/it)}.min()?:i}

val tests = listOf(
        1 to 1,
        7 to 1,
        10 to 10,
        24 to 1,
        230 to 23,
        234 to 78,
        10800 to 1,
        10801 to 10801,
        50976 to 118,
        129500 to 37,
        129528 to 257,
        8377128 to 38783,
        655294464 to 1111)

fun main(args: Array<String>) {
    for ( test in tests) {
        val computed = f(test.first)
        val expected = test.second
        if (computed != expected) {
            throw AssertionError("$computed != $expected")
        }
    }
}

Ediciones

jrtapsell
fuente
3

Jalea , 15 bytes

ÆDḊfD
:Ç߀µÇ¡FṂ

Pruébalo en línea!

Debo admitir que la ߀parte está tomada de la respuesta de Erik . El resto se desarrolla por separado, en parte porque ni siquiera entiendo cómo funciona el resto de esa respuesta de todos modos: P.

¿Cómo funciona?

ÆDḊfD ~ Helper link (monadic). I'll call the argument N.

ÆD    ~ Take the divisors.
  Ḋ   ~ Dequeue (drop the first element). This serves the purpose of removing 1.
   fD ~ Take the intersection with the decimal digits.

:Ç߀µÇ¡FṂ ~ Main link.

 Ç        ~ Apply the helper link to the first input.
:         ~ And perform element-wise integer division.
     Ç¡   ~ If the helper link applied again is non-empty*, then...
  ߀µ     ~ Apply this link to each (recurse).
       FṂ ~ Flatten and get the maximum.

* Estoy gratamente sorprendido de que ¡funcione así en las listas, porque su significado normal es aplicar esto n veces .

Después explicó Dennis por eso ߀no necesita un condicional, tenemos este 12-byter , o su versión de 8 bytes: P.

Sr. Xcoder
fuente
3

R , 101 98 bytes

f=function(x,e=(d=x%/%10^(0:nchar(x))%%10)[d>1])"if"(sum(y<-which(!x%%e)),min(sapply(x/e[y],f)),x)

Pruébalo en línea!

Una tonelada de bytes se destina a extraer los dígitos y cuáles se dividen x; Quizás otro enfoque sea necesario.

Giuseppe
fuente
3

Excel Vba, 153 bytes

Primer código de golf en el único idioma que conozco :( No es exactamente amigable para el golf ...

Function S(X)
S = X
For I = 1 To Len(CStr(X))
A = Mid(X, I, 1)
If A > 1 Then If X Mod A = 0 Then N = S(X / A)
If N < S And N > 0 Then S = N
Next I
End Function

Llama así:

Sub callS()

result = S(655294464)

MsgBox result

End Sub

No tengo idea de dónde probar esto en línea.

Durielblood
fuente
1
Bienvenido a PPCG! Realmente no conozco Vba, pero sospecho que puedes reemplazarlo And N > 0 con un N = Sen una línea anterior. (Además, si tuviera una forma de probarlo, mi primer instinto sería verificar si se pueden eliminar algunos de los espacios).
Ørjan Johansen
2

APL (Dyalog) , 33 bytes

{⍬≡do/⍨0=⍵|⍨o1~⍨⍎¨⍕⍵:⍵⋄⌊/∇¨⍵÷d}

Pruébalo en línea!

¿Cómo?

⍎¨⍕⍵ - agarrar dígitos de n

1~⍨- excluyendo 1s

o/⍨ - filtrado por

0=⍵|⍨o- divisibilidad de npor el dígito

⍬≡...:⍵ - si está vacío, regrese n

⌊/ - de lo contrario, devolver un mínimo de

∇¨ - recursividad para cada número en

⍵÷d- la división de npor cada uno de los dígitos filtrados arriba

Uriel
fuente
2

Perl 5, 87 + 1 ( -p) = 88 bytes

$r=0,map{$\=$_,$r++if!$\|$_<$\;for$i(/[2-9]/g){$_%$i||$h{$_/$i}++}}$_,keys%h;$r&&redo}{

pruébalo en línea

Nahuel Fouilleul
fuente