# How small can it get?

Starting with a positive integer N, find the smallest integer N' which can be computed by repeatedly dividing N by one of its digits (in base-10). Each selected digit must be a divisor of N greater than 1.

## Example #1

The expected output for N = 230 is N' = 23:

## Example #2

The expected output for N = 129528 is N' = 257:

Beware of non-optimal paths!

We could start with 129528 / 9 = 14392, but that would not lead to the smallest possible result. The best we can do if we first divide by 9 is:

## Rules

• Input can be taken in any reasonable format (integer, string, array of digits, ...).
• This is , so the shortest answer in bytes wins!

## Test cases

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
• I wonder if this series (1, 1, ..., 10, 11, 1, 13, ..., 1, ...) has an OEIS entry Dec 28, 2017 at 1:48
• It doesn't (yet), AFAICS. Dec 29, 2017 at 15:18

# Haskell, 67 61 bytes

f n=minimum$n:[f$div n d|d<-read.pure<$>show n,d>1,mod n d<1] Try it online! ### Explanation: • read.pure<$>show n transforms the input integer n into a list of digits.
• For each digit d from this list, we check d>1 and mod n d<1, that is whether d divides n.

Try it online!

# Wolfram Language (Mathematica), 44 bytes

-7 bytes thanks to Misha Lavrov.

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

Try it online!

• Somewhat golfier is this 44-byte solution based on using the character for Intersection. But there are large cases it can no longer handle because it runs out of memory generating Range[#-1]. Dec 27, 2017 at 15:08
• We can use Most@Divisors@# instead of Range[#-1] to avoid the memory issue, but the result is 49 bytes. Dec 27, 2017 at 15:15

## JavaScript (Firefox 30-57), 49 bytes

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

ES6-compatible version, 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>

Originally I tried filtering out irrelevant digits but it turns out to be slightly longer at 54 bytes:

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

# APL (Dyalog), 33 bytes

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

Try it online!

How?

⍎¨⍕⍵ - grab digits of n

1~⍨ - excluding 1s

o/⍨ - filter by

0=⍵|⍨o - divisibility of n by the digit

⍬≡...:⍵ - if empty, return n

⌊/ - otherwise, return minimum of

∇¨ - recursion for each number in

⍵÷d - the division of n by each of the digits filtered above

# 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}

## Beautified

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

## Test

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")
}
}
}

# Jelly, 15 bytes

ÆDḊfD
:Çß€µÇ¡FṂ

Try it online!

I must admit that the ß€ part is borrowed from Erik's answer. The rest is developed separately, partly because I don't even understand how the rest of that answer works anyway :P.

### How it works?

Æ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.

*I am pleasantly surprised that ¡ works like that on lists, because its normal meaning is apply this n times.

After Dennis explained why ß€ doesn't need a conditional, we have this 12-byter, or his 8 byte version :P.

# 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)

Try it online!

A ton of bytes go into extracting the digits and which ones divide x; perhaps another approach is necessary.

## Excel Vba, 153 bytes

First ever code-golf in the only language I know :( Not exactly golf-friendly...

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

Call like this:

Sub callS()

result = S(655294464)

MsgBox result

End Sub

I haven't a clue where to test this online.

• Welcome to PPCG! I don't really know Vba but I suspect you can replace And N > 0 with a N = S on a previous line. (Also, if I had a way to test it my first instinct would be to check if any of the spaces can be removed.) Dec 29, 2017 at 15:37

$r=0,map{$\=$_,$r++if!$\|$_<$\;for$i(/[2-9]/g){$_%$i||$h{$_/$i}++}}$_,keys%h;$r&&redo}{ try it online # PHP, 120 bytes <?php function f($n){$r=array_map(function($x)use($n){return$x>1&&!($n%$x)?f($n/$x):$n;},str_split($n));return min(\$r);}

Try it online!

• Welcome to the site! :) Dec 27, 2017 at 18:31
• You can omit the opening PHP tags and save 6 bytes :-) Dec 28, 2017 at 15:48

# Pari/GP, 49 bytes

f(n)=vecmin([if(d<2||n%d,n,f(n/d))|d<-digits(n)])

Try it online!