Is it possible to find function that describes irrational things?

[epkid08]

i.e. decimals of an irrational number, pi(n), etc.

The function itself, f(n), can change with n, as long as it changes in a patterned way.

This seems like a straight foreword question, either you can for all, or you can't for all. A simple example of a changing function would be the Fibonacci sequence.

Also, do you think that a function such as this(one that describes an irrational thing), could have to do with a floor, ceiling, or some type of rounding, function?

 

[HallsofIvy]

Perhaps you need to give more detail about what you want.

"f(n)= the n^th decimal place of $\pi$" is a perfectly good function that gives "decimals of an irrational number".

 

[epkid08]

Perhaps you need to give more detail about what you want.

"f(n)= the n^th decimal place of $\pi$" is a perfectly good function that gives "decimals of an irrational number".

Can you define f(n) using n and/or $$\pi$$ in such a way where the change in f(n) is considered patterned?

Edit: Basically what I'm asking is, is it possible to make prime a counting function, where (if $$\pi_k(n)$$ changes with $$n_k$$) $$\pi_k(n)$$ is patterned.

 

[Hurkyl]

It's really not clear what you're asking for. But I can answer one specific thing: there are straightforward formulas for the n-th decimal digit of a real number, such as

$$\left\lfloor 10^{-n} x - 10 \left\lfloor 10^{-n-1} x \right\rfloor<br /> \right\rfloor.$$

 

[epkid08]

It's really not clear what you're asking for. But I can answer one specific thing: there are straightforward formulas for the n-th decimal digit of a real number, such as

$$\left\lfloor 10^{-n} x - 10 \left\lfloor 10^{-n-1} x \right\rfloor<br /> \right\rfloor.$$

Here is my question the simplest way I can put it:

Is there a way to define $$\pi(n)$$(prime counting function), for all n?

 

[CRGreathouse]

Is there a way to define $$\pi(n)$$(prime counting function), for all n?

"$\pi(n)$ is the number of primes less than or equal to n."

Are you asking if there is a closed-form expression for this? In that case, the answer is still yes; MathWorld and Wikipedia both have pages on this (something like 'prime formulas').

 

[epkid08]

It is known that no non-constant polynomial function P(n) exists that evaluates to a prime number for all integers n. The proof is simple: Suppose such a polynomial existed. Then P(1) would evaluate to a prime p, so P(1) \equiv 0 \pmod p. But for any k, P(1+kp) \equiv 0 \pmod p also, so P(1 + kp) cannot also be prime (as it would be divisible by p) unless it were p itself, but the only way P(1 + kp) = P(1) for all k is if the polynomial function is constant.

I got this from wikipedia. This is sort of the question I was asking. I wondering whether a P(n) function exists for all n. It clearly states no, which is what thought for a non-constant polynomial function, but what about a function that constantly changes to a pattern? A poor example:

$$P_1=\sum^n_{k=0}(n_{n-k})*((2n-1)+P_{n-1})mod(\lfloor tan^n(\frac{2\pi}{2\pi+n})\rfloor)$$

$$P_2=\sum^n_{k=0}(n_{n-k})*((2n-1)+P_{n-1})mod(\lfloor tan^n(\frac{2\pi}{2\pi+n})\rfloor) + \lfloor \prod^{P_{n-1}}_{k=n}(ln(k))\rfloor$$

$$P_3=\sum^n_{k=0}(n_{n-k})*((2n-1)+P_{n-1})mod(\lfloor tan^n(\frac{2\pi}{2\pi+n})\rfloor) + \lfloor \prod^{P_{n-1}}_{k=n}(ln(k))\rfloor - \lfloor \prod^{P_{n-2}}_{k=n}(ln(k))\rfloor$$

This function probably makes no sense at all, it was just an example.

 

[CRGreathouse]

I got this from wikipedia. This is sort of the question I was asking. I wondering whether a P(n) function exists for all n. It clearly states no, which is what thought for a non-constant polynomial function, but what about a function that constantly changes to a pattern?

Such functions certainly exist, they're just not polynomials (unless they're constant). An example would be the function P_n, which sends a positive integer n to the nth prime.

 

[CRGreathouse]

Here, I sense a communication problem. When you say "function", I think you mean to say "closed-form expression". Is that right?

 

[Alex6200]

The integral of 4/(1+t^2) with respect to T from 0 to X describes pi if X = 1.

$$\pi\ = \int_{0}^1\frac{4}{1 + t^2} dt$$

 

