17
\$\begingroup\$

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/

\$\endgroup\$
3
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ @Ventero: Fails both test cases. I think you are forgetting to leave out squares starting with 0* \$\endgroup\$ – mellamokb Jun 2 '11 at 14:56
  • \$\begingroup\$ @mellamokb: Doesn't fail them here: $ ruby1.9 sndd.rb 14000 15000 => 14441. x[0]>?0 checks for squares starting with 0. \$\endgroup\$ – Ventero Jun 2 '11 at 14:58
  • \$\begingroup\$ @mellamokb: It passes the test cases here. \$\endgroup\$ – Nabb Jun 2 '11 at 15:02
  • \$\begingroup\$ @Ventero: Hmm.. something must be wrong with my ruby test environment. I'm not familiar with Ruby. I have 1.87 I think, and I copied / pasted the code above into sndd.rb, then run with ruby sndd.rb 14000 15000 from Windows, I get 14000. \$\endgroup\$ – mellamokb Jun 2 '11 at 15:04
  • \$\begingroup\$ @mellamokb: In Ruby 1.8, ?0 is a Fixnum, whereas in Ruby 1.8 it's a string, so the comparison I mentioned has a different meaning depending on the Ruby version (actually it should throw an exception in 1.8). That's why I explicitly mentioned version 1.9 in the title. \$\endgroup\$ – Ventero Jun 2 '11 at 15:09
8
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Interesting! You may have just proven that this sequence is actually infinite. \$\endgroup\$ – ESultanik Jun 1 '11 at 20:51
  • \$\begingroup\$ @ESultanik: Not really, because there is no requirement here that the overall number be a perfect square. \$\endgroup\$ – mellamokb Jun 1 '11 at 21:10
  • \$\begingroup\$ @ESutanik: I don't think that sequence is related, as they are requiring the whole number to be a square - in my sequence the only squares are small subsequences (<= 5 digits), unless by accident there is a larger one. \$\endgroup\$ – Keith Randall Jun 1 '11 at 21:12
  • \$\begingroup\$ You could also generate an infinite sequence where the link generates an extra square, i.e., something ending in 44 and beginning with 1 would make a 441 with every combination. A trivial example would be the sequence 144, 144144, 144144144, etc. \$\endgroup\$ – mellamokb Jun 1 '11 at 21:17
  • \$\begingroup\$ @mellamokb Wow, I totally missed that the number didn't have to be a perfect square. You're right. \$\endgroup\$ – ESultanik Jun 2 '11 at 3:06
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Try range(*map(int,sys.argv[1:])) \$\endgroup\$ – Keith Randall Jun 1 '11 at 19:32
  • 1
    \$\begingroup\$ Conjecture 2 is false if the 1.75-convergent sequence in my answer produces the best scores (a big if, admittedly), as subsequent elements of the sequence are marginally better, forever. \$\endgroup\$ – Keith Randall Jun 1 '11 at 22:44
  • \$\begingroup\$ Conjecture 2 is false by @Arnt's answer, because the value of SNDD can be made arbitrarily large. \$\endgroup\$ – mellamokb Jun 7 '11 at 18:10
2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ "'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." I'd like to see this proof developed. I can see the largest sequence ending in 25 where every number ending in 25 is a square is 275625. There's no digit 1-9 you can place on the beginning to find another square. Are you saying this can be made arbitrarily large, and if so, how and why? \$\endgroup\$ – mellamokb Jun 7 '11 at 17:58
  • \$\begingroup\$ Yes, the sequence can be made arbitrarily large. The proof is this: If a*a=b is your starting number, then (a+10^c)*(a+10^c) also ends in b if c is sufficiently large. In practice there may be smaller numbers which end in b if you take the square. For the example, 18275625 is a square(4275*4275). \$\endgroup\$ – Arnt Veenstra Jun 7 '11 at 18:05
  • \$\begingroup\$ Code to find squares: jsfiddle.net/zVSuZ/2 \$\endgroup\$ – mellamokb Jun 7 '11 at 18:05
  • \$\begingroup\$ @Arnt: Here is such a (trivial) sequence, 5^2 (1/2), 55^2 (2/4), 5055^2 (3/8), 50005055^2 (4/16), etc. where each addition is 5 * 10^n, where n is twice the previous entry. Each entry grows smaller in score, but the limit when applying the add two 00's rule grows marginally larger, so the limits are (1/2), (2/2), (3/2), (4/2), etc. \$\endgroup\$ – mellamokb Jun 7 '11 at 18:08
  • \$\begingroup\$ Yes, that's the idea which proofs any value for the SNDD can be reached. \$\endgroup\$ – Arnt Veenstra Jun 7 '11 at 18:18
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.