Number Theory Number Theory Math Forum

August 15th, 2017, 06:26 PM   #21
Senior Member

Joined: May 2016
From: USA

Posts: 1,310
Thanks: 552

Quote:
 Originally Posted by Micrm@ss Then what would be a useful function? What do we define by a useful, efficient function? Without such an answer, this thread is pretty much meaningless.
The original question is meaningless because the terms are not carefully defined.

Perhaps the question is whether the distribution of primes is close to random in some statistical sense, but what sense is not specified nor is "close enough."

Some interpreted the question to mean whether there was a deterministic way to determine whether a number is prime, and of course there is. In the sense that if it impossible to determine whether a given number is prime, primality is random, no one asserts that primes are random so the original question is absurd.

I thought that the question made sense if it was asking whether a closed form formula to determine what the nth prime was in ascending order. If such a form exists, then primality is not "random." I have now been told both that such a formula has been found and that such a formula has not been found. Which of those answers is correct strikes me as an unambiguous question and certainly not meaningless although whether it is interesting is a matter of subjective taste. August 15th, 2017, 08:39 PM #22 Banned Camp   Joined: Dec 2012 Posts: 1,028 Thanks: 24 The worrd "random" was used several time in Sautoy books. It stinks me lot, and push me to start my own investigation on them, finally finding the 3 algos to have back a prime: $z=n!/n^2$ Than the correct number of primes within a certain $x$ (starting from 5 because for $4$ the previous formula gives a false value), $$Pi(x) = \left( \sum_{n = 5}^{\ P} (\lfloor(n!/n^2)\rfloor-\lfloor(n!/n^2)\rfloor)+1/3 \right) +2$$ and the next prime. I already posted them several years ago here, but someone argue that they are just algos, not clean formulas or functions etc. etc... But now I discover that applying a certain function on the Primes (only) produce a very similar output than if we apply it on the Integers, and this, I think, will confirm that they cannot be randomly placed since if so a similar distribution will be a very improbable (just to be carefull) case. And since this pattern is respected with various exponents of such function it confirm our suspect. But from here to write a theorem, than a math proof is another story.... August 16th, 2017, 04:26 AM #23 Global Moderator   Joined: Dec 2006 Posts: 21,124 Thanks: 2332 It's hard to prove something that neither makes sense nor works at all. August 16th, 2017, 05:13 AM   #24
Banned Camp

Joined: Dec 2012

Posts: 1,028
Thanks: 24

Quote:
 Originally Posted by skipjack It's hard to prove something that neither makes sense
To what ?

Quote:
 Originally Posted by skipjack nor works at all.
Why ?

The trick is this:

Wrote Integers from n,m=1 to n,m=1000 as Complicate Number $M_2$, and as Complicate Number $M_3$:

$n= (\lfloor(n^{1/2})\rfloor)^2+(n- (\lfloor(n^{1/2})\rfloor)^2)$ ; $m= (\lfloor(m^{1/3})\rfloor)^3+(m- (\lfloor(m^{1/3})\rfloor)^3)$

where

$Rest_{2,n}=(n- (\lfloor(n^{1/2})\rfloor)^2)$

$Rest_{3,m}=(m- (\lfloor(m^{1/3})\rfloor)^3)$

So you have:

$1= 1^2+0$ ; $1= 1^3+0$
...

$1000= 31^2+39$ ; $1000= 10^3+0$

Than Sum:

$MagicSum=Rest_{2,n}+ Rest_{3,m}$

and plot $n, MagicSum$

Now do the same using $n,m=1,2,3,5,7,11,13,17...... \pi_{1000}$

Put on a graph and jump on the chair...

Ciao
Stefano

Last edited by complicatemodulus; August 16th, 2017 at 05:18 AM. August 16th, 2017, 08:08 AM #25 Senior Member   Joined: Apr 2014 From: Glasgow Posts: 2,166 Thanks: 738 Math Focus: Physics, mathematical modelling, numerical and computational solutions Wow! If there really is a formula, that's AMAZING That means that the evaluation of the nth prime is actually a P-problem... the dream of proving if $\displaystyle P = NP$ is a bit closer! It's a pity that there's a "mod" in there that makes it computationally inefficient. If it were computationally efficient, then existing encryption algorithms based on large prime numbers would become obsolete. Last edited by Benit13; August 16th, 2017 at 08:18 AM. August 16th, 2017, 08:24 AM   #26
Senior Member

Joined: Aug 2017
From: United Kingdom

Posts: 313
Thanks: 112

Math Focus: Number Theory, Algebraic Geometry
Quote:
 Originally Posted by Benit13 Okay, sure. My jargon is not on point. What I meant to say was that there is no formula known (at this time) that evaluates what some arbitrary prime number is in the sequence of primes. For example, I cannot just put n = 2348 into some formula and get out the 2348th prime number. Existing computer implementations that provide that ability don't use a formula, they use look-up tables of previously calculated values, which are calculated based on NP algorithms (one example is Eratosthenes' sieve). The relevance of whether something is deterministic or not is that the OP asked a question about the whether the distribution of primes is "random". I was attempting to clarify that although the distribution of primes isn't "random", the primes are not evaluated using some sort of straightforward deterministic function and their evaluation is instead made through NP-algorithms.
Ah, fair enough. Out of interest, what do you mean by a "deterministic function", and (in the context of this discussion, at least) what is the significance of them compared to an NP algorithm? August 16th, 2017, 08:30 AM   #27
Senior Member