[epkid08]

The integral of 4/(1+t^2) with respect to T from 0 to X describes pi if X = 1.

$$\pi\ = \int_{0}^1\frac{4}{1 + t^2} dt$$

This is only true if you setup a constraint i.e. if x=1.

Here's a question, can an expression of any kind, describe the change from any prime to the next prime?

 

[n_bourbaki]

You have so many undefined terms it is impossible to know where to begin.

What does 'the change from prime to prime' even mean? As has been pointed out before, functions can be defined that describe *anything*, the only question is whether that function has a 'nice' form, or can be calculated quickly. But you'd need to define what you consider 'nice' and 'quickly' to mean.

 

[epkid08]

I think this is what I was looking for:
$$p_n = 1 + \sum_{m=1}^{2^n} \left\lfloor \left\lfloor { n \over 1 + \(\sum_{j=2}^m \left\lfloor {(j-1)! + 1 \over j} - \left\lfloor{(j-1)! \over j}\right\rfloor \right\rfloor) } \right\rfloor^{1 \over n} \right\rfloor$$

An expression in the form $$P_n=f(N_p)$$, where everything is defined.

 

[Alex6200]

This is only true if you setup a constraint i.e. if x=1.

Well, yes. But that IS a function that describes an irrational number in a non-circular fashion (i.e, a function f(x) = $$\pi\ =\ 3.14159265358979323$$ would be circular)

Here's a question, can an expression of any kind, describe the change from any prime to the next prime?

Ummm... I don't think so. I mean there are obviously functions that one could write that could do that. But since that would involve using if-then statements I don't know if it would qualify as an expression.

 

[CRGreathouse]

Here's a question, can an expression of any kind, describe the change from any prime to the next prime?

Of course. One expression would be "the difference between the (n+1)th prime and the nth prime". Another would be $p_{n+1}-p_n.$ Another, using your expression above, would be

$$\sum_{m=1}^{2^{n+1}} \left\lfloor \left\lfloor { {n+1} \over 1 + \(\sum_{j=2}^m \left\lfloor {(j-1)! + 1 \over j} - \left\lfloor{(j-1)! \over j}\right\rfloor \right\rfloor) } \right\rfloor^{1 \over {n+1}} \right\rfloor - \sum_{m=1}^{2^n} \left\lfloor \left\lfloor { n \over 1 + \(\sum_{j=2}^m \left\lfloor {(j-1)! + 1 \over j} - \left\lfloor{(j-1)! \over j}\right\rfloor \right\rfloor) } \right\rfloor^{1 \over n} \right\rfloor$$

 

[CRGreathouse]

Let's standardize our terminology here:

• Expression: any well-formed mathematical statement. Examples: x = y, y + 3, "the set of numbers one greater than a prime", and any of the below.
• Function: an expression which relates any x from the function's domain to exactly one y from the function's codomain. Examples: the function from the set of people on Earth to the set {Jan 1, Jan 2, Jan 3, ..., Dec 30, Dec 31} defined by f(x) = the birthday of x, or any of the closed-form functions below.
• Closed-form expression: an expression which can be written with a particular subset of the symbols, say {+, -, *, /, ^, %, sum, !, 0, 1, floor, sin} plus function variables. Examples: 7! or any of the closed-form functions below.
• Closed-form function: a closed-form expression which is a function. Examples: f(x) = sin (x), f(n) = $\lfloor\sqrt n\rfloor.$

 

[epkid08]

Let's standardize our terminology here:

• Expression: any well-formed mathematical statement. Examples: x = y, y + 3, "the set of numbers one greater than a prime", and any of the below.
• Function: an expression which relates any x from the function's domain to exactly one y from the function's codomain. Examples: the function from the set of people on Earth to the set {Jan 1, Jan 2, Jan 3, ..., Dec 30, Dec 31} defined by f(x) = the birthday of x, or any of the closed-form functions below.
• Closed-form expression: an expression which can be written with a particular subset of the symbols, say {+, -, *, /, ^, %, sum, !, 0, 1, floor, sin} plus function variables. Examples: 7! or any of the closed-form functions below.
• Closed-form function: a closed-form expression which is a function. Examples: f(x) = sin (x), f(n) = $\lfloor\sqrt n\rfloor.$

I was under the impression that there existed no type of function or expression that took the form of $$P_n=f(N_p)$$. I originally assumed this because 1) I've been told numerous times that there wasn't (probably told that there was no function), and 2) everybody makes a huge deal about the distribution of primes and finding an easy way to find all of the primes, and so I thought there existed no expression.

