20201211, 00:38  #1 
"Viliam Furík"
Jul 2018
Martin, Slovakia
2·353 Posts 
Prime representing constant
Inspired by recent Numberphile video (very short, 12 minutes long), I have started programming a Python program that could compute the constant to as many places as possible, in at most 24 hours, which is what I consider a reasonable time frame for the development phase. So far, the longest completed run computed 3 million decimal digits and took roughly 6 hours to complete. The collected time data suggests that if runtime for n digits is x, then runtime for an is xa^{2}. It also seems to be lower than that, by a factor of about 1.1, on average.
My program uses a slight variation of the algorithm used in the video (the infinite sum) > As we know, what is the highest prime we will use, we can end the sum there, and sum up the fractions. Then we can factor out all the way to the beginning, and we get something like this: ( ( ( (21)*2 + (31) )*3 + (51) )*5 + (71) )*7 + (111)... / 2*3*5*7... If you look at the bracket part, you will notice, that for each prime, you add it to the previous result, subtract 1, and then you multiply the whole thing by the prime, and then do the same for the next prime. At each step, you also multiply the denominator by the prime, continuing the primorial. When you are done, you simply divide the fraction into a number with a given number of digits. That should be a lot faster than the original algorithm because you divide only in the end, thus keeping the numbers you work with as integers, until the end. Plus, it opens the possibility of backup files so that when you end, you can continue the computation later. I have also found, that for n decimal digits, the highest prime I need is at least (1+x)*n/log_{10}(e), where x tends to zero as n grows – for n = 25000, x = 0.02 should be sufficient. That results from Chebyshev’s function and some quick mathematics using logarithms. A friend of mine is going to help me convert it into a C program, using hopefully a simple FFT multiplication (current Python program uses Karatsuba multiplication for simplicity). Until then, I will try if using NumPy speeds it up (it should, hopefully), and maybe I will get it to run on CUDA, through the Numba library. My question to Alex Yee is, whether it is worth including in the ycruncher. Another question to anyone, apart from FFT and C, are there any other improvements that can be done? BTW, my program reads the primes from a sieved file containing primes under 1,000,000,000, enough to compute 400,000,000 digits. I found it is faster to read them from a file, rather than sieving them on the start of each run, i.e. the total time it takes it to read them is lower than the time it takes it to sieve them. 
20201211, 00:52  #2  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2×23×137 Posts 
Quote:
But what is your goal here? Just to make it really fast and nothing else? If all the effort is just for a single run then it seems not worthwhile to go to a lot of trouble when you can let the computer do the hard work, albeit a little less efficiently and for longer, instead of you using your time while the computer sits idle. 

20201211, 02:01  #3 
Feb 2017
Nowhere
19·269 Posts 
See also the arxiv submission A PrimeRepresenting Constant. This includes a proof that the constant is irrational.

20201211, 02:05  #4  
"Viliam Furík"
Jul 2018
Martin, Slovakia
2C2_{16} Posts 
Quote:


20201211, 04:24  #5 
Dec 2005
27_{8} Posts 
Have you tried using the gmpy2 library? It provides access to the GMP library for multipleprecision arithmetic. It should be very easy to convert your existing program to use gmpy2.
I maintain gmpy2. If you have any questions, let's start a new thread under Programming. casevh 
20201211, 11:17  #6  
"Viliam Furík"
Jul 2018
Martin, Slovakia
2×353 Posts 
Quote:


20201211, 17:24  #7 
"Daniel Jackson"
May 2011
14285714285714285714
1010100101_{2} Posts 
I hope you release this to the public when it's finished. I would love to try it out.

20201211, 18:29  #8 
"Viliam Furík"
Jul 2018
Martin, Slovakia
2×353 Posts 

20201211, 20:15  #9  
Feb 2017
Nowhere
19·269 Posts 
Quote:
g_{n} < f_{1} < g_{n} + 2/p_{n1}#. Using the Prime Number Theorem, this estimate indicates that, for a given positive integer K, 0 < f_{1}  g_{n} < 10^{K} if p_{n} > K*ln(10), approximately. If this estimate is right, then for 3 million decimal digits' accuracy you need to take primes p up to about 6.9 million. Of course, being able to maintain accuracy to K decimal digits has its own price if K is large. 

20201211, 21:09  #10  
"Viliam Furík"
Jul 2018
Martin, Slovakia
1302_{8} Posts 
Quote:
Quote:
Quote:
Quote:


20201215, 01:02  #11  
"Viliam Furík"
Jul 2018
Martin, Slovakia
1011000010_{2} Posts 
Quote:
Program is fast enough to compute 100,000,000 digits in less than 2 hours, and 1,000,000 in one second. Unfortunately, the runtime scaling of the generating algorithm is quadratic (imperfectly), because it iterates through all primes less than a maximum bound, which I set to be 2.5 times the number of digits. All times are measured for a singlethreaded run because the multicore parallelization hasn't been successfully implemented yet. I am hugely thankful to casevh not only for his gmpy2 library but also for his help with programming. Without his contribution, I wouldn't have got this far. The first publicly available version will be made when the program reaches 1 billion (10^9) decimal places under a day, which, I hope, will be soon. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Does the constant 4.018 exists?  miket  Computer Science & Computational Number Theory  1  20191220 06:53 
Constant n Search  kar_bon  Riesel Prime Data Collecting (k*2^n1)  5  20090622 23:00 
Constant nSearch for k*2^n1  kar_bon  Riesel Prime Search  45  20071127 19:15 
Representing x^2+3y^2  ZetaFlux  Math  5  20050803 21:10 
Kaprekar's constant  mfgoode  Math  10  20040602 04:06 