Square Number Digit Density

Question

The square number digit density (SNDD) of a number - invented by myself - is the ratio of the count of square numbers found in consecutive digits to the length of the number. For instance, 169 is a 3-digit number containing 4 square numbers - 1, 9, 16, 169 - and thus has a square number digit density of 4/3, or 1.33. The 4-digit number 1444 has 6 squares - 1, 4, 4, 4, 144, 1444 - and thus a ratio of 6/4, or 1.5. Notice in the previous example that squares are allowed to be repeated. Also, 441 is not allowed, because it cannot be found consecutively inside the number 1444.

Your task is to write a program that searches a given range A - B (inclusive) for the number with the highest square number digit density. Your program should abide by the following specifications:

• Take input A, B in the range 1 to 1,000,000,000 (1 billion). Example: sndd 50 1000
• Return as a result the number with the largest SNDD. In the case of a tie, return the smallest number.
• 0 does not count as a square in any form, 0, 00, 000, etc. Neither do squares starting with 0, such as 049 or 0049.
• Note that the entire number does not have to be a square number.

Examples:

sndd 14000 15000
Output: 14441

sndd 300 500
Output: 441

Bonus: What is the number with the largest SNDD between 1 and 1,000,000,000? Can you prove whether this is the largest possible, or there might be a larger one in a higher range?

Current Scores:

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

Now that an answer has been selected, here is my (ungolfed) reference implementation in JavaScript: http://jsfiddle.net/ywc25/2/

Answer 1

Answering the bonus: the best score for numbers <1e9 is 5/3=1.666..., generated by 144411449 (and maybe others?).

But you can do better with larger numbers. Generally if n has a score of x, then you can concatenate two copies of n and get the same score x. If you're lucky and n has the same first and last digit, then you can drop one of those digits in the concatenation and improve your score slightly (one less than double the number of squares and one less than double the number of digits).

n=11449441 has a score of 1.625 and has the same first & last digit. Using that fact, we get the following sequence of scores:

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

which gives an infinite sequence of numbers which are strictly (although decreasingly) better than previous numbers, and all but the first 2 better than the best score for numbers < 1e9.

This sequence may not be the best overall, though. It converges to a finite score (12/7=1.714) and there may be other numbers with better scores than the limit.

Edit: a better sequence, converges to 1.75

1.600 14441
1.667 144414441
1.692 1444144414441
1.706 14441444144414441
1.714 144414441444144414441

Answer 2

Ruby 1.9, 142 characters

$><<($*[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): Fixed output in case of a tie.

Answer 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]

Thanks to Ventero for a one-byte reduction I was too stupid to find myself.

154-byte version explained:

$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

Answer 4

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: Cleaned up the argument parsing code thanks to a tip from Keith Randall.

This could be a lot shorter if the range were read from stdin as opposed to the command line arguments.

Edit:

With respect to the bonus, my experiments suggest the following:

Conjecture 1. For every n ∈ ℕ, the number in ℕ_≤n with the largest SNDD must contain solely the digits 1, 4, and 9.

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

Proof sketch. The set of squares with digits 1, 4, and 9 are likely finite. ∎

Answer 5

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

Answer 6

Jelly, 21 bytes, language postdates challenge

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

Try it online!

Explanation

Helper function (calculates digit density of its input):

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}

Main program:

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

The program's arguably more interesting without the Ḣ – that way, it returns all maximal-density numbers rather than just one – but I added it to comply with the specification.

Answer 7

Considering the bonus question: Outside of the range the highest possible SNDD is infinite.

At least, if I read the question correctly, a square like 100 (10*10) does count.

If you consider the number 275625, the score is 5/6, since 25, 625, 5625, 75625 and 275625 are all square.

Adding 2 zero's gives: 27562500, which has a score of 10/8. The limit of this sequence is 5/2=2.5

Along the same lines, you can find squares which end in any number of smaller squares desired. I can proof this, but you probably get the idea.

Admittedly, this is not a very nice solution, but it proofs there's no upper limit to the SNDD.

Answer 8

Clojure - 185 chars

Probably could be optimised further but here goes:

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

Used as a function with two parameters:

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

Answer 9

Japt -h, 18 bytes

Well, this is pretty hideous!

õV ñÈì ã fÎxÈì ¬v1

Try it

õV ñÈì ã fÎxÈì ¬v1     :Implicit input of integers U & V
õV                     :Range [V,U]
   ñ                   :Sort by
    È                  :Passing each through the following function
     ì                 :  Convert to digit array
       ã               :  Sub-arrays
         f             :  Filter by
          Î            :    First element (0 is falsey)
           x           :  Reduce by addition after
            È          :  Passing each through the following function
             ì         :    Convert from digit array
               ¬       :    Square root
                v1     :    Divisible by 1?
                       :Implicit output of last element