After so much procrastination (an art I seem to master quite well…), at last I started messing with Python. The final kick-start came from a short post about “curious numbers” on gorgeous John D. Cook’s blog. In short, a number is curious when it has the last digits of its square equal to the number itself, e.g. 252 = 625. That’s all I needed to know.
Finding all curious numbers up to a given number of digits seemed a good task to start writing a few lines of Python. Bash shell was an option, too, although I should have limited the search to numbers up ~3.037×109 (the square root of the largest integer the shell can handle, 263-1 ≅ 9.22×1018).
One last note: you’re about to read a quite long rambling about coding, numbers and learning Python. I chose to describe at length the process that brought me from the basics to functional code, gradually improved and extended, rather than providing the final result of my efforts. It is a way to describe the method I’m trying to adopt to learn Python and, hopefully, a useful example of approach.
Keyboard & Screen
First attempt is rough and inefficient: brute force processing all numbers
n between 102 and 109 (exponent defined by variable
order) and check if they meet the requirements (last
order digits are the same as
n). It just worked, no matter how well, as I was mainly getting used to the peculiar Python syntax at the time: indentation to define blocks of code and no closing words for clauses (no
if ... fi or
do ... done like *nix shell, for example).
First loop of improvement (no optimizations, yet!): interactively set the upper
limit for search, accepting only integers ≥ 3, and measure execution time. Typical Python stuff involved here:
import what you need,
try something /
except when input is garbage, and boast the 3.x style of
import time while True: try: limit = int(input('Enter limit: ')) if limit >= 3: break except ValueError: pass texec = time.clock() for order in range(2, limit+1): for n in range(int(10**(order-1)), 10**order): n_sqr = n**2 tail = (n**2 % 10**order) if n == tail: print(order,n_sqr,tail) texec = time.clock() - texec print('Execution time: ' + str(texec) + ' seconds')
2 625 25
2 5776 76
3 141376 376
3 390625 625
4 87909376 9376
5 8212890625 90625
6 11963109376 109376
6 793212890625 890625
7 8355712890625 2890625
7 50543227109376 7109376
Execution time: 14.183878 seconds
Data show how bad this implementation is (spoiler: very bad!). When processing all numbers with 2 up to
limit digits, things escalate quickly: at
order = 2 the search is in interval [10, 99] (90 numbers), at
order = 3 in [100, 999] (900 additional numbers to search, 990 in total) and so on. The table below summarizes the magnificent inefficiency of this iteration.
|timeN / timeN-1|
The duration of each whole run increases by a factor of ~10 when the search limit is increased by 1, of course because there are ~10 times more numbers to process (hint: geometric progression). You can figure out what it means to reach
order = 9 or higher. I did it once, for science sake, and never again: the longest ~27 minutes of my life.
To go up, up, and away I have to narrow the search.
Pen & Paper
The sample output above shows a posteriori the path to optimize the search. Among single digit numbers, only 0, 1, 5 and 6 can be classified as curious.
That narrows down the possible choices quite a lot; moreover, 0 and 1 are “special cases” valid only for single digit numbers (i.e. themselves!) therefore only 5 and 6 can lead to a curious number.
That is easily demonstrated: for a generic 2-digit number ending with 1, for example ( means first digit is , second digit is )
d 1 * d 1 = __________ d 1 + d2 d = __________ d2 2d 1
(2nd digit of squared number) = (corresponding digit in number) is true only for (falls back to 1-digit number case). Things are a little more interesting for and : the first easily leads to 25 as a solution, the latter allows for a few additional considerations.
The square of results in that has the solution for , which makes no sense because is a single digit. Since has to be a single digit, too, carrying 1 or 2 to the left digit if (for ), we need the modulo 10 of it (the remainder of division by 10). So:
and finally ; any (integer) value of q provides a viable solution, but only gives a single digit one, , leading to 76 as curious number. Great! Any number ending in 25 or 76 is good: the script will be processing 2×10limit-2 compared to 10limit-10 numbers (2×106 compared to ~108 at
limit = 8 for example, ~50 times less) with a massive efficiency improvement. Measured execution time is consistent with the reduced amount of processed numbers: 2.64s are roughly 1/50th of the previous 134.34s.
And I used a tuple! And I had no idea at all two numbers enclosed in parentheses were a tuple! Yeah, how cool is this thing? 😉
# blah blah import and input stuff unchanged for order in range(2, limit+1): for n in range(10**(order-2), 10**(order-1)): for last in (25, 76): num = (n * 100) + last num_sqr = num**2 tail = (num_sqr % (10**order)) if num == tail: print(order, num_sqr, tail) # blah blah time and printing stuff unchanged
The long execution times at higher limits are only postponed, though.
The final leap towards the best implementation (at least, the best I could devise!) is made when the
last digits to append to numbers are updated at each loop with the results. That is: first time (
order = 2) the script finds 25 and 76, stores them and uses them for the next loop (
order = 3). Now 25 and 76 will be appended to form a 3-digit number, meaning we only need to loop over 1 remaining digit, (9 values, [1,9]) to find the next couple of numbers, 376 and 625. Overall, a total of a mere 9×
limit numbers will be processed! That means you probably won’t notice the execution time until you set
limit=106 or so (that’ll be 106 digits!). Again, this statement, already shown by program output, can be demonstrated quite easily comparing side by side the squares of two generic numbers ending with the same digit. I’ll consider last digit 6, 2- and 3-digit numbers for the example:
d 6 * c d 6 * d 6 = c d 6 = _____________ ________________________ 6d+3 6 + 6c 6d+3 6 + d2 6d = cd d2 6d + _____________ c2 cd 6c = d2+d 2d+3 6 ________________________ c2 cd+c 2c+d2+d 2d+3 6
Once a solution is found for a digit long number, the solution for digits must originate from because the squares of both numbers share the same last digits. Finally, it is also demonstrated why there are only 2 curious number for any given number of digits (including the special case of 1st digit = 0): moving to the left digits, the expressions to calculate their value is always a 1st degree equation. In the example above (3rd and 4th digit of with as calculated before):
(due to all the modulo stuff above).
A few sheets of paper were harmed in the process, but for a good reason.
Back to Keyboard & Screen
The modifications to previous version are quite little, and yet they have a dramatic effect on Speed effect absolutely relevant herespeed. As I realized from all the scribbling shown above, I have to feed the calculation loops with the result of one iteration as last digits of the next one. So, I started with a list of the first two (
last_digits) that is updated after a solution is found (replacing the current value
last, just used for the calculations, with the new one
last_digits[last_digits.index(last)] = num). The inner loop only cycles on a single digit, that is made large enough to accommodate the remaining digits. Clever trick. It works. Me happy 😀 Another nice refinement I found, that shaves off a few hundredths or tenths of a second, is the
break instruction after the
if clause: once the only new solution for a given group of
last_digits is found, the inner loop should stop and restart the search with the next group of
import time while True: try: limit = int(input('Enter limit: ')) if limit >= 2: break except ValueError: pass texec = time.clock() last_digits = [5, 6] for order in range(2, limit+1): for last in last_digits: for n in range(int(10**(order-1)), 10**order, 10**(order-1)): num = n + last num_sqr = num**2 tail = num_sqr % (10**order) if num == tail: last_digits[last_digits.index(last)] = num print(order, tail, num_sqr) break texec = time.clock() - texec print('Execution time: ' + str(texec) + ' seconds')
How fast is this? Well, this fast (
order = 20):
Or even this fast (
order = 500, the squared number is 1000-ish digits long, merely 0.21s to do all the magic):
Quite impressive, isn’t it? Just out of curiosity, I calculated how long it would take to reach this same
order at the pace of the brute force version of the script: the result is not a curious number, it’s a ludicrous number. I’ll just leave it here: 5.13×10486 years. Well, that would be the hell of an uptime!
That’s all for now (it’s more than enough, actually). It was fun and definitely not bad for a first taste. Not bad at all.