Как эффективно найти элемент последовательности Digit Sum?

20

Просто ради интереса я попытался решить проблему из категории «Недавние» Project Euler ( последовательность цифр суммы ). Но я не могу придумать, как решить проблему эффективно. Проблема заключается в следующем (в исходной последовательности вопросов в начале есть две, но она не меняет последовательность):

Последовательность цифр составляет 1,2,4,8,16,23,28,38,49 .... где термин NTчас последовательности представляет собой сумму цифр, предшествующих ему в последовательности. Найдите 1015Tчас член последовательности.

Наивное решение не может быть реализовано, потому что оно занимает много времени. Я пытался свести задачу к случаю матрицы экспоненциации (который был бы занимает О(Lограмм(1015)) количество времени) , но не могли придумать такое повторение подгонки линейных критериев, рецидивы для этой последовательности вполне своеобразно. Видно, что последовательность определяется повторением:

aNзнак равноaN-1+d(aN-1),,,,,(1)

где является n t h термом последовательности, а d является функцией, которая, когда в качестве входных данных задано натуральное число, возвращает сумму цифр числа (например,aNNTчасd ). Мой второй подход состоял в том, чтобы попытаться найти какой-то шаблон в последовательности. Можно видеть, что первые несколько членов последовательности можно записать в видеd(+786)знак равно21

   a_1 = 1  
   a_2 = 1 + d( 1 )
   a_3 = 1 + d( 1 ) + d( 1 + d( 1 ) )
   a_4 = 1 + d( 1 ) + d( 1 + d( 1 ) ) + d( 1 + d( 1 ) + d( 1 + d( 1 ) ) )
   a_5 = 1 + d( 1 ) + d( 1 + d( 1 ) ) + d( 1 + d( 1 ) + d( 1 + d( 1 ) ) ) + d( 1 +  d(  
   1 ) + d( 1 + d( 1 ) ) + d( 1 + d( 1 ) + d( 1 + d( 1 ) ) ) )

Из вышеприведенного шаблона выясняется, что член последовательности может быть сгенерирован следующим способом:NTчас

  1. Напишите 1 с добавлением символа между ними.2N-1 1
  2. Оставив первый , затем примените функцию d к следующим 2 0 слагаемым, затем к следующим 2 1 слагаемым, затем к следующим 2 2 слагаемым и так далее.1d202122
  3. Затем примените вышеуказанный метод рекурсивно к аргументам каждой применяемой функции .d

например, если n = 3, мы выполняем следующие манипуляции:

    1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
    1 + d( 1 ) + d( 1 + 1 ) + d( 1 + 1 + 1 + 1 )
    1 + d( 1 ) + d( 1 + d(1) ) + d( 1 + d( 1 ) + d( 1 +d( 1 ) ) )

Путем динамического программирования можно генерировать срок с использованием вышеуказанного метода в времени O ( л о г ( 2 10 15 ) ) , что опять - таки не лучше , чем наивным решения.NTчасО(Lограмм(21015))

РЕДАКТИРОВАТЬ 1
Другое, что можно наблюдать, что . Например, d ( a 6 ) = d ( 23 ) = d ( 32 ) = 5 . Но я не могу использовать эту точку зрения. Я снова попытался найти линейное рекуррентное соотношение (для возведения в степень матрицы), но я не могу его найти.d(aN)знак равноd(2N-1)d(a6)знак равноd(23)знак равноd(32)знак равно5

РЕДАКТИРОВАТЬ 2

Ниже приведен график, когда последовательность строится для меньшего диапазона (первые терминов последовательности нанесены). 106введите описание изображения здесь

PS: я знаю, что не стоит спрашивать решения у Project Euler. Но я просто хочу новое направление или подсказку, поскольку последние несколько дней я двигаюсь по кругу. Если это также неприемлемо, я могу снять вопрос, если предложено.

SashaS
источник
1
Я чувствую, что You are given a106 = 31054319.в оригинальной проблеме Эйлера это подсказка.
Филип Хаглунд
@FilipHaglund это не подсказка. Как только с помощью грубой силы, я могу легко вычислить это значение. Это просто для проверки вашего подхода.
Саш
3
Также в OEIS: oeis.org/A004207 .
Юваль Фильмус
@ EvilJS мог бы, да, я построил график так, чтобы он постепенно увеличивался зигзагообразно. Не могли бы вы уточнить свой последний пункт "" шаблоны кэширования ... ".
sashas
Учитывая, что интересные шаблоны появляются в моде 9, происходит ли что-нибудь интересное, если мы посмотрим на последовательность модов 11 или 99? Значение mod 11 может быть получено из суммы цифр с нечетным индексом и суммы цифр с нечетным индексом. Значение mod 99 может быть получено из суммы соседних пар цифр.
DW

Ответы:

4

Ваша последовательность описана в oeis.org/A004207 как сумма цифр. Есть несколько хороших моментов, например, последовательность мода 9 имеет повторяющийся узор , она разделяет цифровые корни сoeis.org/A065075иoeis.org/A001370. Если эти свойства полезны, это открытая проблема (потому что не существует уравнения в замкнутой форме для n - t h числа).(1,2,4,8,7,5)N-Tчас

