Digits Sequence Problem

Problem Description

We are tasked with finding the n-th element of an infinite sequence defined as follows:

0, 1, 1, 2, 3, 5, 8, 13, 12, 7, 10, 8, 9, ...

• The 0th element of the sequence is 0.
• The 1st element of the sequence is 1.
• Each successive element is calculated as the sum of the separate digits of the two previous elements.

Examples

1. Given n = 2, the function should return 1.
2. Given n = 6, the function should return 8.
3. Given n = 10, the function should return 10.

Assumptions

• n is an integer within the range 0..1,000,000,000.
• You should write an efficient algorithm that handles large values of n effectively.

---

Requirements

1. Write a function with the following signature:

   function digits_sequence(int $n): int;

2. Optimize the function for:

   • Time complexity: Handle up to ( n = 1,000,000,000 ).
   • Memory complexity: Use minimal memory for storing intermediate values.

3. (Optional but recommended) Dockerize the solution for easy testing and deployment.

4. Write unit tests to validate the correctness of the function.

---

Example Function Call

<?php

echo digits_sequence(10); // Output: 10

---

Additional Considerations

• Use cycle detection to improve efficiency when repetitive patterns are observed in the sequence.
• Handle edge cases such as n = 0 and n = 1 separately.
• Include helper functions if necessary to keep the main function clean and readable.

---

Deliverables

1. digits_sequence.php: Implementation of the function.
2. tests/: Unit tests for verifying the correctness of the function.
3. Dockerfile: Docker setup for running the solution.
4. README.md: Explanation of the problem and how to run the solution.

---

Run Instructions

Run some digit example

make run_example

Run the tests

make run_tests