// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (42 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 206 Solution

Project Euler 206 Solution

Project Euler 206: Find the unique positive integer for a concealed square


Problem Description

Find the unique positive integer whose square has the form 1_2_3_4_5_6_7_8_9_0,
where each “_” is a single digit.

Analysis

The square of any number, n, will end in 00 if the last digit of n is zero.  So, our square root ends in a zero and the square has the form  1_2_3_4_5_6_7_8_900.

We can reduce our search to 1_2_3_4_5_6_7_8_9 and multiply the square root (when we find it) by 10.  Now, the only way to end a square with 9 is to square a number ending with 3 or 7. OK, so our square root ends with 3 or 7, an odd number, and we can skip even-numbered n from consideration.

Let’s begin our search with the maximum possible number, 19293949596979899 and take its square root. Starting with an odd number we count down by 2 until the square fits our pattern.

Project Euler 206 Solution

Runs < 0.001 seconds in Python 2.7.
download arrowUse this link to get the Project Euler 206 Solution Python 2.7 source.

Afterthoughts

  • The square root can only be a 9 digit integer that starts with 1 and ends with 0.
Project Euler 206 Solution last updated

Discussion

7 Responses to “Project Euler 206 Solution”

  1. I do like your approach to matching. I came here because I couldn’t see what was wrong with my solution. As it happens, I was offering the square rather than the square root. 🙁

    Posted by Bill | March 19, 2016, 10:26 AM
  2. The assumption made is incompletely justified for the problem statement

    The question asks for the number whose square is 1_2_3…_9_0

    There is no explicit guarantee that n ends in 0, only that n^2 ends in 0.

    A better rationale is that there is no value other than a multiple of 10, that when multiplied by itself which gives x0, thus n must be divisible by 10

    Posted by Philip Whitehouse | December 8, 2012, 6:01 PM
    • Phil, if someone planted an explosive device under your chair and told you that to disarm it all you had to do was type in any integer ending with a zero that, when squared, would not end with a zero would you be blown left or right from the concussion?

      Posted by Mike | February 3, 2014, 11:25 PM
    • If a proper square ends in 0, then its square root ends in a zero.
      Proof:
      0x0=[0]
      1×1=[1]
      2×2=[4]
      3×3=[9]
      4×4=1[6]
      5×5=2[5]
      6×6=3[6]
      7×7=4[9]
      8×8=6[4]
      9×9=8[1]
      Occurances of a square ending in a zero: 1; 0x0.
      So, the square root ends in a zero.

      Posted by Anonymous | July 28, 2017, 12:59 PM

Post a comment