Prove that no new numbers are generated after 1 iterations no matter how big $N$ is.

Question

Given a positive integer N,

1. Define limit $L= \lfloor N^{1/2} \rfloor$
2. Create a list of number $\lfloor N/i \rfloor $ for all $i \in [1,\lceil N^{1/2} \rceil +1]$ but $\ge L$.
3. On second iteration choose the next largest number in the list ie $\lfloor N/2 \rfloor $ as numerator and repeat above step(ie only step2, not step 1) for all i such that new generated numbers are $\ge L$ and add the newly generated numbers to the list.On third iteration with next biggest currently in list(ie till second iteration) ie $\lfloor N/3 \rfloor $ and so on.

    def generate_new_elems(N, L):
        # print("doing for", N)
        N_sq = int(N ** 0.5)
        touch_points = []
        for i in range(2, N_sq + 2):
            if N // i < L:
                break
            else:
                touch_points.append(N // i)
        return [N] + touch_points
    
    highest_iteration = 0
    for StartingN in range(2, 10000):
        L = int(StartingN ** 0.5)
        touch_points = generate_new_elems(StartingN, L)
        iteration_cnt = 1
    
        for i in range(1, len(touch_points)):
            new_elems = generate_new_elems(touch_points[i], L)
            old_size = len(touch_points)
            for e in new_elems:
                if e not in touch_points:
                    touch_points.append(e)
            touch_points.sort()
            touch_points.reverse()
            print(touch_points)
            print(iteration_cnt)
            new_size = len(touch_points)
            if old_size != new_size:
                iteration_cnt = i+1
    
        highest_iteration = max(highest_iteration, iteration_cnt)
        print(StartingN, iteration_cnt)
        print("highest_iteration=", highest_iteration)

We find, beyond 1st iteration no new numbers are being generated.

Prove that it takes no more than 1 iterations to reach a stable point ie a stage such that no new number outside the list is generated for further iterations.

I have run programatic simulation all $N$s till 10 million and found in no case it takes more than 1 iterations to reach stable state.

Example:

• $N=100$,

After 1st iteration: $[100, 50, 33, 25, 20, 16, 14, 12, 11, 10]$

So for $N=100$, only one iteration is needed to reach stable state.

For $N=100$ case it remains same no matter how many times you iterate.

Answer 1

One important fact for this problem is that $\lfloor\frac{\lfloor\frac{N}{a}\rfloor}{b}\rfloor=\lfloor\frac{N}{ab}\rfloor$. Proof:

Let $q,r\in\Bbb{N}\space |\space\lfloor\frac{N}{a}\rfloor=qb+r,0\le r\lt b$

So $q$ is the quotient of $\frac{\lfloor\frac{N} {a}\rfloor}{b}$ and $r$ is the remainder of $\frac{\lfloor\frac{N}{a}\rfloor}{b}$.

This implies:$$\frac{\lfloor\frac{N}{a}\rfloor}{b}=q+\frac{r}{b}\quad [1]$$ and $$\lfloor\frac{\lfloor\frac{N}{a}\rfloor}{b}\rfloor=q\quad [2]$$ Clearly, $$\frac{N}{a}-\lfloor\frac{N}{a}\rfloor\lt 1 \quad[3]$$ $$\frac{N}{ab}-\frac{\lfloor\frac{N}{a}\rfloor}{b}\lt \frac{1}{b} \quad[4]$$ $$\frac{N}{ab}\lt\frac{\lfloor\frac{N}{a}\rfloor}{b}+ \frac{1}{b} \quad[5]$$

Using eq. [1] we can substitute $\frac{\lfloor\frac{N}{a}\rfloor}{b}$ for $q+\frac{r}{b}$

$$\frac{N}{ab}\lt q+\frac{r}{b}+ \frac{1}{b} \quad[6]$$

To maximize $\frac{N}{ab}$ we let $r$ be the maximum value $b-1$.

$$\frac{N}{ab}\lt q+\frac{b-1}{b}+ \frac{1}{b} \quad[7]$$

$$\frac{N}{ab}\lt q+\frac{b-1+1}{b} \quad[8]$$

$$\frac{N}{ab}\lt q+\frac{b}{b} \quad[9]$$

Clearly,

$$\lfloor\frac{N}{a}\rfloor\le\frac{N}{a}\quad[10]$$

$$\frac{\lfloor\frac{N}{a}\rfloor}{b}\le\frac{N}{ab}\quad[11] $$

Now using [1],[11], and [9] we have the following inequality:

$$q\le\frac{\lfloor\frac{N}{a}\rfloor}{b}\le\frac{N}{ab}\lt q+1 \quad[12]$$

$$q=\lfloor\frac{\lfloor\frac{N}{a}\rfloor}{b}\rfloor=\lfloor\frac{N}{ab}\rfloor\quad[13]$$

QED

This means that iterations after the first are redundant. For example the third term in the second iteration is $\lfloor\frac{\lfloor\frac{N}{2}\rfloor}{3}\rfloor = \lfloor\frac{N}{6}\rfloor$ This is the same term as the sixth term for the first iteration.

All elements of iterations beyond the first will just create elements that was already created by the first. So in general The $b^{th}$ element of the $a^{th}$ iteration will be the $(a*b)^{th}$ element of the first iteration.