Skip to content

Problem Solving with Iteration

Problem Set

The following problem sets are intended for practice. Attempt these on your own.

Unique Divisor

Problem

Problem Description

Given an integer \(n\), another integer \(d\) is a divisor if \(n\) is fully divisible by \(d\). By fully divisible, we mean that there is an integer \(k\) such that \(d \times k = n\). Actually, both \(d\) and \(k\) are both divisors! What we want is to find the number of unique divisors of a number \(n\). We ensure that \(n\) is positive (i.e., \(n > 0\)) and we want only positive \(d\).

Let \(n = 6\), there are 4 unique divisors: \(1\), \(2\), \(3\) and \(6\) because \(1 \times 2 = 6\) and \(2 \times 3 = 6\).

Let \(n = 9\), there are 3 unique divisors: \(1\), \(3\), and \(9\) because \(1 \times 9 = 9\) and \(3 \times 3 = 9\).

Let \(n = 1\), there is only 1 unique divisor, which is \(1 \times 1 = 1\).

Task

Write Python code to compute and print the number of unique divisors of a number n.

Assumptions

  • n is a positive integer (i.e., n > 0).
Hints
Hint #1

Say we have a number d, how do we know if d is a divisor of n?

1
n % d == 0
Hint #2

What are the possible range of divisors of n?

The smallest is 1 and the largest is n.

Hint #3

What kind of loop can we use?

We can easily use fixed repetition.

Possible Solution 
1
2
3
4
5
6
# Assume n is initialized
ctx, d = 0, 1
while d < n:
  if n % d == 0:
    ctx = ctx + 1
print(ctx)

Fixed Arctan

Problem

Problem Description

The Taylor series expansion for \(\text{arctan}(x)\) is also quite simple as shown below.

\[ \text{arctan}(x) = x - \frac{x^3}{3} + \frac{x^5}{5} - \cdots = {\displaystyle \sum_{i = 0}^{\infty} (-1)^i \frac{x^{2i + 1}}{2i + 1}} \]

Task

Write Python code to compute \(\text{arctan}(x)\) approximated to n iterations. In other words, compute the following.

\[ \text{arctan}(x)_n = x - \frac{x^3}{3} + \frac{x^5}{5} - \cdots = {\displaystyle \sum_{i = 0}^{n-1} (-1)^i \frac{x^{2i + 1}}{2i + 1}} \]

Assumptions

  • x is a floating point number between 0 and 1 (i.e., 0 < x < 1).
  • n is a positive integer (i.e., n < 0).
  • x and n are initialized.
Hints

There is no hints, this should be a straightforward modification of \(\text{ln}(1 + x)\).

Possible Solution 
1
2
3
4
5
6
7
# Assume x and n are initialized
res = 0
i = 0         # start from 0
while i < n:  # end at n - 1
  res = res + (((-1) ** i) * (x ** (2 * i + 1)) / (2 * i + 1))
  i = i + 1
print(res)

Precise Arctan

Problem

Problem Description

This is the same problem as above, but we will stop at 4 decimal places.

Task

Write Python code to compute \(\text{arctan}(x)\) approximated to 4 decimal places.

Assumptions

  • x is a floating point number between 0 and 1 (i.e., 0 < x < 1).
  • x is initialized.
Hints

There is no hints, this should be a straightforward modification of \(\text{ln}(1 + x)\).

Possible Solution 
1
2
3
4
5
6
7
8
9
# Assume x is initialized
res = 0
i = 0    # start from 0
val = (((-1) ** i) * (x ** (2 * i + 1)) / (2 * i + 1))
while abs(val) >= 0.0001:
  res = res + val
  i = i + 1
  val = (((-1) ** i) * (x ** (2 * i + 1)) / (2 * i + 1))
print(res)

Number of Digits

Problem

Problem Description

Given a positive integer \(n\), we want to find the number of digits of \(n\).

Task

Write Python code to compute and print the number of digits of n.

Assumptions

  • n is a positive integer (i.e., n > 0).

Restrictions

  • You are NOT allowed to convert to other data types.
    • You must work only on integer.
    • Otherwise, it is simply len(str(n)).
Hints
Hint #1

What kind of loop can we use?

To use fixed repetition, we need to know how many times we need to loop. The number of times we need to loop is exactly the number of digits. Unfortunately, that is this current problem. So we need to use arbitrary repetitions.

Hint #2

What should be the condition to stop?

What is/are the number(s) with the smallest number of digits? Since \(n > 0\), we can say that we stop when it is a single digit. Alternatively, we can stop when \(n = 0\).

Hint #3

Given the condition to stop, what is the condition to continue?

  • Stop when number of digit is one: while n >= 10:
  • Stop when \(n\) is zero: while n > 0:
Hint #4

How do we get simpler number with fewer number of digits to help us towards the stopping condition?

We remove one digit. 

1
n = n // 10 # remove rightmost digit

Possible Solution

We will explain the solution in more details later.