Joined: Apr 2014
From: Glasgow

Posts: 2,166
Thanks: 738

Math Focus: Physics, mathematical modelling, numerical and computational solutions
Quote:
 Originally Posted by Maschke If you give me n, I can deterministically obtain f(n) via the sieve of Eratosthenes. It's deterministic. Someone complained that it's not efficiently computable. That's irrelevant. It's computable. Give me n and I'll give you f(n) via a deterministic algorithm that halts in a finite number of steps.
I thought that the sieve of Eratosthenes was NP, but then I read this:

https://en.wikipedia.org/wiki/Primality_test

Interesting stuff! August 16th, 2017, 08:48 AM   #28
Senior Member

Joined: Apr 2014
From: Glasgow

Posts: 2,166
Thanks: 738

Math Focus: Physics, mathematical modelling, numerical and computational solutions
Quote:
 Originally Posted by cjem Ah, fair enough. Out of interest, what do you mean by a "deterministic function", and (in the context of this discussion, at least) what is the significance of them compared to an NP algorithm?
Haha, I decided to edit my post because it was rubbish! I'm amazed that the primes can now be evaluated in a straightforward manner without knowing previous primes in the sequence.

By using "deterministic" I was referring to P-problems in complexity theory. P-problems are solved by algorithms that take some set of input parameters, perform a known set of finite operations on them and then obtain a set of output parameters without doing any guesswork. A computer algorithm that implements the solutions to P-problems has no steps that perform "if" conditions of any kind. Consequently, it should be possible to determine precisely how many steps the algorithm is going to perform without actually performing any of the steps.

NP-problems are non-deterministic in that the number of steps is unknown, even for a specific scenario under investigation (it doesn't mean that it can't be estimated or that the number of steps is unconstrained... just that the actual number of steps is unknown until the algorithm is actually initiated). They usually require some form of estimation or guesswork followed by conditions that determine improvements. Classic examples of NP-problems are the bucket-filling problem and travelling Salesman problem. All (afaik...) numerical methods for approximating solutions based on some form of convergence criterion are NP problems. Techniques for solving optimization problems can also be in NP (e.g. the genetic algorithm), but not all of them (e.g. differentiating a quadratic and setting it to zero to get a stationary point is in P).

Basic algorithms that implement the sieve of Eratosthenes are NP algorithms because the number of steps made is known only when you actually perform the algorithm... it requires constructing the sequence of primes by iterating over all numbers less than the target number and then deciding whether that number should be in the sequence or not by testing for primality which, if iterating over a set of divisors, is an NP-problem.

However... there are tests for primality in P and algorithms now exist for evaluating the primes which is in P... that's amazing!

Last edited by Benit13; August 16th, 2017 at 09:24 AM. August 16th, 2017, 11:53 PM #29 Banned Camp   Joined: Dec 2012 Posts: 1,028 Thanks: 24 Here the interesting fact: If primes was "randomly" placed the Magic Sum will have an high probablility to have a fully different behaviour respect to the complete distribution of all the Integers. Here the Magic Sum for All the Integers (1 to 1000) Here the Magic Sum for PRIMES JUST (1 to $\pi_{1000}$) The reason can be that, as we know, the distribution of the Primes is "Quasi" Smooth Rising distribution, but the Math truth is the unknown very deep point to be investigated. (of course some easy concerning on the Class of the Rest can be done, pls see yellow ones) MORE: Forgotting the Primes If for example you'll plot R2-R4 (for all Intgers), so the Magic Sum for Square and Fourth power (^4), or (R2-R6) (for all Intgers), you'll see that the distribution is more "Regular". When some post ago I talk of "Turbolence", or Interferences in Physics, I'm referring to this Math phenomenon. We all imagine Physics phenomenon are consequances of continous variables, but in case of a scalar variable (and I suspect are ALL scalar), we have to take count of this effect. So while is very easy to predict smooth waves summations, it is not soo easy to predict all the effects of this kind of scalar summation. One example is the electron's jump: till it do not receive/loose enough energy it continue to lay on the same orbit (so in the example associated with an Integer Root value), but continuing to push/suck energy, the Delta Energy is accumulated in another "inthernal" variable, here represented as the Rest. When the Rest, or the Sum of the Rests Rise to an high enough level, the Two Hand Clock take the Rest to Zero, and the Integer Hand make one step (foreward / backward). It happens elsewhere in the universe.... Little O.T. but I think very very interesting.... I hope... Ciao Stefano Last edited by complicatemodulus; August 16th, 2017 at 11:57 PM. August 17th, 2017, 02:13 AM #30 Banned Camp   Joined: Dec 2012 Posts: 1,028 Thanks: 24 Edit: Sorry here some corrections to the formula to start the counting from n=1: The Number of Primes $Pi(x)$ within a certain $P$: $$Pi(x) = \left( \sum_{n = 1}^{\ P} \lfloor([((n-1)!/n)-\lfloor((n-1)!/n)\rfloor)+1/3] \rfloor \right)$$ Asap the ones to the one to computate the next prime. Last edited by complicatemodulus; August 17th, 2017 at 02:52 AM. Tags primes, proof, random Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post Bromster Algebra 0 December 24th, 2015 11:09 PM skynet Probability and Statistics 1 June 18th, 2014 01:26 PM SedaKhold Calculus 0 February 13th, 2012 12:45 PM brunojo Number Theory 70 June 15th, 2009 05:37 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top      