Dichte der quadratischen Ziffern

17

Die Square Number Digit Density (SNDD) einer von mir erfundenen Zahl ist das Verhältnis der Anzahl der in aufeinanderfolgenden Ziffern gefundenen Square Numbers zur Länge der Zahl. Beispielsweise ist 169 eine dreistellige Zahl mit 4 Quadratzahlen - 1, 9, 16, 169 - und hat somit eine Quadratzahlendichte von 4/3 oder 1,33. Die 4-stellige Zahl 1444 hat 6 Quadrate - 1, 4, 4, 4, 144, 1444 - und damit ein Verhältnis von 6/4 oder 1,5. Beachten Sie im vorherigen Beispiel, dass Quadrate wiederholt werden dürfen. Außerdem ist 441 nicht zulässig, da es nicht fortlaufend innerhalb der Nummer 1444 gefunden werden kann.

Ihre Aufgabe ist es, ein Programm zu schreiben, das einen bestimmten Bereich von A bis B (einschließlich) nach der Zahl mit der höchsten Dichte von Quadratziffern durchsucht. Ihr Programm sollte die folgenden Spezifikationen einhalten:

  • Nehmen Sie Input A, B im Bereich von 1 bis 1.000.000.000 (1 Milliarde). Beispiel:sndd 50 1000
  • Geben Sie als Ergebnis die Nummer mit der größten SNDD zurück. Im Falle eines Unentschieden geben Sie die kleinste Zahl zurück.
  • 0 zählt in keiner Form als Quadrat, 0, 00, 000 usw. Ebenso wenig wie Quadrate, die mit 0 beginnen, wie z. B. 049 oder 0049.
  • Beachten Sie, dass die gesamte Zahl kein Quadrat sein muss.

Beispiele:

sndd 14000 15000
Output: 14441

sndd 300 500
Output: 441

Bonus: Was ist die Nummer mit dem größten SNDD zwischen 1 und 1.000.000.000? Können Sie nachweisen, ob dies der größtmögliche Wert ist oder ob es einen größeren Wert in einem höheren Bereich gibt?

Aktuelle Ergebnisse:

  1. Rubin: 142
  2. Windows PowerShell: 153
  3. Scala: 222
  4. Python: 245

Nachdem eine Antwort ausgewählt wurde, ist hier meine (ungolfed) Referenzimplementierung in JavaScript: http://jsfiddle.net/ywc25/2/

mellamokb
quelle

Antworten:

3

Ruby 1.9, 142 Zeichen

$><<($*[0]..$*[1]).map{|a|n=0.0;(1..s=a.size).map{|i|n+=a.chars.each_cons(i).count{|x|x[0]>?0&&(r=x.join.to_i**0.5)==r.to_i}};[-n/s,a]}.min[1]
  • (139 -> 143): Ausgabe bei Gleichstand behoben.
Ventero
quelle
@Ventero: Beide Testfälle schlagen fehl. Ich glaube, Sie vergessen, die Quadrate
wegzulassen, die
@mellamokb: Hat sie hier nicht fehl: $ ruby1.9 sndd.rb 14000 15000 => 14441. x[0]>?0Überprüft,
ob
@mellamokb: Es besteht die Testfälle hier.
Nabb
@Ventero: Hmm .. irgendwas muss mit meiner Ruby-Testumgebung nicht stimmen. Ich kenne Ruby nicht. Ich habe 1.87, denke ich, und ich habe den obigen Code in die Datei sndd.rb kopiert / eingefügt. Dann ruby sndd.rb 14000 15000starte ich mit Windows und erhalte 14000.
mellamokb
@mellamokb: In Ruby 1.8 ?0handelt es sich um ein Fixnum, während es sich in Ruby 1.8 um einen String handelt. Der Vergleich, den ich erwähnte, hat je nach Ruby-Version eine andere Bedeutung (eigentlich sollte er in 1.8 eine Ausnahme auslösen). Aus diesem Grund habe ich im Titel ausdrücklich die Version 1.9 erwähnt.
Ventero
8

Beantwortung des Bonus: Die beste Punktzahl für Zahlen <1e9 ist 5/3 = 1.666 ..., generiert von 144411449 (und vielleicht anderen?).

Aber mit größeren Zahlen kann man es besser machen. Wenn n eine Punktzahl von x hat, können Sie im Allgemeinen zwei Kopien von n verketten und die gleiche Punktzahl x erhalten. Wenn Sie Glück haben und n dieselbe erste und letzte Ziffer hat, können Sie eine dieser Ziffern in der Verkettung ablegen und Ihre Punktzahl geringfügig verbessern (eine weniger als die doppelte Anzahl von Quadraten und eine weniger als die doppelte Anzahl von Ziffern). .

n = 11449441 hat eine Punktzahl von 1,625 und hat die gleiche erste und letzte Ziffer. Unter Verwendung dieser Tatsache erhalten wir die folgende Reihenfolge von Bewertungen:

1.625 for 11449441
1.666 for 114494411449441
1.682 for 1144944114494411449441
1.690 for 11449441144944114494411449441
1.694 for 114494411449441144944114494411449441

