# An interesting algorithm

• Jan 8th 2014, 05:23 AM
RuyHayabusa
An interesting algorithm
For natural number N,we can take the smallest and largest prime divisors and get the sum of them and repeat the process as many times as we want.For example N=3 => sum of the smallest and largest prime divisors is 3+3=6 =>
2+3=5 => 5+5=10 => 2+5=7 etc... Prove that we can get a square number by doing this for any natural N.

I noticed that if N is even the sum of the primes would be odd,and if it's odd the sum would be even.I think there's a pattern but can't figure out what it is.Help would be apprciated.
• Jan 10th 2014, 12:01 PM
ebaines
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.