mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Programming (https://www.mersenneforum.org/forumdisplay.php?f=29)
-   -   Algebraithm for calculating primes (https://www.mersenneforum.org/showthread.php?t=20351)

 irina 2015-07-11 14:54

Algebraithm for calculating primes

[FONT=&quot]For prime number A, there is only one value B, such that what А + В[sup]2[/sup] = С[sup]2[/sup]
В = (А-1)/2
С = (А+1)/2
А = С[sup]2[/sup] – В[sup]2[/sup] = (С-В)*(С+В)
С – В = 1
If the number of semiprime A = k1 * k2, then there are at least two values, such that А + В[sup]2[/sup] = С[sup]2[/sup]
1. 1) А = С[sup]2[/sup] – В[sup]2[/sup] = (С-В)*(С+В);
k1 = C-B; k2= C + B
B2 = (n + trunc (sqrt (A))2 – A;
n – natural number [1; +∞);
C = n + trunc (sqrt (A))
2. 2) А = С[sup]2[/sup] – В[sup]2[/sup] = (С-В)*(С+В); С – В = 1
В = (А-1)/2 (B- maximum)
С = (А+1)/2

Example, А = 21
B1 = (А-1)/2 = (21-1)/2 = 10;
С = (А+1)/2 = (21+1)/2 = 11
21 + 10[sup]2[/sup] = 11[sup]2[/sup]
If semiprime A, then there is at least one value В2< B1:
Sqrt (21) = 4,58257..
Trunc (4,58257) = 4
B2 = (n + 4)2 – 21
for n =1 B2 = (1+4)[sup]2[/sup] – 21 = 4; B = 2;
C = n+ 4 = 1 + 4 =5
A = С2 – В2 = (С-В)*(С+В) = (5 – 2)*(5+2) = 3*7
А=k1 * k2= 3*7[/FONT]

 xilman 2015-07-11 17:57

[URL="http://rosettacode.org/wiki/AKS_test_for_primes#ALGOL_68"]Another algorithm for calculating primes[/URL]

 danaj 2015-07-11 21:16

For even more awesomeness you could use [URL="http://rosettacode.org/wiki/Miller-Rabin_primality_test#Deterministic_version"]Deterministic M-R[/URL] with ceil(n/4) as the limit.

[SIZE=1](I really wish the previously referenced task could be renamed, as far too many people think what is described is actually AKS)

Tempted to post the primality regex...
[/SIZE]

 R.D. Silverman 2015-07-13 12:24

[QUOTE=irina;405658][FONT=&quot]For prime number A, there is only one value B, such that what А + В[sup]2[/sup] = С[sup]2[/sup]
В = (А-1)/2
С = (А+1)/2
А = С[sup]2[/sup] – В[sup]2[/sup] = (С-В)*(С+В)
С – В = 1
If the number of semiprime A = k1 * k2, then there are at least two values, such that А + В[sup]2[/sup] = С[sup]2[/sup]
1. 1) А = С[sup]2[/sup] – В[sup]2[/sup] = (С-В)*(С+В);
k1 = C-B; k2= C + B
B2 = (n + trunc (sqrt (A))2 – A;
n – natural number [1; +∞);
C = n + trunc (sqrt (A))
2. 2) А = С[sup]2[/sup] – В[sup]2[/sup] = (С-В)*(С+В); С – В = 1
В = (А-1)/2 (B- maximum)
С = (А+1)/2

Example, А = 21
B1 = (А-1)/2 = (21-1)/2 = 10;
С = (А+1)/2 = (21+1)/2 = 11
21 + 10[sup]2[/sup] = 11[sup]2[/sup]
If semiprime A, then there is at least one value В2< B1:
Sqrt (21) = 4,58257..
Trunc (4,58257) = 4
B2 = (n + 4)2 – 21
for n =1 B2 = (1+4)[sup]2[/sup] – 21 = 4; B = 2;
C = n+ 4 = 1 + 4 =5
A = С2 – В2 = (С-В)*(С+В) = (5 – 2)*(5+2) = 3*7
А=k1 * k2= 3*7[/FONT][/QUOTE]

This is nothing but trivial algebra. Where is the ALGORITHM?
You have failed to specify any kind of procedure. All you have done is
assert the existence of some values satisfying some relations.

 retina 2015-07-13 12:27

[QUOTE=R.D. Silverman;405786]This is nothing but trivial algebra. Where is the ALGORITHM?[/QUOTE]Algebraithm for calculating primes?

 alpertron 2015-08-16 01:55

[QUOTE=irina;405658][FONT=&quot]For prime number A, there is only one value B, such that what А + В[sup]2[/sup] = С[sup]2[/sup]
В = (А-1)/2
С = (А+1)/2
А = С[sup]2[/sup] – В[sup]2[/sup] = (С-В)*(С+В)
С – В = 1
If the number of semiprime A = k1 * k2, then there are at least two values, such that А + В[sup]2[/sup] = С[sup]2[/sup]
1. 1) А = С[sup]2[/sup] – В[sup]2[/sup] = (С-В)*(С+В);
k1 = C-B; k2= C + B
B2 = (n + trunc (sqrt (A))2 – A;
n – natural number [1; +∞);
C = n + trunc (sqrt (A))
2. 2) А = С[sup]2[/sup] – В[sup]2[/sup] = (С-В)*(С+В); С – В = 1
В = (А-1)/2 (B- maximum)
С = (А+1)/2

Example, А = 21
B1 = (А-1)/2 = (21-1)/2 = 10;
С = (А+1)/2 = (21+1)/2 = 11
21 + 10[sup]2[/sup] = 11[sup]2[/sup]
If semiprime A, then there is at least one value В2< B1:
Sqrt (21) = 4,58257..
Trunc (4,58257) = 4
B2 = (n + 4)2 – 21
for n =1 B2 = (1+4)[sup]2[/sup] – 21 = 4; B = 2;
C = n+ 4 = 1 + 4 =5
A = С2 – В2 = (С-В)*(С+В) = (5 – 2)*(5+2) = 3*7
А=k1 * k2= 3*7[/FONT][/QUOTE]

It appears that you suggest to select n=1, 2, 3, ... until you get the factorization. This is just [URL="https://en.wikipedia.org/wiki/Fermat%27s_factorization_method"]Fermat's method[/URL].

 irina 2018-05-28 13:50

Mersenne prime number search algorithm

?

 All times are UTC. The time now is 10:05.