mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   Busted functions (https://www.mersenneforum.org/showthread.php?t=5523)

Dougy 2006-02-22 08:01

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

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

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

The motivation behind this conjecture is to disprove anyone who claims something like "if [tex]x_1[/tex] is a prime, and [tex]x_n := f(x_{n-1})[/tex], then [tex](x_n)[/tex] 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 [tex]f: \mathbb{R} \rightarrow \mathbb{R}[/tex] be a function. Then if, for all [tex]m \in \mathbb{N}[/tex], one of the following is true:
(i) [tex]f^n(m)[/tex] is not prime for some [tex]n \in \mathbb{N}[/tex]. (where [tex]f^1(m)=f(m)[/tex] and [tex]f^n(m)=f(f^{n-1}(m))[/tex], i.e. function composition)
(ii) [tex]f^i(m)=f^j(m)[/tex] for distinct [tex]i,j \in \mathbb{N}[/tex].
then [tex]f[/tex] is called a [I]busted[/I] function.

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

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

The motivation behind this conjecture is to disprove anyone who claims something like "if [tex]x_1[/tex] is a prime, and [tex]x_n := f(x_{n-1})[/tex], then [tex](x_n)[/tex] 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 [tex]f^i(m)=m[/tex] for some i

are you sure you mean that [tex]f: \mathbb{R} \rightarrow \mathbb{R}[/tex]? if I have [tex]f(x) = ax + \pi, a \in \mathbb{N}[/tex] 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

Thanks for your response.

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

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

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

I certainly do mean [tex]f: \mathbb{R} \rightarrow \mathbb{R}[/tex]. The other possibility [tex]f: \mathbb{N} \rightarrow \mathbb{N}[/tex] would not include all of the relevant functions, for example, [tex]f(x)=\frac{3}{2}x+\frac{1}{2}[/tex], if [tex]m=3[/tex] then [tex]f^n(m)[/tex] 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 [tex]f: \mathbb{N} \rightarrow \mathbb{R}[/tex], but then [tex]f(f(x))[/tex] 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 [tex]f: \mathbb{R} \rightarrow \mathbb{R}[/tex] be a function. Then if there exists a proof that [tex]f[/tex] is busted, we say [tex]f[/tex] is [I]bustible[/I].

Dougy 2006-02-22 12:50

[QUOTE=Dougy]...for example, [tex]f(x)=\frac{3}{2}x+\frac{1}{2}[/tex], if [tex]m=3[/tex] then [tex]f^n(m)[/tex] 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 [tex]f[/tex] which would not be included if [tex]f:\mathbb{N} \rightarrow \mathbb{N}[/tex]. Eg. [tex]f(x)=2^{x-2}+1[/tex] has the property that [tex]f(1)[/tex] is not a natural number, while [tex]f(x) \in \mathbb{N}[/tex] when [tex]x \in \mathbb{N}[/tex] and [tex]x>1[/tex].

It is possible to create a related function [tex]g:\mathbb{N} \rightarrow \mathbb{N}[/tex] such that [tex]g(x)=f(x)[/tex] whenever [tex]f(x) \in \mathbb{N}[/tex], and [tex]g(x)=1[/tex] whenever [tex]f(x)[/tex] 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.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.