mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   The "one billion minus 999,994,000" digits prime number (https://www.mersenneforum.org/showthread.php?t=20568)

 alpertron 2015-10-24 17:52

[QUOTE=a1call;413638]I have not done any calculations for the run time. However for the sake of argument, suppose that there is a mathematical expression made of numbers and mathematical operators (example: 2 + 3) that is guaranteed to be a prime if it is less than 10[SUP]10000000000[/SUP]. Then you won't need to try and calculate every digit of the mathematical expression. A scientific notation form it would be enough to show that it is smaller than 10[SUP]10000000000[/SUP. Still when you are talking about a billion+ digits the expression will be lengthy and run time long. But based on an educated guess it would still be quicker than what already has been done with relatively smaller large primes.
But that's just a guesstimate.[/QUOTE]
From this text I highly doubt that you will find someone to program your algorithm, except if you pay his/her services in advance.

 science_man_88 2015-10-24 19:45

[QUOTE=alpertron;413648]From this text I highly doubt that you will find someone to program your algorithm, except if you pay his/her services in advance.[/QUOTE]

Too late, but it's not really the newest idea. Or the fastest.edit never mind that pm was a test of my programming skills.

 VBCurtis 2015-10-24 20:06

[QUOTE=a1call;413638]I have not done any calculations for the run time. However for the sake of argument, suppose that there is a mathematical expression made of numbers and mathematical operators (example: 2 + 3) that is guaranteed to be a prime if it is less than 10[SUP]10000000000[/SUP]. Then you won't need to try and calculate every digit of the mathematical expression. A scientific notation form it would be enough to show that it is smaller than 10[SUP]10000000000[/SUP. Still when you are talking about a billion+ digits the expression will be lengthy and run time long. But based on an educated guess it would still be quicker than what already has been done with relatively smaller large primes.
But that's just a guesstimate.[/QUOTE]

Do. It. Produce small primes. 20 digits with pencil and paper, use pari/wolfram to check your output. Your "educated guess" is uneducated until you demonstrate otherwise. Find a prime of length 100 digits, by hand or by wolfram alpha or whatever via your algorithm. To find one of 1000 digits, the algorithm should take 1000 times longer. Each zero you add for digit length, 1000 times longer to find a prime. How many zeroes longer is 1 billion digits?

My educated guess is that your method would take longer than our lifetime to calculate an actual 1 million digit prime. Your claims so far amount to "I have a formula, but I don't know how complicated it is for big numbers. Computers are fast, so I just need a programmer to make my formula on a computer, and it'll turn out primes fast. Easy!"

 a1call 2015-10-24 20:06

[QUOTE=science_man_88;413657]Too late, but it's not really the newest idea. Or the fastest.edit never mind that pm was a test of my programming skills.[/QUOTE]

Not to mention elementary school arithmetic.

 alpertron 2015-10-25 12:17

[QUOTE=VBCurtis;413659]Do. It. Produce small primes. 20 digits with pencil and paper, use pari/wolfram to check your output. Your "educated guess" is uneducated until you demonstrate otherwise. Find a prime of length 100 digits, by hand or by wolfram alpha or whatever via your algorithm. To find one of 1000 digits, the algorithm should take 1000 times longer. Each zero you add for digit length, 1000 times longer to find a prime. How many zeroes longer is 1 billion digits?

My educated guess is that your method would take longer than our lifetime to calculate an actual 1 million digit prime. Your claims so far amount to "I have a formula, but I don't know how complicated it is for big numbers. Computers are fast, so I just need a programmer to make my formula on a computer, and it'll turn out primes fast. Easy!"[/QUOTE]

If the method produced only prime numbers as the OP claims, there would be no need to check the output for primality. So the method could run a lot faster than O(n[SUP]3[/SUP]). Anyway, it appears that this is material for a Math-fiction book.

 a1call 2015-10-26 00:12

Hi,
Since someone let the cat out of the bag (with good intentions no doubt) I might as well let it out properly and 1st hand.
However, the following statement is likely to be overlooked by a few members and in order of not having to repeat myself, please forgive the text format:

[SIZE=5][B][COLOR=Red]The following is not what I had in mind when I decided to tackle the one-billion+ prime challenge. That theorem and its associated approach is still safe and will only be disclosed to a party with the right computing credentials which would be willing to assist me in this endeavor.
[/COLOR][/B][/SIZE]
Anyone who is not pleased with that then, though.

One more note: This is a first draft of the proof and I have not proofread it. So should you find an i not dotted or a t not crossed, then good for you. A real mathematician would not need a proof and would instantly see that the statement is true (I know there are a few of them around).

[COLOR=#2E74B5][FONT=&quot]Theorem 1: [/FONT][/COLOR]
[FONT=Calibri]For the set [/FONT][B][FONT=&quot]A[/FONT][/B][FONT=Calibri] of [B][I]n[/I][/B] [U]consecutive[/U] prime numbers staring from [B]2[/B] and ending at [B]Pn[/B].[/FONT]
[FONT=Calibri]Let:[/FONT]
[B][FONT=&quot]B[/FONT][/B][B][FONT=&quot]⊂[/FONT][/B][B][FONT=&quot]A &[/FONT][/B][FONT=&quot] [B]C=A-B[/B][/FONT]
[FONT=Calibri] [/FONT]
[FONT=Calibri]Let the number [B]b[/B] be equal to multiples of any-integer-power greater-than [B]0[/B] of all-the-elements of [/FONT][B][FONT=&quot]B[/FONT][/B][FONT=Calibri].[/FONT]
[FONT=Calibri] [/FONT]
[FONT=Calibri]Let the number [B]c[/B] be equal to multiples of any-integer-power greater-than [B]0[/B] of all-the-elements of [/FONT][B][FONT=&quot]C[/FONT][/B][FONT=Calibri].[/FONT]
[FONT=Calibri] [/FONT]
[FONT=Calibri]Then [B]d = [/B][/FONT][B]|±[/B][B][FONT=Calibri]b[/FONT]±[/B][B][FONT=Calibri]c[/FONT]|[/B] [FONT=Calibri] is a [B][U]prime number[/U],[/B][/FONT]
[B][FONT=&quot]∀[/FONT][/B][B][FONT=Calibri]d: d < Pn2[/FONT][/B][FONT=Calibri] [/FONT]
[B][FONT=&quot]Proof:[/FONT][/B]

[B][FONT=Calibri]d[/FONT][/B][FONT=Calibri] is not divisible by any elements of [/FONT][B][FONT=&quot]A[/FONT][/B][FONT=Calibri], because [/FONT]
[B][I][FONT=Calibri](I) [/FONT][/I][/B][FONT=Calibri]if there are any [/FONT][B][I]a [/I][/B][I]such that[/I][FONT=Calibri]:[/FONT]
[B][I] a [/I][/B][B][FONT=&quot]∈[/FONT][/B][B][FONT=&quot] A &[/FONT][/B][FONT=&quot] [B] ([/B][/FONT][B][I]a [/I][/B][B][FONT=&quot]∈[/FONT][/B][B][FONT=&quot] B [/FONT][/B][B][FONT=&quot]⊕[/FONT][/B][B][FONT=&quot] [/FONT][I]a [/I][/B][B][FONT=&quot]∈[/FONT][/B][B][FONT=&quot] B) &[/FONT][/B][FONT=&quot] [B] [/B][/FONT][B][I]a[/I][/B][B][FONT=&quot][I]∣[/I][/FONT][/B][B][FONT=Calibri]d [/FONT][/B][B][FONT=&quot]⇒[/FONT][/B][B][FONT=Calibri] ( d/[/FONT][I]a[/I][I] = m & m [/I][/B][B][FONT=&quot]∈ ℤ)[/FONT][I][/I][/B]
[I]Then[/I]
[B][FONT=Calibri]d/[/FONT][I]a[/I][I] = m [/I][/B][B][FONT=&quot]⇒ [/FONT]|±[/B][B][FONT=Calibri]b[/FONT]±[/B][B][FONT=Calibri]c[/FONT]|[/B][B][FONT=Calibri]/[/FONT][I]a[/I][I] = m [/I][/B][B][FONT=&quot]⇒ [/FONT]|[/B][B][FONT=Calibri]b[/FONT]|/[I]a [/I] ± |[/B][B][FONT=Calibri]c[/FONT]|[/B][B][FONT=Calibri]/[/FONT][I]a[/I][I] = m [/I][/B]
[B][FONT=&quot] [/FONT][/B]
[B][I][FONT=&quot](ii) [/FONT][/I][/B][B][FONT=&quot]∵[/FONT][/B][B][FONT=&quot] ([/FONT][I]a [/I][/B][B][FONT=&quot]∈[/FONT][/B][B][FONT=&quot] B [/FONT][/B][B][FONT=&quot]⊕[/FONT][/B][B][FONT=&quot] [/FONT][I]a [/I][/B][B][FONT=&quot]∈[/FONT][/B][B][FONT=&quot] C) [/FONT][/B][FONT=&quot]∴ [B]([/B][/FONT][B]|[/B][B][FONT=Calibri]b[/FONT]|/[I] a [/I][/B][B][FONT=&quot]∈ ℤ[/FONT][/B][B][FONT=&quot] [/FONT][/B][B][FONT=&quot]⊕ [/FONT]|c|/[I] a [/I][/B][B][FONT=&quot]∈ ℤ[/FONT][/B][B][FONT=&quot] )[/FONT][/B]
[B][FONT=&quot] [/FONT][/B]
[FONT=&quot]Since [/FONT][B]|[/B][B][FONT=Calibri]b[/FONT]|/[I]a [/I] ± |[/B][B][FONT=Calibri]c[/FONT]|[/B][B][FONT=Calibri]/[/FONT][I]a [/I][/B][I]is an integer and either [/I][B]|[/B][B][FONT=Calibri]b[/FONT]|/[I]a [/I] [/B]or [B] |[/B][B][FONT=Calibri]c[/FONT]|[/B][B][FONT=Calibri]/[/FONT][I]a [/I][/B][I]is an integer, then the other has to be an integer since the sum of an integer number with a non integer number cannot be an integer. This conflicts with statement [B][I](ii)[/I][/B] which states that either [/I][B]|[/B][B][FONT=Calibri]b[/FONT]|/[I]a [/I][/B][I]or [/I][B]|c|/[I]a[/I][/B][I] is an integer exclusively. Thus statement [B][I](i)[/I][/B] is false.[/I]
[I]Since [/I][B][FONT=Calibri]d < Pn2[/FONT][/B][FONT=Calibri] and [B] d[/B] is not divisible by any prime number less than or equal to [B]Pn[/B] , then [B]d [/B]is a [B]prime number[/B].[/FONT]
[FONT=&quot][I]∎[/I][/FONT][I][/I]

The following is the routine that I have forwarded to the 2 people who have offered to assist me.

[QUOTE]* Take any set S of [B]consecutive[/B] positive primes starting from 2 and ending at some Pn.
* Write a code routine to try either random combinations, or ordered trial combinations of [B]all of[/B] the above primes and generate a sum of the form z = a - b where a and b have no common prime factors
* a and b each, are multiplications of positive integer powers of any distinct and non empty subsets of A and B such that A + B = S
** Any sum z < Pn2 that your routine comes up with id's guaranteed to be a prime.

Here is a small integer example for clarification:
z = 13 x 11[SUP]2[/SUP] - 7[SUP]2[/SUP] x 5 x 3 x 2 = 103
Here S is the set of first consecutive primes from 2 to Pn = 13
A = {11,13}
B = {2,3,5,7}
Note: sets A and B do not need to be made of consecutive elements.
[/QUOTE]

Here is the thread on the Physics Forum:

Thank you to all for your time and replies.

 alpertron 2015-10-26 00:49

Although the method generates primes as expected, the minuend and subtrahend are almost as big as in the previous version. For more interesting ranges, you should subtract extremely huge numbers and the timing would be worse than trial division.

You could use modular arithmetic in order to speed up your algorithm, but again this will be worse than trial division. Why? The union of the sets A and B must include all prime numbers below n. So you need to perform about n/log(n) multiplications mod prime greater than n[SUP]2[/SUP]. So the number of steps is the same as the worst case of trial division. Notice also that to find a prime p<n[SUP]2[/SUP] first you will need to compute a prime larger than n[SUP]2[/SUP] in order to use it as the modulus. So again this is not useful at all.

1 Attachment(s)
Is this Phase [STRIKE]1[/STRIKE] 2 of [STRIKE][URL="https://en.wikipedia.org/wiki/We%27re_Only_in_It_for_the_Money"]Lumpy Gravy[/URL][/STRIKE] [URL="http://www.mersenneforum.org/showthread.php?t=19507"]Kathegetes[/URL]? :smile:

 science_man_88 2015-10-26 01:11

so that wasn't just a test of my programming skills ? edit: is that better Batalov.

 Batalov 2015-10-26 01:16

[QUOTE=a1call;413772][code]* Take any set S of [B]consecutive[/B] positive primes starting from 2 and ending at some P[SUB]n[/SUB].
* ...
* ...
* Any sum z < P[SUB]n[/SUB]2 that your routine comes up with id's guaranteed to be a prime.
* PROFIT!!!!!!!!![/code][/QUOTE]
So, you are saying that for you method to work you need to store somewhere [B]all primes[/B] up to 10[SUP]500000000[/SUP], right?
Good luck with that.
This universe is not equipped to store all primes up to 10[SUP]1000[/SUP], is it?

 Batalov 2015-10-26 01:22

[QUOTE=science_man_88;413777]so that wasn't just a test of my programming skills ?[/QUOTE]
A rhetorical question if there ever was one.

[SPOILER]Not seeing your messages saves so much of my page space!
You really needed to quote the whole message to ask [I]that[/I]?[/SPOILER]

All times are UTC. The time now is 20:35.