Project Euler – Problem 80 Solution

Problem

It is well known that if the square root of a nat­ur­al num­ber is not an inte­ger, then it is irra­tional. The dec­i­mal expan­sion of such square roots is infi­nite with­out any repeat­ing pat­tern at all.

The square root of two is 1.41421356237309504880…, and the dig­i­tal sum of the first one hun­dred dec­i­mal dig­its is 475.

For the first one hun­dred nat­ur­al num­bers, find the total of the dig­i­tal sums of the first one hun­dred dec­i­mal dig­its for all the irra­tional square roots.

Solution

(see full solu­tion here).

The premise of the prob­lem itself is fair­ly straight for­ward, the chal­lenge here is down to the way float­ing points are imple­ment­ed on com­put­ers which lacks the pre­ci­sion nec­es­sary to solve this prob­lem. So the bulk of the research went into find­ing a way to gen­er­ate an arbi­trary num­ber of dig­its of a square root.

As usu­al, Wikipedia has plen­ty to offer and the eas­i­est solu­tion imple­men­ta­tion wise is this solu­tion by Fraz­er Jarvis.

image

which trans­lates to:

image

The rest is real­ly straight for­ward, with the only tricky thing being the con­ver­sion from char to int since this returns the inter­nal inte­ger val­ue instead – e.g. int ‘0’ => 48 and int ‘1’ => 49 – hence the need for some hack­ery in the sum func­tion.

Here is the full solu­tion:

image

 

The solu­tion took 95ms to com­plete on my machine.