project_euler.problem_551.sol1
==============================

.. py:module:: project_euler.problem_551.sol1

.. autoapi-nested-parse::

   Sum of digits sequence
   Problem 551

   Let a(0), a(1),... be an integer sequence defined by:
        a(0) = 1
        for n >= 1, a(n) is the sum of the digits of all preceding terms

   The sequence starts with 1, 1, 2, 4, 8, ...
   You are given a(10^6) = 31054319.

   Find a(10^15)



Attributes
----------

.. autoapisummary::

   project_euler.problem_551.sol1.base
   project_euler.problem_551.sol1.ks
   project_euler.problem_551.sol1.memo


Functions
---------

.. autoapisummary::

   project_euler.problem_551.sol1.add
   project_euler.problem_551.sol1.compute
   project_euler.problem_551.sol1.next_term
   project_euler.problem_551.sol1.solution


Module Contents
---------------

.. py:function:: add(digits, k, addend)

   adds addend to digit array given in digits
   starting at index k


.. py:function:: compute(a_i, k, i, n)

   same as next_term(a_i, k, i, n) but computes terms without memoizing results.


.. py:function:: next_term(a_i, k, i, n)

   Calculates and updates a_i in-place to either the n-th term or the
   smallest term for which c > 10^k when the terms are written in the form:
           a(i) = b * 10^k + c

   For any a(i), if digitsum(b) and c have the same value, the difference
   between subsequent terms will be the same until c >= 10^k.  This difference
   is cached to greatly speed up the computation.

   Arguments:
   a_i -- array of digits starting from the one's place that represent
          the i-th term in the sequence
   k --  k when terms are written in the from a(i) = b*10^k + c.
         Term are calulcated until c > 10^k or the n-th term is reached.
   i -- position along the sequence
   n -- term to calculate up to if k is large enough

   Return: a tuple of difference between ending term and starting term, and
   the number of terms calculated. ex. if starting term is a_0=1, and
   ending term is a_10=62, then (61, 9) is returned.


.. py:function:: solution(n: int = 10**15) -> int

   returns n-th term of sequence

   >>> solution(10)
   62

   >>> solution(10**6)
   31054319

   >>> solution(10**15)
   73597483551591773


.. py:data:: base

.. py:data:: ks

.. py:data:: memo
   :type:  dict[int, dict[int, list[list[int]]]]