Re: An interesting algorithm

By "get a square number" I assume that you mean if you get into a repeating loop at least one of the numbers is a square. For example: 3-6-5-10-7-14-9-6-5-10-14-9-6-5 - .....

has the number 9 in the loop. Another example; 39 - 16 - 4 - 4 - 4... has both 16 and 4 in the sequence.

You can prove this using induction. The folowing explanation is not a rigorous proof but I hope yuo can see what I'm getting at.

First show that the algorithm works for N= 2, 3, 4, and 5. For larger values of N, if it's a composite number then the sum of the largest and smallest primes is always less than N, so you get into a loop that has already yielded a square. If N is a prime number then two steps later the algorithm always yields N+2. If N+2 is a composite number then the sum of its largest amd smallest primes is less than N, so you get into a loop that you know yields a square; and if N+2 is prime then two steps later it yields N+4, which must be a composite (you can't have three odd numbers in a row that are all prime for N>3, because one of them will have 3 as a prime factor). The sum of the largest and smallest primes for N+4 will be less than N for any composuite number >5, so again, it becomes a sequence already proven to yield a square.