Just out of interest I tried to solve a problem from "Recent" category of Project Euler ( Digit Sum sequence ). But I am unable to think of a way to solve the problem efficiently. The problem is as follows ( in the original question sequence has two ones in beginning , but it does not change the sequence ) :
The Digit Sum sequence is 1,2,4,8,16,23,28,38,49.... where the $n^{th}$ term of sequence is sum of digits preceding it in the sequence. Find the $10^{15}th$ term of the sequence.
The naive solution can't be implemented because it takes a lot of time. I tried to reduce the problem to a case of matrix exponentiation ( that would takes $O(log ( 10^{15}))$ amount of time ) but could not come up with such a recurrence fitting the linear criteria as recurrence for this sequence is quite peculiar. It can be seen that the sequence is governed by the recurrence :
$$ a_n = a_{n-1} + d( a_{n-1} ) ..... (1 )$$
where $a_n$ is $n^{th}$ term of the sequence and $d$ is a function which when given a natural number as input returns sum of digits of the number ( eg. $\;d(786)=21$ ). My second approach was to try to find some pattern in the sequence. It can be seen that the first few terms of the sequence can be written as
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 ) ) ) )
From the pattern above it becomes that $n^{th}$ term of the sequence can be generated by the following method :
- Write $2^{n-1}$ $1$'s with addition symbol between them.
- Leaving the first $1$, then apply the function $d$ on the next $2^{0}$ terms then on next $2^{1}$ terms, then on next $2^{2}$ terms and so on.
- Then apply the above method recursively on arguments of each $d$ function applied.
for example if n=3 we perform the following manipulations:
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 ) ) )
By dynamic programming I can generate the $n^{th}$ term using the above method in time $O(log ( 2^{10^{15}} ) )$, which again is no better than the naive solution.
EDIT 1
Another thing that can be observed is that $d(a_n) = d(2^{n-1})$. For example $d(a_6)=d(23)=d(32)=5$. But I am unable to make use of this point. I again tried to find a linear recurrence relation ( for matrix exponentiation ) , but I am unable to find it.
EDIT 2
Following is the graph when the sequence is plotted for smaller range ( first $10^6$ terms of the sequence are plotted ).
PS: I know it is not advisable to ask solutions from Project Euler. But I just want a new direction or a hint, as I have been moving in circles for past few days. If that is also unacceptable I can remove the question if suggested.
You are given a106 = 31054319.
in the original Euler problem is a hint. $\endgroup$