Dies ergibt eine unendliche Folge von Zahlen, die streng (wenn auch abnehmend) besser sind als vorherige Zahlen und alle bis auf die ersten 2 besser als die beste Punktzahl für Zahlen <1e9.

Diese Sequenz ist jedoch möglicherweise nicht die beste. Es konvergiert zu einer endlichen Punktzahl (12/7 = 1.714) und es kann andere Zahlen geben, deren Punktzahl besser ist als das Limit.

Edit : eine bessere Sequenz, konvergiert zu 1,75

1.600 14441
1.667 144414441
1.692 1444144414441
1.706 14441444144414441
1.714 144414441444144414441
Keith Randall
quelle
Interessant! Sie haben vielleicht gerade bewiesen, dass diese Sequenz tatsächlich unendlich ist.
ESultanik
@ ESultanik: Nicht wirklich, denn hier muss die Gesamtzahl kein perfektes Quadrat sein.
Mellamokb
@ ESutanik: Ich glaube nicht, dass die Sequenz verwandt ist, da die ganze Zahl ein Quadrat sein muss. In meiner Sequenz sind die einzigen Quadrate kleine Teilsequenzen (<= 5 Ziffern), es sei denn, es gibt versehentlich eine größere.
Keith Randall
Sie können auch eine unendliche Folge erzeugen, in der der Link ein zusätzliches Quadrat erzeugt, dh, dass etwas, das mit 44 endet und mit 1 beginnt, mit jeder Kombination eine 441 ergibt. Ein triviales Beispiel wäre die Sequenz 144, 144144, 144144144 usw.
mellamokb
@mellamokb Wow, ich habe total vermisst, dass die Zahl kein perfektes Quadrat sein musste. Du hast recht.
ESultanik
3

Windows PowerShell, 153 154 155 164 174

$a,$b=$args
@($a..$b|sort{-(0..($l=($s="$_").length)|%{($c=$_)..$l|%{-join$s[$c..$_]}}|?{$_[0]-48-and($x=[math]::sqrt($_))-eq[int]$x}).Count/$l},{$_})[0]

Dank Ventero für eine Ein-Byte-Reduzierung war ich zu dumm, um mich selbst zu finden.

154-Byte-Version erklärt:

$a,$b=$args   # get the two numbers. We expect only two arguments, so that
              # assignment will neither assign $null nor an array to $b.

