How small can it get?

Question

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 code-golf, 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 — Draco18s no longer trusts SE
– Draco18s no longer trusts SE, Commented Dec 28, 2017 at 1:48

Community · Accepted Answer · 2020-06-17 09:04:33Z

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.
If the checks are successful, we divide n by d and recursively apply f: f$div n d.
Altogether, this yields a list of the minimal integers from all sub-trees of n.
As the list might be empty, we append n to it and return the minimum of the list.

Dennis · Accepted Answer · 2017-12-27 15:15:15Z

Jelly, 8 bytes

÷DfḶß€Ṃo

Try it online!

Alternate version, much faster, 9 bytes

÷DfÆḌß€Ṃo

Try it online!

How it works

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

Community · Accepted Answer · 2020-06-17 09:04:33Z

Ruby, 52 47 bytes

Competing for the non-exotic languages group! (Note: a good idea, if not golfing, is to add .uniq after .digits because all similar branches have similar results)

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

Try it online!

Explanation

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 }

Can you use x<2|n%x?n:f[n/x] to save two or three bytes (depending on whether you need one | or two)? — Neil
– Neil, Commented Dec 27, 2017 at 17:14
@Neil Unfortunately, ruby treats value%zero as division by zero, so short-circuiting won't work. Also, 0 is a truthy value in ruby (the only falsey values are false and nil). — Unihedron
– Unihedron, Commented Dec 28, 2017 at 8:53
Nope, because 0 is considered true, it would be with >0, but then it's the same char count. — Unihedron
– Unihedron, Commented Dec 28, 2017 at 10:07
Sorry, I'm not seeing where the 0 comes if you're not using |? — Neil
– Neil, Commented Dec 28, 2017 at 10:10

Traut · Accepted Answer · 2017-12-27 20:59:53Z

5

Common Lisp, 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))))

Try it online!

Readable version:

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

edited Dec 27, 2017 at 20:59

answered Dec 27, 2017 at 15:40

Traut

1513 bronze badges

3

\$\begingroup\$ Welcome to PPCG! \$\endgroup\$

Laikoni
– Laikoni

2017-12-27 15:43:48 +00:00
Commented Dec 27, 2017 at 15:43
\$\begingroup\$ @Laikoni thanks! Not the smallest submission but still pretty fun one \$\endgroup\$

Traut
– Traut

2017-12-27 15:45:37 +00:00
Commented Dec 27, 2017 at 15:45
\$\begingroup\$ @Laikoni my mistake, fixed. thank you! \$\endgroup\$

Traut
– Traut

2017-12-27 15:48:57 +00:00
Commented Dec 27, 2017 at 15:48
\$\begingroup\$ @Arnauld thanks for noticing! I fixed the snippet and changed the link. \$\endgroup\$

Traut
– Traut

2017-12-27 15:54:31 +00:00
Commented Dec 27, 2017 at 15:54
\$\begingroup\$ @Laikoni indeed! I got it down to 205b. \$\endgroup\$

Traut
– Traut

2017-12-27 16:06:17 +00:00
Commented Dec 27, 2017 at 16:06

| Show 2 more comments

Erik the Outgolfer · Accepted Answer · 2017-12-27 12:38:04Z

4

Jelly, 21 bytes

Dðḍ>Ị{ DxÇ⁸:ß€µÇẸ$¡FṂ

Try it online!

answered Dec 27, 2017 at 12:38

Erik the Outgolfer

40.8k5 gold badges46 silver badges125 bronze badges

Add a comment |

alephalpha · Accepted Answer · 2017-12-27 15:35:41Z

4

Wolfram Language (Mathematica), 44 bytes

-7 bytes thanks to Misha Lavrov.

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

Try it online!

edited Dec 27, 2017 at 15:35

answered Dec 27, 2017 at 13:01

alephalpha

51.9k7 gold badges75 silver badges197 bronze badges

1

\$\begingroup\$ 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]. \$\endgroup\$

Misha Lavrov
– Misha Lavrov

2017-12-27 15:08:05 +00:00
Commented Dec 27, 2017 at 15:08
1

\$\begingroup\$ We can use Most@Divisors@# instead of Range[#-1] to avoid the memory issue, but the result is 49 bytes. \$\endgroup\$

Misha Lavrov
– Misha Lavrov

2017-12-27 15:15:23 +00:00
Commented Dec 27, 2017 at 15:15

Add a comment |

Neil · Accepted Answer · 2017-12-27 17:11:50Z

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

Uriel · Accepted Answer · 2017-12-27 13:47:51Z

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

jrtapsell · Accepted Answer · 2017-12-27 14:02:56Z

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

Edits

-1 Mr. Xcoder

Community · Accepted Answer · 2020-06-17 09:04:33Z

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.

Giuseppe · Accepted Answer · 2017-12-28 15:06:23Z

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.

Durielblood · Accepted Answer · 2017-12-29 15:13:04Z

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.) — Ørjan Johansen
– Ørjan Johansen, Commented Dec 29, 2017 at 15:37

Nahuel Fouilleul · Accepted Answer · 2017-12-27 15:37:00Z

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

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

try it online

Zerquix18 · Accepted Answer · 2017-12-27 18:28:30Z

2

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!

answered Dec 27, 2017 at 18:28

Zerquix18

1315 bronze badges

3

\$\begingroup\$ Welcome to the site! :) \$\endgroup\$

DJMcMayhem
– DJMcMayhem

2017-12-27 18:31:53 +00:00
Commented Dec 27, 2017 at 18:31
2

\$\begingroup\$ You can omit the opening PHP tags and save 6 bytes :-) \$\endgroup\$

Daniel W.
– Daniel W.

2017-12-28 15:48:15 +00:00
Commented Dec 28, 2017 at 15:48

Add a comment |

alephalpha · Accepted Answer · 2017-12-27 23:57:11Z

2

Pari/GP, 49 bytes

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

Try it online!

answered Dec 27, 2017 at 23:57

alephalpha

51.9k7 gold badges75 silver badges197 bronze badges

Add a comment |

Stack Exchange Network

How small can it get?

Example #1

Example #2

Rules

Test cases

15 Answers 15

Haskell, 67 61 bytes

Explanation:

Jelly, 8 bytes

Alternate version, much faster, 9 bytes

How it works

Ruby, 52 47 bytes

Explanation

Common Lisp, 136 bytes

Jelly, 21 bytes

Wolfram Language (Mathematica), 44 bytes

JavaScript (Firefox 30-57), 49 bytes

APL (Dyalog), 33 bytes

Kotlin, 100 99 bytes

Beautified

Test

Edits

Jelly, 15 bytes

How it works?

R, 101 98 bytes

Excel Vba, 153 bytes

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

PHP, 120 bytes

Pari/GP, 49 bytes

Hot Network Questions

How small can it get?

Example #1

Example #2

Rules

Test cases

15 Answers 15

Haskell, 67 61 bytes

Explanation:

Jelly, 8 bytes

Alternate version, much faster, 9 bytes

How it works

Ruby, 52 47 bytes

Explanation

Common Lisp, 136 bytes

Jelly, 21 bytes

Wolfram Language (Mathematica), 44 bytes

JavaScript (Firefox 30-57), 49 bytes

APL (Dyalog), 33 bytes

Kotlin, 100 99 bytes

Beautified

Test

Edits

Jelly, 15 bytes

How it works?

R, 101 98 bytes

Excel Vba, 153 bytes

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

PHP, 120 bytes

Pari/GP, 49 bytes

Related

Hot Network Questions

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