mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)

 Dougy 2006-02-22 08:01

Busted functions

[B]Definition[/B]: Let $$f: \mathbb{R} \rightarrow \mathbb{R}$$ be a function. Then if, for all $$m \in \mathbb{N}$$, one of the following is true:
(i) $$f^n(m)$$ is not prime for some $$n \in \mathbb{N}$$. (where $$f^1(m)=f(m)$$ and $$f^n(m)=f(f^{n-1}(m))$$, i.e. function composition)
(ii) $$f^i(m)=f^j(m)$$ for distinct $$i,j \in \mathbb{N}$$.
then $$f$$ is called a [I]busted[/I] function.

Some functions are easily busted. E.g. $$f(x)=a$$ for some $$a \in \mathbb{N}$$, or $$f(x)=x$$. While some functions are not bustible. E.g. Any function satisfying $$f(p_n)=p_{n+1}$$, where $$p_i$$ is the $$i^{th}$$ prime.

[B]Question[/B]: What functions are busted?

The motivation behind this conjecture is to disprove anyone who claims something like "if $$x_1$$ is a prime, and $$x_n := f(x_{n-1})$$, then $$(x_n)$$ is a sequence of primes". A function becomes 'busted' when it stops producing new primes.

Has this been done before? Can anyone easily bust some functions?

 Orgasmic Troll 2006-02-22 09:23

[QUOTE=Dougy][B]Definition[/B]: Let $$f: \mathbb{R} \rightarrow \mathbb{R}$$ be a function. Then if, for all $$m \in \mathbb{N}$$, one of the following is true:
(i) $$f^n(m)$$ is not prime for some $$n \in \mathbb{N}$$. (where $$f^1(m)=f(m)$$ and $$f^n(m)=f(f^{n-1}(m))$$, i.e. function composition)
(ii) $$f^i(m)=f^j(m)$$ for distinct $$i,j \in \mathbb{N}$$.
then $$f$$ is called a [I]busted[/I] function.

Some functions are easily busted. E.g. $$f(x)=a$$ for some $$a \in \mathbb{N}$$, or $$f(x)=x$$. While some functions are not bustible. E.g. Any function satisfying $$f(p_n)=p_{n+1}$$, where $$p_i$$ is the $$i^{th}$$ prime.

[B]Question[/B]: What functions are busted?

The motivation behind this conjecture is to disprove anyone who claims something like "if $$x_1$$ is a prime, and $$x_n := f(x_{n-1})$$, then $$(x_n)$$ is a sequence of primes". A function becomes 'busted' when it stops producing new primes.

Has this been done before? Can anyone easily bust some functions?[/QUOTE]

condition II can be rewritten as $$f^i(m)=m$$ for some i

are you sure you mean that $$f: \mathbb{R} \rightarrow \mathbb{R}$$? if I have $$f(x) = ax + \pi, a \in \mathbb{N}$$ then that's a busted function.

what does bustible mean? Either a function is busted or it is not, bustible sounds like we can do something to the function to make sure it is busted.

 Dougy 2006-02-22 12:09

[QUOTE=TravisT]condition II can be rewritten as $$f^i(m)=m$$ for some i
[/QUOTE]

I thought of this, however consider, for example, a function that satisfies $$f(2)=5, f(5)=7, f(7)=5$$. Then if $$m=2$$, $$f^n(m)=5,7,5,7,5,7,...$$ for $$n=1,2,3,...$$. Informally, a loop might occur, but it might not loop right back to the beginning.

[QUOTE=TravisT]are you sure you mean that $$f: \mathbb{R} \rightarrow \mathbb{R}$$? if I have $$f(x) = ax + \pi, a \in \mathbb{N}$$ then that's a busted function.[/QUOTE]

I certainly do mean $$f: \mathbb{R} \rightarrow \mathbb{R}$$. The other possibility $$f: \mathbb{N} \rightarrow \mathbb{N}$$ would not include all of the relevant functions, for example, $$f(x)=\frac{3}{2}x+\frac{1}{2}$$, if $$m=3$$ then $$f^n(m)$$ will still always be a natural number.

Your example is a busted function, however a rather trivial one. It would perhaps be possible to define $$f: \mathbb{N} \rightarrow \mathbb{R}$$, but then $$f(f(x))$$ is not well defined. Basically the functions of any real interest are smooth functions, like polynomials, exponentations, etc..

[QUOTE=TravisT]
what does bustible mean? Either a function is busted or it is not, bustible sounds like we can do something to the function to make sure it is busted.[/QUOTE]

Yes I shouldn't have used the term 'bustible'. This is a human word which I used to mean "it is possible to prove that this function is busted." In fact lets make it a definition.

[B]Definition[/B]: Let $$f: \mathbb{R} \rightarrow \mathbb{R}$$ be a function. Then if there exists a proof that $$f$$ is busted, we say $$f$$ is [I]bustible[/I].

 Dougy 2006-02-22 12:50

[QUOTE=Dougy]...for example, $$f(x)=\frac{3}{2}x+\frac{1}{2}$$, if $$m=3$$ then $$f^n(m)$$ will still always be a natural number.
[/QUOTE]

After I posted it I noticed that this was incorrect. So I'll give another example of a function $$f$$ which would not be included if $$f:\mathbb{N} \rightarrow \mathbb{N}$$. Eg. $$f(x)=2^{x-2}+1$$ has the property that $$f(1)$$ is not a natural number, while $$f(x) \in \mathbb{N}$$ when $$x \in \mathbb{N}$$ and $$x>1$$.

It is possible to create a related function $$g:\mathbb{N} \rightarrow \mathbb{N}$$ such that $$g(x)=f(x)$$ whenever $$f(x) \in \mathbb{N}$$, and $$g(x)=1$$ whenever $$f(x)$$ is not a natural number. But then this would be asking a different question.

 Orgasmic Troll 2006-02-22 20:59

Oops. I think mine implies yours, but not the converse

 All times are UTC. The time now is 03:08.