@(   # @() here since we might iterate over a single number as well
    $a..$b |  # iterate over the range
        sort {   # sort
            (   # figure out all substrings of the number
                0..($l=($s="$_").length) | %{  # iterate to the length of the
                                               # string – this will run off
                                               # end, but that doesn't matter

                    ($c=$_)..$l | %{       # iterate from the current position
                                           # to the end

                        -join$s[$c..$_]    # grab a range of characters and
                                           # make them into a string again
                    }
                } | ?{                     # filter the list
                    $_[0]-48 -and          # must not begin with 0
                    ($x=[math]::sqrt($_))-eq[int]$x  # and the square root
                                                     # must be an integer
                }

            ).Count `  # we're only interested in the count of square numbers
            / $l       # divided by the length of the number
        },
        {-$_}  # tie-breaker
)[-1]  # select the last element which is the smallest number with the
       # largest SNDD
Joey
quelle
2

Python, 245 256

import sys
def t(n,l):return sum(map(lambda x:int(x**0.5+0.5)**2==x,[int(n[i:j+1])for i in range(l)for j in range(i,l)if n[i]!='0']))/float(l)
print max(map(lambda x:(x,t(str(x),len(str(x)))),range(*map(int,sys.argv[1:]))),key=lambda y:y[1])[0]
  • 256 → 245: Der Parsing-Code für Argumente wurde dank eines Tipps von Keith Randall aufgeräumt .

Dies könnte viel kürzer sein, wenn der Bereich von stdinim Gegensatz zu den Befehlszeilenargumenten gelesen wird .

Bearbeiten:

In Bezug auf den Bonus schlagen meine Experimente Folgendes vor:

Vermutung 1 . Für jedes n ∈ ℕ darf die Zahl inn mit der größten SNDD nur die Ziffern 1, 4 und 9 enthalten.

Vermutung 2.n ∈ ∈ i ∈ ≥ ≥ n : SNDD ( n ) ≥ SNDD ( i ).

Proof-Skizze . Die Menge der Quadrate mit den Ziffern 1, 4 und 9 ist wahrscheinlich endlich . ∎

ESultanik
quelle
Versuchen Sierange(*map(int,sys.argv[1:]))
Keith Randall
1
Vermutung 2 ist falsch, wenn die 1,75-konvergente Sequenz in meiner Antwort die besten Ergebnisse liefert (zugegebenermaßen ein großes wenn), da nachfolgende Elemente der Sequenz für immer geringfügig besser sind.
Keith Randall
Vermutung 2 ist nach der Antwort von @ Arnt falsch, weil der Wert von SNDD beliebig groß gemacht werden kann.
Mellamokb
2

Scala, 222

object O extends App{def q(i: Int)={val x=math.sqrt(i).toInt;x*x==i}
println((args(0).toInt to args(1).toInt).maxBy(n=>{val s=n+""
s.tails.flatMap(_.inits).filter(x=>x.size>0&&x(0)!='0'&&q(x.toInt)).size.toFloat/s.size}))}

(Scala 2.9 erforderlich.)

Rex Kerr
quelle
1

In Anbetracht der Bonusfrage: Außerhalb des Bereichs ist die höchstmögliche SNDD unendlich.

Zumindest, wenn ich die Frage richtig lese, zählt ein Quadrat wie 100 (10 * 10).

Wenn Sie die Zahl 275625 berücksichtigen, ist die Punktzahl 5/6, da 25, 625, 5625, 75625 und 275625 alle quadratisch sind.

Das Addieren von 2 Nullen ergibt: 27562500, was eine Punktzahl von 10/8 ergibt. Die Grenze dieser Sequenz ist 5/2 = 2,5

Entlang der gleichen Linie finden Sie Quadrate, die in einer beliebigen Anzahl kleinerer Quadrate enden. Ich kann das beweisen, aber Sie haben wahrscheinlich die Idee.

Zugegeben, dies ist keine sehr gute Lösung, aber es beweist, dass es keine Obergrenze für die SNDD gibt.

Arnt Veenstra
quelle
"In der gleichen Richtung finden Sie Quadrate, die in einer beliebigen Anzahl kleinerer Quadrate enden. Ich kann das beweisen, aber Sie haben wahrscheinlich die Idee." Ich würde gerne sehen, dass dieser Beweis entwickelt wird. Ich kann die größte Sequenz sehen, die mit 25 endet, wobei jede Zahl, die mit 25 endet, ein Quadrat ist, 275625. Es gibt keine Ziffer 1-9, die Sie am Anfang platzieren können, um ein anderes Quadrat zu finden. Wollen Sie damit sagen, dass dies beliebig groß sein kann, und wenn ja, wie und warum?
Mellamokb
Ja, die Sequenz kann beliebig groß gemacht werden. Der Beweis ist folgender: Wenn a * a = b Ihre Startnummer ist, endet (a + 10 ^ c) * (a + 10 ^ c) auch mit b, wenn c ausreichend groß ist. In der Praxis kann es kleinere Zahlen geben, die mit b enden, wenn Sie das Quadrat nehmen. Im Beispiel ist 18275625 ein Quadrat (4275 * 4275).
Arnt Veenstra
Code, um Quadrate zu finden: jsfiddle.net/zVSuZ/2
mellamokb
@Arnt: Hier ist eine solche (triviale) Sequenz, 5 ^ 2 (1/2), 55 ^ 2 (2/4), 5055 ^ 2 (3/8), 50005055 ^ 2 (4/16) usw. Dabei ist jede Addition 5 * 10 ^ n, wobei n das Doppelte des vorherigen Eintrags ist. Jeder Eintrag wird in der Punktzahl kleiner, aber das Limit bei Anwendung der Add-Two-00-Regel wird geringfügig größer, sodass die Limits (1/2), (2/2), (3/2), (4/2) usw .
mellamokb
Ja, das ist die Idee, die beweist, dass jeder Wert für die SNDD erreicht werden kann.
Arnt Veenstra
1

Clojure - 185 Zeichen

Könnte wahrscheinlich weiter optimiert werden, aber hier geht:

(fn[A,B]((first(sort(for[r[range]n(r A(inc B))s[(str n)]l[(count s)]][(/(count(filter #(=(int%)(max 1%))(for[b(r(inc l))a(r b)](Math/sqrt(Integer/parseInt(subs s a b))))))(- l))n])))1))

Wird als Funktion mit zwei Parametern verwendet:

(crazy-function-as-above 14000 15000)
=> 14441
mikera
quelle
1

Jelly , 21 Bytes, Sprachnachstellung

DµẆ1ị$ÐfḌƲS÷L
rµÇÐṀḢ

Probieren Sie es online!

Erläuterung

Hilfsfunktion (berechnet die Stellendichte ihrer Eingabe):

DµẆ1ị$ÐfḌƲS÷L
Dµ              Default argument: the input's decimal representation
  Ẇ             All substrings of {the decimal representation}
      Ðf        Keep only those where
   1ị$          the first digit is truthy (i.e. not 0)
        Ḍ       Convert from decimal back to an integer
         Ʋ     Check each of those integers to see if it's square
           S    Sum (i.e. add 1 for each square, 0 for each nonsquare)
            ÷L  Divide by the length of {the decimal representation}

Hauptprogramm:

rµÇÐṀḢ
rµ              Range from the first input to the second input
  ÇÐṀ           Find values that maximize the helper function
     Ḣ          Choose the first (i.e. smallest)

Das Programm ist wohl interessanter, wenn nicht nur eine, sondern alle Zahlen mit maximaler Dichte zurückgegeben werden, aber ich habe es hinzugefügt, um der Spezifikation zu entsprechen.


quelle