Themabewertung:
  • 0 Bewertung(en) - 0 im Durchschnitt
  • 1
  • 2
  • 3
  • 4
  • 5
Zahlentheorie-Problem gesucht
#1
Ich habe mal (vermutlich in den Mathematik-Rubriken im Spektrum der Wissenschaft) ein Problem gesehen, das ich nicht im Internet finde.
Es wurde mal mit "n-value Problem" , "Wert/Preis einer Zahl" oder ähnlich bezeichnet.

Es ging darum, eine natürliche Zahl auf 1 zu bringen, indem man

a) die Zahl um 1 vergrößert oder verkleinert (das kostet einen Minuspunkt)
b) einen (ganzzahligen) Teiler abspaltet und mit der größeren (genauer: nicht kleineren) Zahl weitermacht (das kostet keinen Minuspunkt)

Beispiel: Ausgangszahl 10
10 -> 9 (-1, 1 Minuspunkt) -> 8 (-1, 1 Minuspunkt) -> 4 (2 abgespalten) -> 2 (2 abgespalten) -> 1 (-1, 1 Minuspunkt) => dieser Weg kostet 3 Minuspunkte
10 -> 5 (2 abgespalten) -> 4 (-1, 1 Minuspunkt) -> 2 (2 abgespalten) -> 1 (-1, 1 Minuspunkt) => dieser Weg kostet 2 Minuspunkte

Die Anzahl Minuspunkte, die man mindestens braucht, ist als "Wert" der Zahl definiert, und das Problem ist dann, gibt es eine obere Schranke für den Wert beliebig großer Zahlen, bzw. welches überhaupt die kleinsten Zahlen sind, die einen Wert von 1,2,3,... haben.

--Jessica
Zitieren
#2
Wenn das Problem einigermaßen weit verbreitet ist und gut untersucht ist, und einem nur der Name fehlt, hilft es vielleicht, ein paar kleine Werte echt auszurechnen und die so entstehende Folge bei oeis.org zu suchen.
Zitieren
#3
Wenn ich mich nicht verrechnet habe, ist die Folge dort nicht zu finden.
Zitieren
#4
Ich habe die Folge jetzt doch in OEIS gefunden (dort ist die Zielzahl 2 statt 1, die Zahlen in meiner Beschreibung sind alle um 1 zu groß, da ich den Schritt von 2 zu 1 noch mitgezählt habe)


A047988

Start with n and reach 2 by repeatedly either dividing by d where d <= the square root or by adding or subtracting 1. The division steps are free, but adding or subtracting 1 costs 1 point. a(n) is the smallest cost to reach 2.

Und den Spektrum-Artikel gleich mit:
Thomas Kantke, Das Spiel Minimum und die Zerlegung natürlicher Zahlen, Mathematische Unterhaltungen, Spectrum der Wissenschaft, April 1993, pp. 11-13.
Zitieren


Möglicherweise verwandte Themen...
Thema Verfasser Antworten Ansichten Letzter Beitrag
  altes Buch gesucht ildiko 8 6.903 15.08.2021, 08:57
Letzter Beitrag: ildiko
  Style-Problem beim Wiki rob 7 3.017 12.04.2021, 09:48
Letzter Beitrag: Statistica
  Jigsaw-Puzzler gesucht CHalb 0 1.420 29.09.2020, 18:53
Letzter Beitrag: CHalb
  rätselaffine/r Programmierer/in gesucht Stefan 0 1.465 01.04.2020, 13:42
Letzter Beitrag: Stefan
  Testlöser gesucht SilBer 9 9.536 22.02.2017, 18:58
Letzter Beitrag: chrisbee

Gehe zu:


Benutzer, die gerade dieses Thema anschauen: 1 Gast/Gäste