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.
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?
- Ruby: 142
- Windows PowerShell: 153
- Scala: 222
- Python: 245