Results 1 to 2 of 2

Math Help - An interesting algorithm

  1. #1
    Junior Member
    Joined
    Feb 2013
    From
    US
    Posts
    37
    Thanks
    1

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor ebaines's Avatar
    Joined
    Jun 2008
    From
    Illinois
    Posts
    1,103
    Thanks
    321

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Division Algorithm or Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: April 10th 2013, 01:10 PM
  2. Is this interesting?
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: October 7th 2012, 06:12 PM
  3. Looks interesting
    Posted in the Math Forum
    Replies: 0
    Last Post: April 23rd 2010, 07:46 AM
  4. Interesting one!
    Posted in the Algebra Forum
    Replies: 2
    Last Post: November 13th 2008, 05:46 AM
  5. Interesting X
    Posted in the Geometry Forum
    Replies: 1
    Last Post: June 16th 2008, 03:44 PM

Search Tags


/mathhelpforum @mathhelpforum