Есть некоторые свойства этой последовательности, о которых стоит упомянуть:
когда вы вычисляете число , вам нужно хранить только счетчик (чтобы узнать, какой это был номер) и само число. Для перезапуска больше ничего не нужно, так как следующий номер - это текущий номер + сумма его цифр.N-Tчас

Делая некоторые шаги, чтобы сначала обеспечить скорость, хорошо помещать числа в массив, избегая наивных модов и вычислений div, которые стоят дорого. Это дает постоянное ускорение, но время от времени это имеет значение.

От начальной точки вы можете вычислить следующую и следующую, и это работает до некоторой точки, эта самая точка - это изменение числа цифр.
Что более важно, шаблоны меняются с увеличением чисел.
Цифровые суммы невелики по сравнению с самими числами, поэтому в большинстве операций изменяется только часть номера.
Так что же мы можем кешировать?

Мы знаем, что с двумя числами с одинаковой суммой цифр сложение для получения следующего числа будет одинаковым. Как насчет следующего?

саша

Оповещение спойлера, ниже приведен довольно явный шаблон кеша

Это зависит от дополнительных условий, таких как числа, которые не меняются во время прогона , я буду называть его сдвигом , стартовая сумма как стартовая .

Взяв произвольный прогон , например , и начав с 010009100N-Tчас

Ok. До сих пор какая-то100
1001

10

Нам действительно нужно рассчитать их все ? Не на самом деле нет.
Часть таблиц - это просто еще один начальный элемент.
Например, начиная с1,2,4,8

1101218305406517607+7198059041003



100,1000,10000,100000,... 1000000
100

Зло
источник
4

Поскольку вы спрашивали «новое направление или подсказку», а я не знаю ответа, я оставлю это здесь, надеюсь, это будет полезно. некоторые идеи:

Это имеет смысл, там будет шаблон мод 9, так как

К>1,КZ10К1модификация9

Что вы можете доказать по индукции.

Это означает, что все числа совпадают с суммой их цифр мод 9.

aNзнак равноd(aN)модификация9

aNзнак равноaN-1+d(aN-1)знак равно2d(aN-1)модификация9

Если мы продолжим расширять это повторение, мы получим

aNзнак равно2Nмодификация9

Что объясняет шаблон мод 9.

aNзнак равно9К+2N . На каждой итерации мы получаем пробел, который делится на 9. Насколько широки эти пробелы?

Вот немного меньше, чем общий код:

import matplotlib.pyplot as plt
import numpy as np

#sum digits of n
def sum_digits(n):
    s = 0
    while n:
        s += n % 10
        n //= 10
    return s

#get the sequence to n digits
def calculate(n):
    retval = [1]
    for i in range(n):
        retval.append(retval[-1] + sum_digits(retval[-1]))
    return retval;

#empirically confirm that a_n = 2^n mod 9
def confirmPow2(a):
    count = 0
    for i in a[:10000]:
        if((i%9) != (2**count % 9)):
            print "false"
        count = count + 1

#find gaps divisible by 9 in a subset of a
def find9Gaps(a):
    count = 0
    S = []
    for i in a[:10000]:
         S.append(((2**count ) - i)/9)
         count = count + 1
    return S

#repeatedly sum the digits until they're less than 9...
#gives some interesting patterns
def repeatedDigitSum():
    for i in range(1000, 1100):
         print "=========for ",i
         while i > 9:
                 i = sum_digits(i)
                 print i 


a = calculate(10**6)
b = find9Gaps(a)
plt.plot(range(len(b[:100])), b[:100])
plt.show()

Сюжет (для первых 100) выглядит экспоненциально, но я не думаю, что он идеален.

участок для пробелов

Вот вывод

>>> plt.plot(range(len(b[5:60])), np.log2(np.array(b[5:60])))
>>> plt.show()

логарифмический участок зазоров

Последнее, что у меня есть, это то, что кажется, что если вы сложите цифры числа, а затем сложите цифры полученного числа и повторите это, вы в конечном итоге получите это число mod 9.

Имеет смысл, учитывая вышеизложенный факт о полномочиях 10 мод 9.

Nd(N)d(d(N))модификация9

Это дает интересную последовательность чисел, хотя.

Изменить: видимо это называется "цифровой корень".

quietContest
источник
1
Это было как бы трижды прокомментировано. Также, когда вы делаете график, который выглядит экспоненциально для вас, может быть, вы должны использовать логарифм, сообщить об этом по оси шкалы? Если бы вы нарисовали читаемые 10 ^ 16 терминов, я был бы очень впечатлен.
Зло
Что было прокомментировано 3 раза? Люди говорили, что существует «шаблон мод 9», но я чувствовал, что не совсем понятно, что это было. Я просто немного изучил и прокомментировал то, что у меня было, так как не думаю, что смогу продолжать работать над этим. Опять же, у меня нет решения, но вопрос не был задан.
quietContest
Добавлен лог-план в соответствии с предложением EvilJS, я не могу построить больше, потому что срывается, и у меня действительно нет времени продолжать заниматься этой проблемой
quietContest