Repetition, and how to notice it

A process that must either stop or repeat, and two ways to tell which.

Key idea

The argument you already know

A process that repeatedly transforms a value, where the value stays within a finite range, must eventually revisit a value it has seen. From there it repeats forever.

That is the same finiteness argument as Unit 7's array-as-linked-list problem. The consequence is that any such process either reaches a target or enters a cycle, and there is no third outcome.

So the algorithm is: run the process, and stop when you either hit the target or detect repetition.

Below is the transformation itself, followed by the sequence it produces from 2, run far enough for the repeat to be visible.

1def digit_square_sum(n):2    total = 03    while n > 0:4        digit = n % 105        total += digit * digit6        n //= 107    return total8 9n = 210sequence = []11for _ in range(9):12    sequence.append(n)13    n = digit_square_sum(n)14 15print(sequence)16print("next would be", n, "which already appeared at position", sequence.index(n))

Eight distinct values and then it closes on itself, so 2 never reaches 1.

Key idea

Detecting the cycle without a set

The set costs memory proportional to the cycle length. The fast-and-slow pointers from Unit 7 detect the same repetition in constant space, with the transformation playing the role of the next pointer.

It is exactly the same code with a function call in place of a field access. Recognizing that the technique was never about linked lists is the point.

1def digit_square_sum(n):2    total = 03    while n > 0:4        total += (n % 10) ** 25        n //= 106    return total7 8slow, fast = 2, digit_square_sum(2)     # fast starts one step ahead9for step in range(1, 9):10    print(f"step {step}: slow={slow}, fast={fast}")11    if slow == fast:12        break13    slow = digit_square_sum(slow)14    fast = digit_square_sum(digit_square_sum(fast))

They meet without any record of what has been seen, which is the whole saving over a set.

Key idea

Repeated squaring, a different use of repetition

A related idea: computing a power by repeated multiplication takes as many steps as the exponent. Squaring instead halves the exponent each step, so it takes about log of it.

Whether the exponent is odd decides whether one factor is peeled off first. Both the loop and the recursion are short; write whichever you can state the invariant for.

Below the exponent is halved down to nothing, with the odd steps marked. Those marks are exactly the binary digits of the exponent, which is what the technique really is.

1exponent = 132 3while exponent > 0:4    print(f"exponent {exponent:>2}: {'odd, peel one off' if exponent % 2 else 'even, just square'}")5    exponent //= 2

Four steps for an exponent of 13, against thirteen for repeated multiplication.

Predict the output· 5 min

Predict the output: why the values cannot run away

The transformation squares each digit and adds the results. The largest value it can produce from an input of a given length is worked out. Type the three lines it prints.

Python

1def digit_square_sum(n):2    total = 03    while n > 0:4        total += (n % 10) ** 25        n //= 106    return total7 8print("largest from 3 digits:", digit_square_sum(999))9print("largest from 4 digits:", digit_square_sum(9999))10print("so anything above 999 shrinks:", digit_square_sum(9999) < 9999)

Printed output

Problem· 20 min

Happy Number

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

Problem· 22 min

Powx N

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1def digit_square_sum(n):2 total = 03 while n > 0:4 digit = n % 105 total += digit * digit6 n //= 107 return total8 9n = 210sequence = []11for _ in range(9):12 sequence.append(n)13 n = digit_square_sum(n)14 15print(sequence)16print("next would be", n, "which already appeared at position", sequence.index(n))

1def digit_square_sum(n):2 total = 03 while n > 0:4 total += (n % 10) ** 25 n //= 106 return total7 8slow, fast = 2, digit_square_sum(2) # fast starts one step ahead9for step in range(1, 9):10 print(f"step {step}: slow={slow}, fast={fast}")11 if slow == fast:12 break13 slow = digit_square_sum(slow)14 fast = digit_square_sum(digit_square_sum(fast))

1def digit_square_sum(n):2 total = 03 while n > 0:4 total += (n % 10) ** 25 n //= 106 return total7 8print("largest from 3 digits:", digit_square_sum(999))9print("largest from 4 digits:", digit_square_sum(9999))10print("so anything above 999 shrinks:", digit_square_sum(9999) < 9999)