Results 1 to 4 of 4

Math Help - Help finding a clean representation of a peculiar sequence

  1. #1
    Newbie
    Joined
    Jul 2010
    Posts
    1

    Help finding a clean representation of a peculiar sequence

    2, 3, 5, 11, 17, 41, 83, 137, 257, 641, 1097, 2329, 4369, 10537, 17477, 35209, 65537, ...

    I have been unable to find any function, f(n), that gives the nth term in this sequence.
    For those that are curious to know how I came across it:
    Euler's phi(n) function finds how many natural numbers less than n there are that are coprime to n (treating 1 as coprime to every number). If you recursively apply phi() enough times, the number eventually reaches 1. I wrote a function (in the programming sense of the word) that finds the least number of times you must apply phi(n) to get it down to 1, and I plotted the results. The most striking feature of the plot is that the points, while scattered about, seem to follow a logarithm. Specifically, the lower bound of the region in which they reside is \log _3\left(\frac{n}{2}\right)+1. However, I have failed to find an upper bound. That is what the sequence is for: some points on the upper bound are (2,1),(3,2),(5,3),(11,4),(17,5),...
    So you see, I want a function y=f(x) for the upper bound. Can anyone help me? Notice that they are not all prime, and the Euler phi of every 4th term, beginning with the first, is a power of 2. If you can solve this, you will have my eternal thanks.

    (Interestingly, if you take the sum: \frac{1}{2}-\frac{1}{3}+\frac{1}{5}-\frac{1}{11}+\frac{1}{17}-\frac{1}{41}+\frac{1}{83}-\frac{1}{137}+\ldots , it appears to approach \frac{1}{\pi }, but finding more terms in the sequence is currently an inefficient process, so I cannot test this hypothesis any further.)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by quasi View Post
    2, 3, 5, 11, 17, 41, 83, 137, 257, 641, 1097, 2329, 4369, 10537, 17477, 35209, 65537, ...

    I have been unable to find any function, f(n), that gives the nth term in this sequence.
    For those that are curious to know how I came across it:
    Euler's phi(n) function finds how many natural numbers less than n there are that are coprime to n (treating 1 as coprime to every number). If you recursively apply phi() enough times, the number eventually reaches 1. I wrote a function (in the programming sense of the word) that finds the least number of times you must apply phi(n) to get it down to 1, and I plotted the results. The most striking feature of the plot is that the points, while scattered about, seem to follow a logarithm. Specifically, the lower bound of the region in which they reside is \log _3\left(\frac{n}{2}\right)+1. However, I have failed to find an upper bound. That is what the sequence is for: some points on the upper bound are (2,1),(3,2),(5,3),(11,4),(17,5),...
    So you see, I want a function y=f(x) for the upper bound. Can anyone help me? Notice that they are not all prime, and the Euler phi of every 4th term, beginning with the first, is a power of 2. If you can solve this, you will have my eternal thanks.

    (Interestingly, if you take the sum: \frac{1}{2}-\frac{1}{3}+\frac{1}{5}-\frac{1}{11}+\frac{1}{17}-\frac{1}{41}+\frac{1}{83}-\frac{1}{137}+\ldots , it appears to approach \frac{1}{\pi }, but finding more terms in the sequence is currently an inefficient process, so I cannot test this hypothesis any further.)
    Interesting.. There's some info here, I don't know all the details, but there is a list up to the 1002nd term!

    A007755
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Hello,
    it's probably not going to be a nice simple polynomial function that everyone loves looking at. If it has to be represented by something, it surely is going to involve recursive series or variable exponents, but my best bet is that no "clean" (univariate elementary algebra´c) function can possibly represent this sequence.

    I say this because you tell us this sequence is somewhat related to Euler's Totient function which itself is inherently related to prime numbers which mathematicians fail to understand properly and have enormous difficulties dealing with (twin primes anyone ?). Thus it seems probable that this sequence is, alas, intractable. But why not ? I'll have a look at it. Here is one first observation : every term of the sequence is either prime, either the product of some previous terms (but these terms seem randomly chosen)

    Remember Erd÷s : "A baby could ask questions in number theory that grown adults can't answer".

    However, the sum result is interesting, this would mean there is some kind of link between prime numbers and pi.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    And also, if you just want an upper bound on how many times Phi can be iterated on a number n before reaching one, the strict upper bound is \log_2{(n)} since in the worst case ( n being a power of two), the number gets halved at each iteration. Unless I haven't understood what you mean by iterating the Totient function.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: May 29th 2011, 12:49 AM
  2. Replies: 2
    Last Post: November 17th 2010, 09:30 AM
  3. finding the series representation
    Posted in the Calculus Forum
    Replies: 4
    Last Post: May 3rd 2010, 05:48 AM
  4. a peculiar ODE
    Posted in the Differential Equations Forum
    Replies: 2
    Last Post: January 1st 2010, 07:34 PM
  5. Replies: 5
    Last Post: November 12th 2009, 11:17 AM

Search Tags


/mathhelpforum @mathhelpforum