Here's a final question, why, if we already have an expression in the form, $$P_n=f(N_p)$$, are people still searching for high prime numbers?

$$p_n = 1 + \sum_{m=1}^{2^n} \left\lfloor \left\lfloor { n \over 1 + \(\sum_{j=2}^m \left\lfloor {(j-1)! + 1 \over j} - \left\lfloor{(j-1)! \over j}\right\rfloor \right\rfloor } \right\rfloor^{1 \over n} \right\rfloor$$

Isn't this expression good enough to find any/all of the primes?

 

[CRGreathouse]

I was under the impression that there existed no type of function or expression that took the form of $$P_n=f(N_p)$$. I originally assumed this because 1) I've been told numerous times that there wasn't (probably told that there was no function)

The statement "There is no function that maps a positive integer n to the nth prime" is wrong. The statement "There is no closed-form expression that maps a positive integer n to the nth prime" is wrong, assuming closed-form expressions can use addition, subtraction, multiplication, division, exponents, factorials, indexed sums, and the floor function.

I'm not being condescending at all with the following statement:
Anyone who says that there is no formula for the primes doesn't know what they're talking about. There is no sensible interpretation under which that is true.

everybody makes a huge deal about the distribution of primes and finding an easy way to find all of the primes, and so I thought there existed no expression.

Yes, the formula I posted takes something like 2 * 4ⁿ factorial calculations, which takes a really long time for n greater than, say, 50. But calculating the difference between the 101st prime and the 100th prime, 547 - 541 = 6, is very easy. So improving on this closed-form expression with efficient algorithms is important.

Here's a final question, why, if we already have an expression in the form, $$P_n=f(N_p)$$, are people still searching for high prime numbers?

Using the formula from post #13 to calculate that p_10 = 29 would take 1024 steps through the main loop. Each pass through the main loop runs the inner loop up to 1023 times. Each pass through the inner loop requires the calculation of two factorials, which may be as large as 1023! > 10²³³⁶. In total, over a million factorials are computed, most of which are huge.

But you can instead check each number from 1 to 30 for divisibility by 2, 3, and 5 to determine that 29 is the 10th prime.

This method, millions of times faster than the formula from post #13, is called "trial division" and is considered too slow to test the primality of any but the smallest numbers.

Isn't this expression good enough to find any/all of the primes?

Given enough time that expression will (presumably) find any prime desired. But using a dual-core 1 THz computer, finding the 100th prime with that method would take longer than the life of the universe.

 

[CRGreathouse]

Here's a time comparison for finding the kth prime.

If factorials are calculated directly, the formula from post #13 takes $O(8^{k+\varepsilon})$ multiplications,with yet higher bit complexity.

Trial division takes $O(\sqrt n)$ time for each number, so $O(k\sqrt k)=O(n^{1.5})$ time overall. (Actually it's not quite that bad, since most will exit early.)

APR takes $O((\log n)^{\log\log\log n})$ and AKS takes $O((\log n)^{12}$ for each prime, so the test with either would take $O(k^{1+\varepsilon})$ total steps. (Efficient versions of AKS exist which take substantially less time, but it's not relevant here.)

The real way to do the problem is with the sieve of Eratosthenes, which takes time $O(k\log k\log\log k).$ It might not seem like much of an improvement on the above, but it's far simpler and millions of times faster. (No one would use the above for this purpose; that would be silly.)

The sieve of Atkin, though not as simple as the above, is faster at $O(k/\log\log k).$ This is the first sublinear algorithm for the problem from the list so far.

Meissel's method counts primes up to a given bound. It takes $O(k/(\log k)^3)$ time, and once you have that it takes negligible effort to find the prime needed with a small sieve and binary search.

Mapes' method, an improved way to count primes, takes only $O(k^{0.7})$ and so is the first method on this list that finishes in time o(k).

The Lagarias-Miller-Odlyzko method is the current best, taking $O(k^{2/3}).$

 

[Reedeegi]

yes, there are formulas for many of these functions. Mathworld has a lot of them on their site, as well as many more number theoretic formulae.

 

[CRGreathouse]

Mapes' method, an improved way to count primes, takes only $O(k^{0.7})$ and so is the first method on this list that finishes in time o(k).

That's supposed to be $O(k^{1-\varepsilon})$ for some $\varepsilon,$ by the way.