data/problems/255.yml
---
:id: 255
:name: Rounded Square Roots
:url: https://projecteuler.net/problem=255
:content: "We define the _rounded-square-root_ of a positive integer <var>n</var>
as the square root of <var>n</var> rounded to the nearest integer.\n\nThe following
procedure (essentially Heron's method adapted to integer arithmetic) finds the rounded-square-root
of <var>n</var>:\n\nLet <var>d</var> be the number of digits of the number <var>n</var>.
\ \nIf <var>d</var> is odd, set <var>x</var><sub>0</sub> = 2×10<sup>(<var>d</var>-1)⁄2</sup>.
\ \nIf <var>d</var> is even, set <var>x</var><sub>0</sub> = 7×10<sup>(<var>d</var>-2)⁄2</sup>.
\ \nRepeat:\n\n\n\nuntil <var>x</var><sub><var>k</var>+1</sub>
= <var>x</var><sub><var>k</var></sub>.\n\nAs an example, let us find the rounded-square-root
of <var>n</var> = 4321. \n<var>n</var> has 4 digits, so <var>x</var><sub>0</sub>
= 7×10<sup>(4-2)⁄2</sup> = 70. \n 
\ \nSince <var>x</var><sub>2</sub> = <var>x</var><sub>1</sub>, we stop here. \nSo,
after just two iterations, we have found that the rounded-square-root of 4321 is
66 (the actual square root is 65.7343137…).\n\nThe number of iterations required
when using this method is surprisingly low. \nFor example, we can find the rounded-square-root
of a 5-digit integer (10,000 ≤ <var>n</var> ≤ 99,999) with an average of 3.2102888889
iterations (the average value was rounded to 10 decimal places).\n\nUsing the procedure
described above, what is the average number of iterations required to find the rounded-square-root
of a 14-digit number (10<sup>13</sup> ≤ <var>n</var> \\< 10<sup>14</sup>)? \nGive
your answer rounded to 10 decimal places.\n\nNote: The symbols ⌊<var>x</var>⌋ and
⌈<var>x</var>⌉ represent the <dfn title=\"the largest integer not greater than x\">floor
function</dfn> and <dfn title=\"the smallest integer not less than x\">ceiling function</dfn>
respectively.\n\n"