Natural numbers ($2\leq n$) divided into two sets. I'm trying to find characterization of these sets.

Question

Here is tiny program that finds biggest prime divisor of a number (function find), written in pseudocode (Project Euler 3rd exercise, original source in C language from https://codereview.stackexchange.com/a/74792 by Altinak):

GLOBAL VARIABLE highest;

factorize(n, f) {
    if (n < f)
        return n
    while (n mod f == 0) {
        n = n / f
        if (f > highest)
            highest = f
    }
    return n
}

find(n) {
    highest = 1

    n = factorize(n, 2)
    n = factorize(n, 3)

    if (n >= 5) {
        i = 5
        while (i * i <= n) {
            n = factorize(n, i)
            n = factorize(n, i + 2)
            i = i + 6
        }
    }
    if (n == 1)
        return highest
    else
        return n
}

Numbers $n$ (where $2\leq n$) can be divided in two sets:

1. where in the body of find(n) the end value of $n$ is equal to $1$;
2. the other case - the final value of $n$ isn't equal to $1$.

I have difficulties characterizing these two sets. I need that for writing a post-condition (?, I believe it's called so) for the first if in the body of the find function. (I'm trying to prove the correctness of this program.)

I will think about it and post answer if I find it. But big thanks in advance for any hints!

Possible answer:

For now it seems that the 1st set is characterized by such condition: $N=1 \vee \left(W_N^2 | N\right) \vee \left(\operatorname{prime}\left(W_N-2\right) \wedge \left(\left(W_N-2\right)|N\right)\right)$ ($N$ here is the $n$ with $2$ and $3$ factored out of it, $W_N$ is the biggest prime divisor of $N$ and $\operatorname{prime}(X)$ means that $X$ is prime).

But I haven't proven that yet, as it is necessary to find the loop invariant for the loop inside find function to do that, probably.

Answer 1

I'm sorry I got a little confused in the comments but now I understand the logic behind it.

Characterizing them into 2 cases is extremely difficult but can be done if you define which set an element belongs to (case 1 or case 2) based on some sort of recursive process (like adding a factor smaller than n to get from any n in case 2 to another element in case 2) and then showing that such recursions eventually include every integer - probably using a proof by a contradiction of some sort.

But if you just want to show the correctness of your program there is a much simpler approach which is a proof by contradiction as follows:

Suppose there exists some smallest integer n such that your algorithm will not give it's largest prime factor: By our assumption that it is the smallest such integer it cannot be that $\, \exists i^2\le n$ for which $i | n$ or else we could divide and find a smaller counterexample (you might point out that your algorithm would then only check factors after i but if some other integer divides ${n \over i^k}$ then it also divides n and hence we could eliminate this possibility by considering the smallest such value of i). But we know that if n has no factors less than or equal to it's squareroot then it is prime and thus would be part of case 2.

If you still want to do this by splitting all of the integers into 2 sets I might be able to work it out but it doesn't seem to follow any nice rules. You would most likely have to define some process that eventually gives all numbers with 1 then 2 then 3 etc... prime factors.

Hope this helps.