How to resolve the algorithm Iterated digits squaring step by step in the Python programming language

Published on 12 May 2024 09:40 PM
#Python

How to resolve the algorithm Iterated digits squaring step by step in the Python programming language

Table of Contents

Problem Statement

If you add the square of the digits of a Natural number (an integer bigger than zero), you always end with either 1 or 89: An example in Python:

Or, for much less credit - (showing that your algorithm and/or language is slow): This problem derives from the Project Euler problem 92. For a quick algorithm for this task see the talk page

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Iterated digits squaring step by step in the Python programming language

The code you provided consists of three different Python functions that calculate the number of D-digit numbers composed of digits from 0 through 9 that, when squared and summed, produce 89.

Main Function:

  1. main():
    • It initializes a list number of 10 elements to store digits, a variable result to store the count of valid numbers, and a variable i to traverse the list.
    • The outer loop iterates through the digits from right to left, with i representing the current digit's position.
    • If i is 0 and the current digit is 9, it indicates the end of the loop, and if i is the last index and the current digit is less than 9, it increments the digit and checks if the resulting number is valid.
    • If the current digit is 9, it moves to the previous digit by decrementing i.
    • Otherwise, it increments the current digit, copies its value to the remaining digits, updates i to the last index, and checks if the resulting number is valid.
    • The code accumulates the count of valid numbers in the result variable.

Helper Functions:

  1. next_step(x):

    • This function squares and sums the digits of a number x to calculate the next step in the process of determining whether it produces 89 when squared and summed repeatedly.

  2. check(number):

    • It takes a list of digits number as input and checks if the corresponding number produces 89 when squared and summed repeatedly.
    • If the number produces 89, it calculates the number of unique permutations that can be formed from the digits in the number and returns that count. Otherwise, it returns 0.

Alternative Approaches (not in the provided code):

  1. Using the combinations_with_replacement function from the itertools module, you can generate all possible combinations of D digits and check if the corresponding number produces 89.

  2. Using the @lru_cache decorator, you can memoize the results of the ids function to optimize the computation.

  3. Using the check89 function, you can iteratively check if a number produces 89 when squared and summed repeatedly.

These alternative approaches provide different ways to solve the same problem, emphasizing efficiency and optimization.

Source code in the python programming language

from math import ceil, log10, factorial

def next_step(x):
    result = 0
    while x > 0:
        result += (x % 10) ** 2
        x /= 10
    return result

def check(number):
    candidate = 0
    for n in number:
        candidate = candidate * 10 + n

    while candidate != 89 and candidate != 1:
        candidate = next_step(candidate)

    if candidate == 89:
        digits_count = [0] * 10
        for d in number:
            digits_count[d] += 1

        result = factorial(len(number))
        for c in digits_count:
            result /= factorial(c)
        return result

    return 0

def main():
    limit = 100000000
    cache_size = int(ceil(log10(limit)))
    assert 10 ** cache_size == limit

    number = [0] * cache_size
    result = 0
    i = cache_size - 1

    while True:
        if i == 0 and number[i] == 9:
            break
        if i == cache_size - 1 and number[i] < 9:
            number[i] += 1
            result += check(number)
        elif number[i] == 9:
            i -= 1
        else:
            number[i] += 1
            for j in xrange(i + 1, cache_size):
                number[j] = number[i]
            i = cache_size - 1
            result += check(number)

    print result

main()


from itertools import combinations_with_replacement
from array import array
from time import clock
D = 8
F = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000]
def b(n):
    yield 1
    for g in range(1,n+1):
        gn = g
        res = 0
        while gn > 0:
            gn,rem = divmod(gn,10)
            res += rem**2
        if res==89:
            yield 0
        else:
            yield res
N = array('I',b(81*D))
for n in range(2,len(N)):
    q = N[n]
    while q>1:
        q = N[q]
    N[n] = q

es = clock()
z = 0
for n in combinations_with_replacement(range(10),D):
    t = 0
    for g in n:
        t += g*g
    if N[t] == 0:
        continue
    t = [0,0,0,0,0,0,0,0,0,0]
    for g in n:
        t[g] += 1
    t1 = F[D]
    for g in t:
        t1 /= F[g]
    z += t1
ee = clock() - es
print "\nD==" + str(D) + "\n  " + str(z) + " numbers produce 1 and " + str(10**D-z) + " numbers produce 89"
print "Time ~= " + str(ee) + " secs"


>>> from functools import lru_cache
>>> @lru_cache(maxsize=1024)
def ids(n):
	if n in {1, 89}: return n
	else: return ids(sum(int(d) ** 2 for d in str(n)))

	
>>> ids(15)
89
>>> [ids(x) for x in range(1, 21)]
[1, 89, 89, 89, 89, 89, 1, 89, 89, 1, 89, 89, 1, 89, 89, 89, 89, 89, 1, 89]
>>> sum(ids(x) == 89 for x in range(1, 100000000))
85744333
>>>


>>> from functools import lru_cache
>>> @lru_cache(maxsize=1024)
def _ids(nt):
	if nt in {('1',), ('8', '9')}: return nt
	else: return _ids(tuple(sorted(str(sum(int(d) ** 2 for d in nt)))))

	
>>> def ids(n):
	return int(''.join(_ids(tuple(sorted(str(n))))))

>>> ids(1), ids(15)
(1, 89)
>>> [ids(x) for x in range(1, 21)]
[1, 89, 89, 89, 89, 89, 1, 89, 89, 1, 89, 89, 1, 89, 89, 89, 89, 89, 1, 89]
>>> sum(ids(x) == 89 for x in range(1, 100000000))
85744333
>>> _ids.cache_info()
CacheInfo(hits=99991418, misses=5867462, maxsize=1024, currsize=1024)
>>>


from __future__ import print_function
from itertools import count

def check89(n):
    while True:
        n, t = 0, n
        while t: n, t = n + (t%10)**2, t//10
        if n <= 1: return False
        if n ==89: return True

a, sq, is89 = [1], [x**2 for x in range(1, 10)], [False]
for n in range(1, 500):
    b, a = a, a + [0]*81
    is89 += map(check89, range(len(b), len(a)))

    for i,v in enumerate(b):
        for s in sq: a[i + s] += v

    x = sum(a[i] for i in range(len(a)) if is89[i])
    print("10^%d" % n, x)

You may also check:How to resolve the algorithm Loops/Infinite step by step in the EDSAC order code programming language
You may also check:How to resolve the algorithm P-Adic square roots step by step in the Julia programming language
You may also check:How to resolve the algorithm Look-and-say sequence step by step in the Objective-C programming language
You may also check:How to resolve the algorithm Command-line arguments step by step in the Sather programming language
You may also check:How to resolve the algorithm Input loop step by step in the BASIC programming language