Andrica's Conjecture Doc -- by Harry J. Smith

Documentation for Andrica's Conjecture Program

I have developed a computer program to investigate Andrica’s conjecture. My plan was to generate the consecutive primes and compute the Andrica function for each new prime. In order to see what was happening to the function without too much output, the program only saves and output results when the function is larger than all following values. Af(k) > Af(m) for all m > k. This is a heuristic program and the results are experimental since it has not been proven that the function could not have a large value, even greater than 1 for some later prime. The program’s short name is PrimeSRvb. The SR is for Square Root and the vb is for Visual Basic.

When you execute the program PrimeSRvb.exe you get the message:

PrimeSRvb - Investigates Andrica's Conjecture: Af(n) < 1 for all n > 0.

It using the sieve of Eratosthenes with DOUBLE Floating-point.

Visual Basic Version 3.6.23

This program computes terms for The On-Line Encyclopedia of Integer Sequences maintained by N. J. A. Sloane. See: http://www.research.att.com/~njas/sequences/ .

The sequences computed are A084974, A084975, A084976, and A084977.

A084974(n) are the primes such that Af(k) > Af(m) for all m > k, where Af(k) is the Andrica function sqrt(+1) − sqrt(), and denotes the k-th prime. See: http://mathworld.wolfram.com/AndricasConjecture.html .

A084975(n) are the primes +1 such that Af(k) > Af(m) for all m > k.

A084976(n) are values of k such that Af(k) > Af(m) for all m > k.

A084977(n) = Ag(k) = floor(1000000*Af(k)) with k such that Af(k) > Af(m) for all m > k.

The latest version of this program and all of its source files can be downloaded from http://www.geocities.com/hjsmithh/PrimeSR/ .

Andrica's conjecture states that, for the n-th prime number, the inequality

Af(n) = − < 1 for all n > 0.

The largest value found for Af(n) is at n = 4 where we have

Af(4) = − = 0.6708734792908092586... .

The search has gown past n = 26 * 10, so it is highly likely the conjecture is true. However, it has never been proven. Past n = 26 * 10, Af(n) appears to be less than 0.0002.

To show how Af(n) decreases with n, four sequences are defined and computed, see above.

The program uses a Function NPrime(M As Long) As Long to generate consecutive prime numbers. It is an implementation of Algorithm 357 of the Collected Algorithms from ACM. It is an efficient prime number generator using the sieve of Eratosthenes. Here M = Number of new primes desired this call. The current length of the tables in array IQ and JQ is returned. This is approximately the number of primes < . It must not exceed QS, referred to as "Prime # Table Length" on the opening screen when you start the program. The user can set QS to any value 1 <= QS <= 2−1. Values less than 200 produce no output. Numbers greater than about 10000000 give an out of memory alarm. The default value is 200000.

The next parameter on the startup screen is Siz "Size of Result Table". The default value is 500. The result table is used to store new values of the four sequences as they are computed and the time it took to compute them. If you intend to compute many terms, you need a value of Siz at least 100 or so. It is not known how large it must be for extremely long calculations. If the program stops with "Numbers got too large!" message due to Siz being to small, the program can be restarted with a larger Siz. Just do a "Read SnapShot" after the program gets started.

The user can also control Mc, the number of new primes generated on each call of NPrime. This is called "Primes Gen. Per Cycle" on the initial operating screen. The default value is 105000, but the user can change it to any value 2 <= Mc <= 2−1. Values much larger than the nominal are not recommended. Also, if you plan to reread snapshot files, explained later, The value of Mc cannot be changed from what it was when the file was written.

The last parameter on the screen that the operator can change is Cyc "Cycles Per Status". Its default value is one, but Cyc be changed to any value 1 <= Cyc <= 1000. Large values on Cyc produce fewer status updates.

There are two command buttons on this first screen "Run" and "Exit". Choose "Exit" to totally terminate the program. Choose "Run" to bring up the second screen and start calculations.

