Подсчитать количество чисел, принадлежащих интервалу

Question

необходимо подсчитать количество чисел в интервале от 222222222 до 333333333, которое при записи в хотя бы одной системе счисления с основанием от 2 до 36 состоит из нескольких одинаковых цифр.

count = 0 
for num in range(222222222, 333333334):
smooth = False
for base in range(2, 37):
    if len(set(str(num))) == 1:
        smooth = True
        break
if smooth:
    count += 1
print(count)

Answer 1

можно использовать многопоточность для ускорения процесса

import numpy as np
import concurrent.futures

def check(num):
    for base in range(2, 37):
        try:
            converted = np.base_repr(num, base)
            if len(set(converted)) == 1:
                return True
        except ValueError:
            continue
    return False

def main():
    count = 0
    with concurrent.futures.ThreadPoolExecutor() as executor:
        results = list(executor.map(check, range(222222222, 333333334)))
        count = results.count(True)
    print(count)

if __name__ == "__main__":
    main()

Answer 2

Вариант решения

def num_to_base(x, base):  # необязательная вспомогательная функция отображения числа в системах счисления
    s, zero = '', ord('0')
    while x:
        x, y = divmod(x, base)
        s += chr(y + zero + 7 * (y > 9))
    return s[::-1]


cnt, start, end = set(), 222222222, 333333333
for base in range(2, 37):  # перебираем системы счисления
    for num in range(1, base):  # перебираем цифры в системах счисления от 1 до base-1
        s = 0  # здесь будет формироваться число, записываемое одинаковыми цифрами для каждой из систем счисления
        while s <= end:  # цикл пока число не превысило верхнюю границу диапазона
            if s >= start:
                cnt.add(s)  # если число в диапазоне, добавляем его
                # print(f'Основание {base}: {num_to_base(s, base)}, десятичное: {s:_}')  # печать для наглядности
            s = s * base + num  # сдвигаем число на разряд влево и добавляем справа младший разряд
print(len(cnt))

Answer 3

Перебирать числа-кандидаты и проверять каждое - тупик. Их линейное количество, а количество найденых - логарифмическое. Ещё одна причина - порождать числа из одинаковых цифр значительно проще чем проверять числа на "одинаковоциферность".

Генератор repunits(base) возвращает бесконечную последовательность репьюнитов в указаной системе счисления: 1_base, 11_base, 111_base, ....

Генератор repdigits(base) возвращает бесконечную последовательность репдиджитов.

Функция count_repdigits(low, high) составляет множество репдиджитов для оснований от 2 до 36 в интервале [low, high] и возвращает его размер.

def repunits(base):
    n = 0
    while True:
        n = base * n + 1
        yield n


def repdigits(base):
    for n in repunits(base):
        yield from range(n, base * n, n)


def count_repdigits(low, high):
    s = set()
    for base in range(2, 36 + 1):
        for n in repdigits(base):
            if high < n:
                break
            if low <= n:
                s.add(n)
    return len(s)


print(count_repdigits(222222222, 333333333))

$ python count_repdigits.py
87

БЛОГ НА HUSL

Подсчитать количество чисел, принадлежащих интервалу

Ответы (3 шт):