My Math Forum Tricky way to generate huge list of prime numbers

 Number Theory Number Theory Math Forum

 September 24th, 2015, 07:45 AM #1 Senior Member   Joined: Dec 2013 Posts: 1,101 Thanks: 40 Tricky way to generate huge list of prime numbers Let us concatenate a list of the first primes: 235711131719....... and so on At some point if we stop the list the 10.000th prime we will have a number: A=235711131719.......(10.000th prime). Now assume that we find a function of some form or a particular sequence sequence up to A we could then generate all the first 10.000 primes. The mathematical problem involved is: how to build a function such as using minimal data we could rebuild any huge number (I'm talking about the digits)? We do not know, for example, if 2^k with very large k will produce some known sequence concatenated. Just a little example: 235711131719 could be the sum of sequence U(n) where n is 3 digit number or less. I'm thinking to a general solution to build such sequences or functions or polynom etc... Last edited by skipjack; September 24th, 2015 at 08:58 AM.
 September 24th, 2015, 10:12 AM #2 Senior Member   Joined: Dec 2007 Posts: 687 Thanks: 47 There are some formulas to generate only prime numbers, but a closed form formula, at least some polynomial, does not give it if I'm not mistaken. Charles knows all of this. Suppose you got a function $conc(\vec x)$ whose domain and image are subsets of $\mathbb{P}$ (cute notation for the set of primes). Lets not even think about the form of the function, lets say just that it is a set of recipes. What are the ingredients? Only prime numbers, and the "cake" is a new prime number. First you need to prove that there are infinitely many prime numbers which are concatenations of prime numbers: if that's false the whole thing does not work. Second, if you happily prove it, then you are in no way with some predictive function, maybe yes, most probably not, since your ingredients are occurring in a random fashion. I'd test the first hypothesis, although it seems very hard, as hard as any other "easy-to-state-very-hard-to-prove" prime numbers' conjectures. Thanks from mobel
September 24th, 2015, 11:11 AM   #3
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 933

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
 Originally Posted by al-mahed There are some formulas to generate only prime numbers, but a closed form formula, at least some polynomial, does not give it if I'm not mistaken. Charles knows all of this.
Yep. There are plenty of formulas for generating prime numbers, maybe a dozen of which are well-known. Polynomials can't generate only primes unless they are constant. But you can have (polynomial) Diophantine equations which are positive only on the primes.

As to prime concatenation of primes, see
https://oeis.org/A046284

 September 24th, 2015, 03:13 PM #4 Senior Member   Joined: Dec 2013 Posts: 1,101 Thanks: 40 I was misunderstood. I`m trying to find a polynom generating a list of primes. No. I want to a polynomial P(x) equal to the concatenation of prime numbers as number. P(x)=235711......................(kth prime) for some value of x It is a tricky way not something we could predict with. It is like a compression process. Instead of storing them all I store of P(x) with few data. If the data stored are of the same size of 23511....etc... then there is no need for such P(x). It could a sum of factorial combined to powers etc... 235=2^8 - 21 is unuseful because it is better to store the number concatenated itself. As the grow larger maybe there is a function or polynomial or anything which we could compute to retrieve all the list as number.
 September 24th, 2015, 05:57 PM #5 Senior Member   Joined: Jan 2014 From: The backwoods of Northern Ontario Posts: 371 Thanks: 68 Well, if I wanted to generate primes, I would multiply together the first n primes and add 1. Example: 2×3×5×7 +1 which is the prime number 211.
September 25th, 2015, 11:17 AM   #6
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 933

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
 Originally Posted by mobel I want to a polynomial P(x) equal to the concatenation of prime numbers as number.
The only polynomials that always give concatenations of primes are constant, like P(x) = 23571113.

September 25th, 2015, 08:19 PM   #7
Senior Member

Joined: Dec 2007

Posts: 687
Thanks: 47

Quote:
 Originally Posted by CRGreathouse The only polynomials that always give concatenations of primes are constant, like P(x) = 23571113.
The proof is really simple: suppose $f(x)$ is an univariate polynomial giving only primes, in particular let $f(a)=p$ for $p$ a prime. Then $f(kp+a)\equiv p\pmod p$ but $f(kp+a)\not=f(a)$, this means that $f(kp+a)$ is composite.

 September 25th, 2015, 08:54 PM #8 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 933 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms That's for "not all prime"; the proof for "not all concatenations of primes 2..p" is different.
September 25th, 2015, 09:38 PM   #9
Senior Member

Joined: Dec 2007

Posts: 687
Thanks: 47

Quote:
 Originally Posted by CRGreathouse That's for "not all prime"; the proof for "not all concatenations of primes 2..p" is different.
Well, that's valid for any univariate polynomial, so polynomials giving what he wants are not possible. I think you are saying that we also cannot define a recursive function taking integer values giving only primes? In that case I have no idea how to prove it.

September 26th, 2015, 05:54 AM   #10
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 933

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
 Originally Posted by al-mahed I think you are saying that we also cannot define a recursive function taking integer values giving only primes?
No, I'm saying that no nonconstant univariate polynomial gives only numbers 2, 23, 235, 2357, 235711, 23571113, etc.

 Tags generate, huge, list, numbers, prime, tricky

### list of all pm in tricky way

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post vuacobac Algebra 4 January 10th, 2014 12:56 AM ganeshsrivatsav Number Theory 2 November 15th, 2013 08:43 PM Axel Calculus 3 June 4th, 2011 07:14 PM Quantum++ Computer Science 2 December 25th, 2010 07:37 AM jsmith1994 Advanced Statistics 1 March 2nd, 2010 07:44 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top