Wie klein kann es werden?

42

Suchen Sie ausgehend von einer positiven ganzen Zahl N die kleinste ganze Zahl N ', die berechnet werden kann, indem Sie N wiederholt durch eine der Ziffern (in Basis 10) dividieren . Jede ausgewählte Ziffer muss ein Teiler von N größer als 1 sein .

Beispiel 1

Die erwartete Ausgabe für N = 230 ist N '= 23 :

230/2 = 115, 115/5 = 23

Beispiel # 2

Die erwartete Ausgabe für N = 129528 ist N '= 257 :

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

Vorsicht vor nicht optimalen Wegen!

Wir könnten mit 129528/9 = 14392 beginnen , aber das würde nicht zum kleinstmöglichen Ergebnis führen. Das Beste, was wir tun können, wenn wir zuerst durch 9 dividieren, ist:

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

Regeln

  • Die Eingabe kann in jedem vernünftigen Format erfolgen (Ganzzahl, Zeichenfolge, Ziffernfeld, ...).
  • Das ist , also gewinnt die kürzeste Antwort in Bytes!

Testfälle

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
quelle
1
Ich frage mich, ob diese Serie (1, 1, ..., 10, 11, 1, 13, ..., 1, ...) einen OEIS-Eintrag hat
Draco18s
AFAICS (noch) nicht.
GNiklasch

Antworten:

11

Haskell , 67 61 Bytes

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

Probieren Sie es online!

Erläuterung:

  • read.pure<$>show nwandelt die eingegebene Ganzzahl nin eine Liste von Ziffern um.
  • Für jede Ziffer daus dieser Liste prüfen wir d>1und mod n d<1, ob also ddividiert wird n.
  • Wenn die Prüfungen erfolgreich sind, teilen wir ndurch dund rekursiv anwenden f: f$div n d.
  • Insgesamt ergibt sich eine Liste der minimalen Ganzzahlen aus allen Teilbäumen von n.
  • Da die Liste möglicherweise leer ist, hängen wir nsie an und geben die minimumder Liste zurück.
Laikoni
quelle
11

Gelee , 8 Bytes

÷DfḶ߀Ṃo

Probieren Sie es online!

Alternative Version, viel schneller, 9 Bytes

÷DfÆḌ߀Ṃo

Probieren Sie es online!

Wie es funktioniert

÷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
quelle
5

Rubin ,52 47 Bytes

Nimm an der nicht-exotischen Sprachgruppe teil! (Hinweis: Eine gute Idee, wenn Sie nicht Golf spielen, ist das Hinzufügen .uniqnach, .digitsda alle ähnlichen Branchen ähnliche Ergebnisse erzielen.)

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

Probieren Sie es online!

Erläuterung

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
}
Eineder
quelle
Können Sie x<2|n%x?n:f[n/x]zwei oder drei Bytes speichern (je nachdem, ob Sie ein |oder zwei benötigen )?
Neil
@Neil Leider wird Ruby value%zeroals Division durch Null behandelt, sodass ein Kurzschluss nicht funktioniert. Außerdem 0ist ein truthy Wert in Ruby (die einzigen Falsey Werte sind falsch und nil).
Unihedron
Also würde es mit zwei ||s funktionieren ?
Neil
Nein, weil 0 als wahr angesehen wird, wäre es mit >0, aber dann ist es die gleiche Zeichenanzahl.
Unihedron
Entschuldigung, ich sehe nicht, woher das 0kommt, wenn Sie es nicht benutzen |?
Neil
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))))

Probieren Sie es online!

Lesbare 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))))
Traut
quelle
3
Willkommen bei PPCG!
Laikoni
@Laikoni danke! Nicht die kleinste Einreichung, aber immer noch ziemlich lustig
Traut
@Laikoni mein Fehler behoben. Dankeschön!
Traut
@Arnauld danke fürs mitbekommen! Ich habe das Snippet repariert und den Link geändert.
Traut
@ Laikoni in der Tat! Ich habe es auf 205b gebracht.
Traut
4

Wolfram Language (Mathematica) , 44 Byte

-7 Bytes dank Mischa Lawrow.

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

Probieren Sie es online!

Alephalpha
quelle
1
Etwas golfiger ist diese 44-Byte-Lösung, die auf der Verwendung des Zeichens für basiert Intersection. Es gibt jedoch große Fälle, die nicht mehr verarbeitet werden können, da nicht mehr genügend Speicher zur Verfügung steht Range[#-1].
Mischa Lawrow
1
Wir können Most@Divisors@#statt verwenden Range[#-1], um das Speicherproblem zu vermeiden, aber das Ergebnis ist 49 Bytes .
Mischa Lawrow
4

JavaScript (Firefox 30-57), 49 Byte

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

ES6-kompatible 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>

Ursprünglich habe ich versucht, irrelevante Ziffern herauszufiltern, aber es stellt sich heraus, dass es mit 54 Bytes etwas länger ist:

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

Kotlin , 100 bis 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}

Verschönert

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

Prüfung

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

Bearbeitungen

jrtapsell
quelle
3

Gelee , 15 Bytes

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

Probieren Sie es online!

Ich muss zugeben, dass der ߀Teil von Eriks Antwort entlehnt ist . Der Rest wird separat entwickelt, zum Teil, weil ich nicht einmal verstehe, wie der Rest dieser Antwort überhaupt funktioniert: P.

Wie es funktioniert?

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

* Ich bin angenehm überrascht, ¡dass das auf Listen so funktioniert, denn seine normale Bedeutung ist es , dies n- mal anzuwenden .

Nachdem Dennis erklärt hat, warum ߀keine Bedingung erforderlich ist, haben wir diesen 12- Byte -Code oder seine 8-Byte-Version: P.

Mr. Xcoder
quelle
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)

Probieren Sie es online!

Eine Tonne von Bytes wird verwendet, um die Ziffern zu extrahieren und welche zu teilen x. Vielleicht ist ein anderer Ansatz notwendig.

Giuseppe
quelle
3

Excel Vba, 153 Bytes

Zum ersten Mal Code-Golf in der einzigen Sprache, die ich kenne :( Nicht gerade golffreundlich ...

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

Rufen Sie wie folgt an:

Sub callS()

result = S(655294464)

MsgBox result

End Sub

Ich habe keine Ahnung, wo ich das online testen soll.

Durielblut
quelle
1
Willkommen bei PPCG! Ich kenne Vba nicht wirklich, aber ich vermute, Sie können es durch And N > 0 ein N = Sin einer vorherigen Zeile ersetzen . (Wenn ich es testen könnte, wäre mein erster Instinkt, zu prüfen, ob Leerzeichen entfernt werden können.)
Ørjan Johansen
2

APL (Dyalog) , 33 Bytes

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

Probieren Sie es online!

Wie?

⍎¨⍕⍵ - greifen Ziffern von n

1~⍨- ohne 1s

o/⍨ - Filtern nach

0=⍵|⍨o- Teilbarkeit ndurch die Ziffer

⍬≡...:⍵ - Wenn leer, zurück n

⌊/ - Andernfalls geben Sie mindestens

∇¨ - Rekursion für jede Zahl in

⍵÷d- die Division ndurch jede der oben gefilterten Ziffern

Uriel
quelle
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}{

versuche es online

Nahuel Fouilleul
quelle