La densité numérique des nombres carrés (SNDD) d'un nombre - inventé par moi-même - est le rapport entre le nombre de nombres carrés trouvés en chiffres consécutifs et la longueur du nombre. Par exemple, 169 est un nombre à 3 chiffres contenant 4 nombres carrés - 1, 9, 16, 169 - et a donc une densité de chiffres de nombre carré de 4/3, ou 1,33. Le nombre à 4 chiffres 1444 a 6 carrés - 1, 4, 4, 4, 144, 1444 - et donc un rapport de 6/4, ou 1,5. Notez dans l'exemple précédent que les carrés peuvent être répétés. En outre, 441 n'est pas autorisé, car il ne peut pas être trouvé consécutivement à l'intérieur du numéro 1444.

Votre tâche consiste à écrire un programme qui recherche dans une plage donnée A - B (inclus) le nombre ayant la densité de chiffres du nombre carré le plus élevé. Votre programme doit respecter les spécifications suivantes:

• Prenez l'entrée A, B dans la plage de 1 à 1 000 000 000 (1 milliard). Exemple:sndd 50 1000
• Renvoyez en conséquence le nombre avec le plus grand SNDD. En cas d'égalité, renvoyez le plus petit nombre.
• 0 ne compte pas comme un carré sous quelque forme que ce soit, 0, 00, 000, etc. Pas plus que les carrés commençant par 0, comme 049 ou 0049.
• Notez que le nombre entier ne doit pas nécessairement être un nombre carré.

Exemples:

sndd 14000 15000
Output: 14441

sndd 300 500
Output: 441

Bonus: Quel est le nombre avec le plus grand SNDD entre 1 et 1 000 000 000? Pouvez-vous prouver si c'est le plus grand possible, ou s'il pourrait y en avoir un plus grand dans une gamme plus élevée?

Scores actuels:

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

Maintenant qu'une réponse a été sélectionnée, voici mon implémentation de référence (non golfée) en JavaScript: http://jsfiddle.net/ywc25/2/

Ruby 1.9, 142 caractères

$><<($*[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): Sortie fixe en cas d'égalité.

Répondre au bonus: le meilleur score pour les nombres <1e9 est 5/3 = 1,666 ..., généré par 144411449 (et peut-être d'autres?).

Mais vous pouvez faire mieux avec de plus grands nombres. En général, si n a un score de x, vous pouvez concaténer deux copies de n et obtenir le même score x. Si vous êtes chanceux et que n a le même premier et dernier chiffre, vous pouvez supprimer l'un de ces chiffres dans la concaténation et améliorer légèrement votre score (un de moins du double du nombre de carrés et un de moins du double du nombre de chiffres) .

n = 11449441 a un score de 1,625 et a le même premier et dernier chiffre. En utilisant ce fait, nous obtenons la séquence de scores suivante:

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

ce qui donne une séquence infinie de nombres qui sont strictement (bien que de façon décroissante) meilleurs que les nombres précédents, et tous sauf les 2 premiers meilleurs que le meilleur score pour les nombres <1e9.

Cependant, cette séquence n'est peut-être pas la meilleure dans l'ensemble. Il converge vers un score fini (12/7 = 1,714) et il peut y avoir d'autres nombres avec de meilleurs scores que la limite.

Edit : une meilleure séquence, converge vers 1,75

1.600 14441
1.667 144414441
1.692 1444144414441
1.706 14441444144414441
1.714 144414441444144414441

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]

Merci à Ventero pour une réduction d'un octet j'étais trop stupide pour me retrouver.

Version de 154 octets expliquée:

$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

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: nettoyé le code d'analyse des arguments grâce à un conseil de Keith Randall .

Cela pourrait être beaucoup plus court si la plage était lue stdinpar opposition aux arguments de la ligne de commande.

Éditer:

En ce qui concerne le bonus, mes expériences suggèrent ce qui suit:

Conjecture 1 . Pour chaque n ∈ ℕ , le nombre dans ℕ _{≤ n} avec le plus grand SNDD doit contenir uniquement les chiffres 1, 4 et 9.

Conjecture 2. ∃ n ∈ ℕ ∀ i ∈ ℕ _{≥ n} : SNDD ( n ) ≥ SNDD ( i ).

Croquis de preuve . L'ensemble des carrés avec les chiffres 1, 4 et 9 est probablement fini . ∎

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

Considérant la question bonus: en dehors de la plage, le SNDD le plus élevé possible est infini.

Au moins, si j'ai bien lu la question, un carré comme 100 (10 * 10) compte.

Si vous considérez le nombre 275625, le score est de 5/6, car 25, 625, 5625, 75625 et 275625 sont tous carrés.

L'ajout de 2 zéro donne: 27562500, qui a un score de 10/8. La limite de cette séquence est 5/2 = 2,5

Dans le même ordre d'idées, vous pouvez trouver des carrés qui se terminent par un nombre quelconque de petits carrés souhaités. Je peux le prouver, mais vous avez probablement compris l'idée.

Certes, ce n'est pas une très bonne solution, mais cela prouve qu'il n'y a pas de limite supérieure au SNDD.

Clojure - 185 caractères

Pourrait probablement être optimisé davantage, mais voici:

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

Utilisé en fonction avec deux paramètres:

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

Jelly , 21 octets, défi de postdates de langue

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

Essayez-le en ligne!

Explication

Fonction d'assistance (calcule la densité numérique de son entrée):

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}

Programme principal:

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

Le programme est sans doute plus intéressant sans Ḣ- de cette façon, il renvoie tous les nombres à densité maximale plutôt qu'un seul - mais je l'ai ajouté pour se conformer à la spécification.