Thread: Interesting number theory problem

  1. #1
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686

    Interesting number theory problem

    This is an interesting problem I ran into last week. I thought I might post it as I have very little clue about how to actually solve it. The proof I turned in concluded with "lots of arm waving... QED" (which actually got a fair amount of credit since no one solved it).

    Let o(n) denote the Euler totient function. That is, o(n) is the number of integers relatively prime to n that are less than n.

    What is the infimum limit as n approached infinity of o(n)/n ?

    I reasoned that it is 0 because if you take the k = p1*p2*...*pm (where the p's are primes to the first power), then o(k)/k = (p1 - 1)*(p2 - 1)*...*(pm - 1)/(p1*p2*...*pm), which looks somewhat like 1*2*3*4...*(n-1)/(2*3*5*...*n) which clearly goes to 0 as n approaches infinity... though most of the terms are missing, so I am not sure.

    The other thought was products of n*log(n) [roughly the nth prime], though I was unable to get anywhere with this.

    Anyways... an interesting problem... anyone got any ideas on it?
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  2. #2
    Pursuing knowledge confuted's Avatar
    Join Date
    Jun 2002
    Posts
    1,916

    Re: Interesting number theory problem

    Originally posted by Zach L.
    This is an interesting problem I ran into last week. I thought I might post it as I have very little clue about how to actually solve it. The proof I turned in concluded with "lots of arm waving... QED" (which actually got a fair amount of credit since no one solved it).

    Let o(n) denote the Euler totient function. That is, o(n) is the number of integers relatively prime to n that are less than n.

    What is the infimum limit as n approached infinity of o(n)/n ?

    I reasoned that it is 0 because if you take the k = p1*p2*...*pm (where the p's are primes to the first power), then o(k)/k = (p1 - 1)*(p2 - 1)*...*(pm - 1)/(p1*p2*...*pm), which looks somewhat like 1*2*3*4...*(n-1)/(2*3*5*...*n) which clearly goes to 0 as n approaches infinity... though most of the terms are missing, so I am not sure.

    The other thought was products of n*log(n) [roughly the nth prime], though I was unable to get anywhere with this.

    Anyways... an interesting problem... anyone got any ideas on it?
    It certainly looks interesting, and I'd like to be able to give it more of a "go," but I don't know anything about the Euler totient function, sadly. Could you elaborate on it?

    You might also want to post it on artofproblemsolving.com under advanced topics or other problem solving... there are some geniuses there.
    Away.

  3. #3
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    Hmm.. good idea.

    The Euler totient function is this (usually it is phi, but I'm using o).

    o(n) = # of integers < n and relatively prime to n

    o(p^n) for prime p = p^n - p^(n-1)
    For n = 1, this is o(p) = p - 1

    o(a*b) for relatively prime a and b = o(a) * o(b)
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  4. #4
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072

    Re: Interesting number theory problem

    Originally posted by Zach L.

    I reasoned that it is 0 because if you take the k = p1*p2*...*pm (where the p's are primes to the first power), then o(k)/k = (p1 - 1)*(p2 - 1)*...*(pm - 1)/(p1*p2*...*pm), which looks somewhat like 1*2*3*4...*(n-1)/(2*3*5*...*n) which clearly goes to 0 as n approaches infinity... though most of the terms are missing, so I am not sure.
    Your resoning here sounds plausible. What makes you unsure?

    But 'infinity' is hard to work with, OTOH. I'm not sure one can divide infinity into prime numbers like that, it could just as well be one single infinitely large prime number, then the answer would be 1.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  5. #5
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    Alright, the professor presented the solution in class. Its a really cool solution too. My reasoning was along the right track, but far from fully developed.

    Take the product of all primes to the first power: n = p1*p2*p3*... (all of thesw are really limits, of course).

    Now, looking at o(n)/n we have (p1-1)*(p2-2)*.../n.

    To show that lim inf (n->infinity) of o(n)/n, we can show that the above limit is 0. It will be zero if its reciprocal is infinite, of course.

    So now look at the infinite product of all terms of the form: p[i]/(p[i] - 1). This can be rewritten as 1/(1-1/p[i]). Remembering that 1/(1-x) is the value of the infinite sum 1+x+x^2+... for abs(x) < 1 (which is the case for inverses of integers), we end up with an infinite product of all of the power series of the inverse of every prime (an infinite product of infinite sums... gee why did I see that )

    Well, as every power of every prime is in there exactly once, and will be multiplied once with every power of every other prime, etc, this product comes out to 1+1/2+1/3+1/4+1/5+... (the harmonic series) which diverges, so the limit of o(n)/n for the given n is 0, and consequently, so is the infimum as n goes to infinity.

    Anyways... I thought that was kind of cool.
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. rapid random number generation problem
    By Newton in forum C Programming
    Replies: 17
    Last Post: 09-19-2008, 02:08 PM
  2. adding a number to a number
    By bigmac(rexdale) in forum C Programming
    Replies: 11
    Last Post: 10-24-2007, 12:56 PM
  3. strange number problem
    By kkjj in forum C Programming
    Replies: 9
    Last Post: 08-09-2007, 07:30 AM
  4. Number theory problem
    By elad in forum A Brief History of Cprogramming.com
    Replies: 9
    Last Post: 09-02-2004, 10:02 AM
  5. Assingnment problem
    By Jason in forum C Programming
    Replies: 1
    Last Post: 08-31-2001, 01:20 PM