The second screen will start calculations and start updating status. The status is the output of J the "Current array index" which is the last index from 1 to Siz where the last terms of the computed sequences were stored. Every time Af(n) is computed, the new terms are stored over any earlier terms that had an Af value less than this current Af(n). The value of J tends to rise and fall with an overall general trend to get larger.

Other status items are, for example "Prime no. table length = 400 of 200000", "Current result array index = 38 of 500" and "Max prime tested = 9,442,211". The prime no. table is the array of all primes less than the square root of the last prime generated be the function NPrime. The Current results array index is the same as described in the last paragraph but here we also get the max length of the array, Siz. The max prime tested is just that. All primes less than this have been generated, counted, and tested by computing Af(n) = − .

The equation for defining Af(n) is good for a definition, but it as an unstable equation for calculation. For large values of n, and have several leading digits the same, so there is a large relative error when they are subtracted. To get a stable equation, multiply and divide by + and you get Af = ( − ) / ( + ). This is a very stable equation for computing Af(n).

There are six command buttons for controlling the actions of the program. they are "Read SnapShot", "Write Snapshot", "Write Results", "Test 'Too Large'", "Pause", and "Quit".

Write SnapShot: Selecting this will write a snapshot file containing all the data that is necessary to initialize and restart the programs calculations exactly where it was when the snapshot was taken. It contains all of the data in the results table and all of the data in the prime number table maintained by the function NPrime. When a snapshot file is written, the previous snapshot file, if any, is renamed PrimeSRvbSnapS.Bak and a new file is named PrimeSRvbSnapS.txt.

Read Snapshot: This will read the latest snapshot file PrimeSRvbSnapS.txt and restart the calculations form there.

Write Results: This will write a file containing the results table in a human readable form. When a results file is written, the previous results file, if any, is renamed PrimeSRvbRFile.Bak and a new file is named PrimeSRvbRFile.txt.

Test 'Too Large': This causes the program to try to store a zero in one cell pact the end of the prime number table. This simulates the numbers getting to large for the program, in its current configuration, to handle. The program will then write a results file to PrimeSRvbRFile.Too and "Quit".

Pause: This causes the program to stop using processor resources and wait to be resumed. When resumed by selecting OK on the message box provided, the amount of time delayed is accounted for to maintain an accurate value of the time required to calculate the terms of the sequences.

Quit: This does cause the calculations to stop and the user is returned to the original screen for possible restart "Run" or termination "Exit".

The functions of the six command buttons are also available in the "File" menu. Minimize and Close buttons are also available. The Close button does the same as the "Quit" as does the "Exit" in the file menu.

Next to the File menu is the Help menu which contains "Print Screen" and "About". The "About is obvious. Selecting "Print Screen" brings up a third screen containing this help text that can be scrolled up and down to review.

This third screen has a File menu that has the options "Print Setup", "Print" and "Exit". These are straightforward. The Exit merely exits this Help screen. The calculations have continued during the Help session.

To install, copy the files PrimeSRvb.exe and PrimeSRvbHelp.txt to any folder and execute the .exe file from there. For development, the following 11 files are required:

Help.frm

Help.frx

PrimeSRvb.BAS

PrimeSRvb.exe

PrimeSRvb.vbp

PrimeSRvb.vbw

PrimeSRvbHelp.txt

Run.frm

Run.frx

Startup.frm

Startup.frx

The program can generate the following 5 files:

PrimeSRvbRfile .Bak

PrimeSRvbRFile .Too

PrimeSRvbRFile .txt

PrimeSRvbSnapS .Bak

PrimeSRvbSnapS .txt

The results of the program were plotted using Mathsoft’s Mathcad program. The plots are shown here after a cut and past job and converting to a .gif file using Jasc Paint Shop Pro. The data for the first plot was actually generated by a simpler QuickBasic program PrimeSRa.QB that output all values of Af(n) from n = 1 to 1000.

-Harry

Return to Andrica's Conjecture
Return to Harry's Home Page

This page accessed times since October 20, 2004.
Page created by: [email protected]
Changes last made on Monday, 18-Jul-05 10:34:45 PDT