Find The A 4 Digit Number Who's Square Is 8 Digits And Last 4 Digits Are The Original Number

From the comments on my answer here, the question was asked (paraphrase): Write a Python program to find a 4 digit whole number, that when multiplied to itself, you get an 8 digit

Solution 1:

Here is a 1-liner solution without any modules:

>>>next((x for x inrange(1000, 10000) ifstr(x*x)[-4:] == str(x)), None)
9376

If you consider numbers from 1000 to 3162, their square gives you a 7 digit number. So iterating from 3163 would be a more optimized because the square should be a 8 digit one. Thanks to @adrin for such a good point.

>>>next((x for x inrange(3163, 10000) ifstr(x*x)[-4:] == str(x)), None)
9376

Solution 2:

If you are happy with using a 3rd party library, you can use numpy. This version combines with numba for optimization.

import numpy as np
from numba import jit

@jit(nopython=True)deffind_result():
    for x inrange(1e7**0.5, 1e9**0.5):  
        i = x**2if i % 1e4 == x:
            return (x, i)

print(find_result())
# (9376, 87909376)

Solution 3:

[Almost] 1-liner:

from math import sqrt, ceil, floorprint(next(x for x in range(ceil(sqrt(10 ** 7)), floor(sqrt(10 ** 8 - 1))) if x == (x * x) % 10000))

printing:

9376

Timing:

%timeit next(x for x inrange(ceil(sqrt(10**7)), floor(sqrt(10**8-1))) if x == (x * x) %10000)
546 µs ± 32.5 µs per loop (mean ± std. dev. of7 runs, 1000 loops each)

@theausome 's answer (the shortest (character-wise)):

%timeit next((x for x inrange(3163, 10000) ifstr(x*x)[-4:] == str(x)), None)
3.09 ms ± 119 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

@jpp 's answer (the fastest):

import numpy as np
from numba import jit

@jit(nopython=True)deffind_result():
    for x inrange(1e7**0.5, 1e9**0.5):  
        i = x**2if i % 1e4 == x:
            return (x, i)
%timeit find_result()
61.8 µs ± 1.46 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Solution 4:

The following solution is not as readable as other answers. But what it lacks in readability, it gains in efficiency.

The brute force approach checks every number in a given range, making it O(10^n) where n is the number of desired digits (worst if we account for multiplication and conversions).

Instead, we can build the desired numbers from right to left, adding digits as long as the generated number forms the trailing digits of its square. This provides a O(n³) algorithm (see the time complexity section at the bottom).

defget_all_numbers(n, _digits=None):
    # We are provided digits that form a number with desired properties
    digits = [] if _digits isNoneelse _digits

    # Base case: if we attained the number of digits, return those digitsiflen(digits) >= n:
        return [int(''.join(digits))]

    solutions = []

    # Add digits from 0 to 9 and check if the new number satisfies our propertyfor x inrange(10):
        next_digits = [str(x)] + digits if x else ['0'] + digits
        next_number = int(''.join(next_digits))

        # If it does try adding yet another digitifint(str(next_number ** 2)[-len(next_digits):]) == next_number:
            solutions.extend(get_all_numbers(n, next_digits))

    # Filter out solutions with too few digits# Necessary as we could have prepended only zeros to an existing solutionreturn [sol for sol in solutions if sol >= 10 ** (n - 1)]

defget_numbers(n, sqr_length=None):
    if sqr_length:
        return [x for x in get_all_numbers(n) iflen(str(x ** 2)) == sqr_length]
    else:
        return get_all_numbers(n)

get_numbers(4, 8) # [9376]

This is not necessary for small numbers of digits, but allows to solve the problem for bigger inputs, where the brute force solution takes forever.

get_numbers(100) # Outputs in a few milliseconds

Time complexity

For a given number of digit n, there can only exist at most two solutions other than 0 and 1. And any solution is built from a solution for a smaller number of digits.

From that we conclude that despite the recursion, the algorithm takes O(n) steps to find a solution.

Now, each step has to execute some multiplication and conversions. Integer conversions are O(n²) and multiplication in Python uses Karatsuba's algorithm which is less than conversion.

Overall this yields a O(n³) time complexity.

This could be improved by using a linear integer conversion algorithm and would then provide a O(n^(1 + log(3))) complexity.

Solution 5:

Here's the one-line implementation, and it excludes 97.24% of candidates:

import itertools
step = itertools.cycle((24, 1, 24, 51))

[x for x inrange(3176, 10000, next(step)) ifstr(x*x)[-4:] == str(x) ]

Call the number abcd. You can optimize by restricting the last two digits cd, there are only 4 legal possibilities, excluding 96% of candidates for cd. Similarly we only need to test 31 <= ab < 100, excluding 31% of candidates for ab. Thus we excluded 97.24%

cd_cands = set((n**2) % 100for n inrange(0,99+1) if ((n**2 % 100) == n))
cd_cands = sorted(cd_cands)
[0, 1, 25, 76]

for ab inrange(31,99+1):
    for cd in cd_cands:
        n = ab*100 + cd
        if n**2 % 10**4 == n :
            print("Answer : {}".format(n))
            #break if you only want the lowest/unique solution... 
Solution: 9376

(Sure you could squeeze that into a one-line list comprehension, but it would be ugly)

Now we can separate the multiple for-loops with the following observations: strictly we only need to start testing at the first legal candidate above 3162, i.e. 3176. Then, we increment by successively adding the steps (100-76, 1-0, 25-1, 76-25) = (24, 1, 24, 51)

import itertools
step = itertools.cycle((24, 1, 24, 51))

abcd = 3176while abcd < 10**4:
    if abcd**2 % 10000 == abcd:
        print("Solution: {}".format(abcd))
    abcd += next(step)

and again that can be reduced to the one-liner(/two-liner) shown at top.

UPDATE: As @mathmandan shows, we can improve further to step = itertools.cycle((1, 624)), eliminating 99.68% of candidates. And start searching at 625 * 6 = 3750