Thread: 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 . 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: , it appears to approach , but finding more terms in the sequence is currently an inefficient process, so I cannot test this hypothesis any further.)

Originally Posted by quasi

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 . 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: , it appears to approach , 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

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.

And also, if you just want an upper bound on how many times Phi can be iterated on a number before reaching one, the strict upper bound is since in the worst case ( 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.