Magic Number

Problem Statement

You are given a positive integer $n$ and a “magic number” $m$ which is a digit between $0$ and $9$ . Suppose we have a function $f(n)$ that takes in a number $n$ and output the sum of the squares of that number’s base ten digits. Let us define the sequence $\{a_i\}$ as follows:

$a_0 = n \\ a_{i + 1} = f(a_{i})$

Your task is described below:

Show that this sequence $a_i$ eventually has a cycle for all $n$ .
Write an algorithm to find the first $i$ such that the last digit of $a_i$ is our magic number $m$ , or return $-1$ if this never happens.
Suppose the statement of the first part was not true. How does this impact your algorithm’s performance.
What is the runtime of the algorithm.

For reference we have included some python starter code for you to use.

    # should return the first i such that the last digit of a_i is our magic number m given a_0 = n.
    # Return -1 if this never happens 
    def magic(n, m):
        # Your code here

Test Cases

Test Case 1

Input: 70, 2
Output: -1

Test Case 2

Input: 27, 3
Output: 1

Test Case 3

Input: 63, 3 
Output: 0

Click Below to see the Solution

Click Me

Part 1: Prove It!

Let us prove the following theorem:

Theorem: If $n > 1$ , $f(n) \leq 81 \left\lceil \log_{10}(n) \right\rceil$

Proof: First, if $n$ is a power of $10$ , then $f(n) = 1$ , which is by assumption less than $n$ . Otherwise $f(n)$ is simply equal to the sum of the digits of $n$ squared. Since each digit, by virtue of being a digit, is less than or equal to $9$ , each term in the sum is less than or equal to $9^2 = 81$ . As a result, since there are $\left\lceil \log_{10}(n) \right\rceil$ digits in $n$ (think about why), we see that $f(n)$ is less than or equal to $81 \left\lceil \log_{10}(n) \right\rceil$

Corollary: If $n > 300$ , $f(n) < n$ .

Proof Beyond 300, the function $81 \left\lceil \log_{10}(n) \right\rceil$ is less than the function $n$ . Sicne both function are increasing and the former grows slower than the latter (by virtue of being a logarthmic vs linear function), we see that $81 \left\lceil \log_{10}(n) \right\rceil < n$ for $n > 300$ . Applying the above theorem, we see that $f(n) < n$ for $n > 300$ .

Corollary: If $n \leq 300$ , $f(n) < 300$ .

Proof: This is trivial for $n = 1$ . Since $81 \left\lceil \log_{10}(n) \right\rceil$ is an increasing function, we see that it is less than $81 \left\lceil \log_{10}(300) \right\rceil = 243 < 300$ . Applying the theorem above, we see that $f(n) < 300$ .

Theorem: $a_i$ eventually has a cycle for all $n$ .

Proof We note that since this sequence is recursively defined, if for differing indices $i$ and $j$ , if $a_i = a_j$ , then there is a repeating cycle goes from $a_i$ up to $a_{j -1}$ and repeats.

So we only need prove that there exists two distinct indices $i$ and $j$ such that $a_i = a_j$ for all $n$ . First, by the first corollary, if $n > 300$ , there exists an $i$ such that $a_i < 300$ . This is because if we iteratively apply $f(n)$ , then the result will be less than the original value of $n$ (and be an integer). This means that eventually, this integer will become less than 300.

Now, given that there is some $a_i \leq 300$ , we see that it must stay less than or equal to $300$ . Since there are only a finite number of positive integers less than 300, by the pigeonhole principle, eventually an index must repeat. This will define our cycle.

Part 2: Code it Up

Algorithm

We will keep applying $f$ on the value $n$ until we find an index where the last digit is equal to the magic number. We also keep track of previously seen numbers in a hash-set. We know that since there will eventually be a cycle, if there is a number that we have seen before, and we have not found the magic number yet, we will never find such a number.

Code for the above algorithm can be seen below:


def magic(n, m):
    count = 0
    prev_seen = set()
    while n not in prev_seen:
        prev_seen.add(n)
        if(n % 10 == m):
            return count
        n = sum_square_digits(n)
    return -1

# return the sum of the square of the digits of n
def sum_square_digits(n):
    summ = 0
    while(n != 0):
        summ += (n % 10)**2
        n = n // 10
    return summ

Part 3: What if…

If the statement of the first theorem were not true, we could not guaruntee that there does not exist an index where $m$ is not the last digit of $a_i$ . Unless we had further information about the behavior of such a function, either we would have to continue our algorithm until it terminates (potentially taking an unbounded amount of computational time), or we would terminate after a set limit (which may impact the correctness of our algorithm).

Part 4: Runtime Analysis

The computational complexity of such an operation is determined by the number of function calls to $f$ mutliplied by the time it takes to compute $f$ . This time is simply $\log(n)$ . Since $f$ returns a number that is on the order of $\log(n)$ , the number of function calls to $f$ before $f$ gets small, is the same as the iterated logarithm or $O(\log^*)$ . Therefore the total runtime is at most $O(\log^*(n) \cdot \log(n))$ .

Once this is less than 300, there are at most 300 function calls before a cycle is found which is constant and does not affect the runtime.

Note: In practice, $\log^*$ decays so rapidly that it is effectively constant for any reasonable computation, so this algorithm is essentially a logararithmic runtime.