Find numbers that have long "square adding" chain lenghts

square_adding.py

from math import *
import random

__author__ = "Lumi Pakkanen"
__licence__ = "Public domain"
__version__ = "1.0.0"

# See https://youtu.be/hGQdsibB2is for context.


def digit_sum(n):
    result = 0
    while n:
        result += n%10
        n //= 10
    return result


def num_digits(n):
    if n == 0:
        return 1
    return 1 + floor(log(n) / log(10))


def square_square(n):
    return 2*digit_sum(n)*num_digits(n)


def chain_length(n):
    seen = set()
    chain_length_ = 0
    while True:
        chain_length_ += 1
        n = square_square(n)
        if n in seen:
            return chain_length_
        seen.add(n)


def digit_bag(counts_per_digit, ignore_errors=False):
    """
    Returns a sorted integer with specified counts for the digits.
    """
    leading = 0
    for n, count in enumerate(counts_per_digit[1:]):
        if count:
            leading = n + 1
            break
    if leading == 0:
        if ignore_errors:
            return 0
        raise ValueError("Cannot have a number with zeros only.")
    digits = [leading]
    for n, count in enumerate(counts_per_digit):
        if n == leading:
            count -= 1
        for _ in range(count):
            digits.append(n)
    n = 0
    for d in digits:
        n = 10*n + d
    return n


smallest_of_lenght = dict()


N = 6
for a in range(N):
    for b in range(N):
        for c in range(N):
            for d in range(N):
                for e in range(N):
                    for f in range(N):
                        for g in range(N):
                            for h in range(N):
                                for i in range(N):
                                    for j in range(N):
                                        n = digit_bag([a, b, c, d, e, f, g, h, i, j], ignore_errors=True)
                                        l = chain_length(n)
                                        if l not in smallest_of_lenght or n < smallest_of_lenght[l]:
                                            smallest_of_lenght[l] = n
                                            print("")
                                            for length, number in sorted(smallest_of_lenght.items()):
                                                print("{}: {}".format(length, number))


print("Exhaustive search done up to {} repetitions of any digit.".format(N))

print("Adding the record holder so far...")
smallest_of_lenght[12] = 10012566679999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
for length, number in sorted(smallest_of_lenght.items()):
    print("{}: {}".format(length, number))

M = 239
print("Commencing opportunistic random search of {} total digits...".format(M))


while True:
    counts = []
    remaining = M
    for i in range(9):
        count = random.randint(0, remaining)
        counts.append(count)
        remaining -= count
    counts.append(remaining)
    counts.reverse()
    n = digit_bag(counts, ignore_errors=True)
    l = chain_length(n)
    if l not in smallest_of_lenght or n < smallest_of_lenght[l]:
        smallest_of_lenght[l] = n
        print("")
        for length, number in sorted(smallest_of_lenght.items()):
            print("{}: {}".format(length, number))