3
$\begingroup$

In a number sequence, 1, 13, 169 and 2014 are respectively the first four terms of the sequence. The next terms are equal to the sum of the four numbers that precede them. For example, the fifth term of this sequence is 1+13+169+2014=2197. How many digits does the 2014th term have?

If needed, we can use 0.285 for log(1.928) and 0.942 for log(8.748).

$\endgroup$
2
  • $\begingroup$ Is this supposed to have a solution that does not involve finding roots of the charateristic equation? Because otherwise it is a standard math problem. $\endgroup$ – justhalf Jun 11 '20 at 5:14
  • $\begingroup$ Oh, right. You put no-computer, so it should be so. $\endgroup$ – justhalf Jun 11 '20 at 5:20
5
$\begingroup$

This is a linear recursion with characteristic polynomial $x^4 - x^3 - x^2 - x - 1,$ which has roots $ z_1 = 1.928, z_2 = -0.775, z_{3,4} = -0.076 \pm 0.815i.$

The general solution is $x_n = \sum\limits c_i z_i^n,$ and the number of digits is $\lfloor \log_{10}(x_n) \rfloor + 1.$

Since $|z_2|, |z_3|, |z_4|<1,$ we have $|x_{2014} - c_1 z_1^{2014}| \le |c_2|+|c_3|+|c_4|,$ and the RHS is practically nothing.

Thus, $\lfloor \log_{10}(x_n) \rfloor \approx \lfloor \log_{10}(c_1 z_1^{2014}) \rfloor = \lfloor \log_{10}(c_1) + 574.0068 \rfloor.$

You can solve for the $c_i$ using the values of $x_1, \dots, x_4,$ but at a quick glance (and using the $y$-intercept of the graph in Fivesideddice's answer), we expect $100 \le c_1 \le 200 \Rightarrow \lfloor \log_{10}(x_n) \rfloor = 576,$ making the number of digits $577.$

$\endgroup$
6
  • 1
    $\begingroup$ $|c_2|+|c_3|+|c_4|$ should be $|c_2 z_2^{2014}| + |c_3 z_3^{2014}| + |c_4 z_4^{2014}|$ $\endgroup$ – Florian F Jun 11 '20 at 8:43
  • 1
    $\begingroup$ ... but $|c_2|+|c_3|+|c_4|$ also does the job, in fact. $\endgroup$ – Florian F Jun 11 '20 at 8:50
  • 1
    $\begingroup$ Computer solution has it at $576$ digits, $f(2014)\approx 9.09124\times 10^{575}$ $\endgroup$ – Daniel Mathias Jun 11 '20 at 9:59
  • 2
    $\begingroup$ This is certainly the right way to do the problem if computers are allowed (or at least a right way; just computing the values works OK too, but would be more painful if we wanted the length of the billionth instead of the 2014th number in the sequence). But with the [no-computers] tag? Finding the roots is a little laborious, and then finding the coefficients is a little painful too, if you want to do it in a way that lets you be confident of having the right final answer. $\endgroup$ – Gareth McCaughan Jun 11 '20 at 12:14
  • 1
    $\begingroup$ Incidentally, like Daniel I get 576 digits rather than 577. $\endgroup$ – Gareth McCaughan Jun 11 '20 at 12:15
2
$\begingroup$

Partial answer and progress:

So I put this into Wolfram Alpha, with the terms of f(n)=f(n-1)+f(n-2)+f(n-3)+f(n-4), f(1)=1, f(2)=13,f(3)=169,f(4)=2014, which can be found here. I noticed that in the graph provided (below), the general rule was 10^(n+2) = f(n*3.5), for n larger than 2.

enter image description here

This would make f(2014) = 10^577.4285714, since 2014 = 575.4285714 * 3.5 and the rule is 10^(n+2) = f(n*3.5). That would make the 2014th term in the series have 577 digits.

This is a rough estimate, and I’d like to prove beyond just extrapolating from a graph later.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.