42
\$\begingroup\$

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:

230/2=115, 115/5=23

Example #2

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

129528/8=16191, 16191/9=1799, 1799/7=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:

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

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

16 Answers 16

11
\$\begingroup\$

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

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

Python 2, 59 bytes

f=lambda a:min([f(a/k)for k in map(int,`a`)if k>1>a%k]+[a])

Try it online!

\$\endgroup\$
5
\$\begingroup\$

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
}
\$\endgroup\$
  • \$\begingroup\$ 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)? \$\endgroup\$ – Neil Dec 27 '17 at 17:14
  • \$\begingroup\$ @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). \$\endgroup\$ – Unihedron Dec 28 '17 at 8:53
  • \$\begingroup\$ So would it work with two ||s? \$\endgroup\$ – Neil Dec 28 '17 at 9:57
  • \$\begingroup\$ Nope, because 0 is considered true, it would be with >0, but then it's the same char count. \$\endgroup\$ – Unihedron Dec 28 '17 at 10:07
  • \$\begingroup\$ Sorry, I'm not seeing where the 0 comes if you're not using |? \$\endgroup\$ – Neil Dec 28 '17 at 10:10
5
\$\begingroup\$

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))))
\$\endgroup\$
  • 3
    \$\begingroup\$ Welcome to PPCG! \$\endgroup\$ – Laikoni Dec 27 '17 at 15:43
  • \$\begingroup\$ @Laikoni thanks! Not the smallest submission but still pretty fun one \$\endgroup\$ – Traut Dec 27 '17 at 15:45
  • \$\begingroup\$ @Laikoni my mistake, fixed. thank you! \$\endgroup\$ – Traut Dec 27 '17 at 15:48
  • \$\begingroup\$ @Arnauld thanks for noticing! I fixed the snippet and changed the link. \$\endgroup\$ – Traut Dec 27 '17 at 15:54
  • \$\begingroup\$ @Laikoni indeed! I got it down to 205b. \$\endgroup\$ – Traut Dec 27 '17 at 16:06
4
\$\begingroup\$

Jelly, 21 bytes

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

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Wolfram Language (Mathematica), 44 bytes

-7 bytes thanks to Misha Lavrov.

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

Try it online!

\$\endgroup\$
  • 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 Dec 27 '17 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 Dec 27 '17 at 15:15
4
\$\begingroup\$

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)))
\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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.) \$\endgroup\$ – Ørjan Johansen Dec 29 '17 at 15:37
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

Pari/GP, 49 bytes

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

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.