smslca
Member level 1
I like to give an a method for factorization.
Below method is not an efficient method , but it is a method to factorize.
I dont know it already exist or not , which mean I have searched for this process on internet , But I did not find this method. So , may be I missed the page where this method already is , or it did not exists.
P-n method:
This method goes around the fact that , Any number P can be written as p - n + n ; n is any number . Here p is an odd number and is not a prime number.
If p0 is the given number. then
if p0 = p1 * p2 ; here p1 < p2
p0 - n = x1 * x2; here x1 < x2
then p0 = (p0 - n ) + n
==> p0 = ( x1 * x2 ) + ( |p1 - x1| * x2 ) - ( ( |p1 - x1| * x2 ) - n ) ;
or p0 = ( x1 * x2 ) - ( |p1 - x1| * x2 ) + ( ( |p1 - x1| * x2 ) + n ) ;
assuming |p1-x1| is the least difference .
Total no.of.loops = 2 * 2 * |p1 - x1| * divisor arrangements
divisor arrangements is explained below.
p-1 method. (later explained p-n method)
-------------
for example consider p-1 method explained with an example .
If given p is odd then p-1 is always an even number .
Let P0 = 919829 = 587 * 1567, then p-1 = 919828 = 2 * 2 * 229957
So , here we have to arrange the p-1 as the product of two divisors . like divisors_arrangement = 2*459914 or 4*229957
*** This divisor arrangement is important because we dont know, for which arrangement we will get an answer.
Here I am taking p-1 = 4*229957
As we know that p = (p-1) + 1 ;
so p = (4*229957) + 1
==> p = (4*229957) + (583 * 229927) - ( (583 * 229927) -1)
==> p = (4 * 229957) + (583 *229927) - 134064930
==> p = (229957 * 587 ) - 134064930
Here this 134064930 is exactly divisible by 587 as 134064930 = 587 * 228390
so p = (229957 * 587 ) - ( 587 * 228390)
==> p = (587 * (229957 - 228390))
==> p = (587 * 1567) ------- which is the required solution.
Here it is inefficient because it requires 587 - 4 no .of loops to factorize .
i.e . if a number n = n1 * n2 ,if n1 < n2 , and n-1 = (2^a0) * n3 , then it requires ( n1 - (2^a0) ) = lowest factor of p - lowest factor of (p-1) loops to factorize.
It is not necessarily to be difference of lowest factors. It may be "largest factor of p - largest factor of (p-1)) , if the difference is negative modulus of the number is the required loops , the least of the difference is the minimum no.of loops we are going to run .
also since there may be |negative difference|< +ve difference , we are going to check
total loops = (2 * the least difference ) * no.of.arrangements of divisors
Another cause for inefficiency is the no.of.arrangement of p-1 factors as the product of two divisors.
if there a "h" ways for the arrangement then the total no.of loops to factorize is = [ h * ( n1 - (2^a0) ) ]
The no.of.loops can be further decrease by , factorizing 229957. It can be done by taking p1 = 229957 and calculate p1 -1 and then proceeding the same steps as done above.
this must be continued until we get pn-1 = (2^an)*prime number , at some point of n.
Here 229957 can be factorized into = 7*7*13*19*19
for the above number 919829 the total number of loops decreased from 583 to 433 loops .
p-n method:
---------------
based on p0 = (p0 - n ) + n
The problem in above method is we have to do approximately the factor<sqrt(p) loops to factorize .
since the above number can be factorized even further we have decreased the no.of .loops .
But If numbers like 33250423 = 4363 * 7621= p0 has p0-1 = 6 * 5541737 . where 5541737 is a prime number then the total no.of .loops
to be run = 4363 - 6 = 4358 loops .
So replace (no.of.digits of p0 )/2 of p from left as zeros . i.e do p0 - 423 = 33250000 , now factorize this number using the same method for which you will get one of its divisors as 4375 , which means 33250000 = 4375 * 7600 ;
so the loops to be run = 2* |4363 - 4375 | * no.of.divisors arrangements = (12 * no.of.divisors arrangements ) loops.
Here also there exits an inefficiency ,
1. as the no.of.factors of p0 - n increases the no.of .ways of divisors arrangement increases. There by increasing the no.of.loops.
2. It is sure that by replacing (no.of.digits of p0 )/2 zeros will get one of the divisor of p0-n nearest to the divisor of p0 .
But I am not sure about the exact no.of zeros that has to be replaced . because,
---the number 694,891,321,868,591 = 15487811 * 44866981 will have the nearest divisor when no.of.zeros to be replaced is,
( (no.of.digits of p0 )/2 - 1 ) , i.e for 694,891,321,000,000 having divisor 15446320 . giving a difference of 41491 ;
---and for number 49976497 = 6343 * 7879 ; we will get minimum when zeros = ( (no.of.digits of p0 )/2 - 1 )
i.e ., at 49976000 have divisor 6247 , giving a difference of 91;
Below method is not an efficient method , but it is a method to factorize.
I dont know it already exist or not , which mean I have searched for this process on internet , But I did not find this method. So , may be I missed the page where this method already is , or it did not exists.
P-n method:
This method goes around the fact that , Any number P can be written as p - n + n ; n is any number . Here p is an odd number and is not a prime number.
If p0 is the given number. then
if p0 = p1 * p2 ; here p1 < p2
p0 - n = x1 * x2; here x1 < x2
then p0 = (p0 - n ) + n
==> p0 = ( x1 * x2 ) + ( |p1 - x1| * x2 ) - ( ( |p1 - x1| * x2 ) - n ) ;
or p0 = ( x1 * x2 ) - ( |p1 - x1| * x2 ) + ( ( |p1 - x1| * x2 ) + n ) ;
assuming |p1-x1| is the least difference .
Total no.of.loops = 2 * 2 * |p1 - x1| * divisor arrangements
divisor arrangements is explained below.
p-1 method. (later explained p-n method)
-------------
for example consider p-1 method explained with an example .
If given p is odd then p-1 is always an even number .
Let P0 = 919829 = 587 * 1567, then p-1 = 919828 = 2 * 2 * 229957
So , here we have to arrange the p-1 as the product of two divisors . like divisors_arrangement = 2*459914 or 4*229957
*** This divisor arrangement is important because we dont know, for which arrangement we will get an answer.
Here I am taking p-1 = 4*229957
As we know that p = (p-1) + 1 ;
so p = (4*229957) + 1
==> p = (4*229957) + (583 * 229927) - ( (583 * 229927) -1)
==> p = (4 * 229957) + (583 *229927) - 134064930
==> p = (229957 * 587 ) - 134064930
Here this 134064930 is exactly divisible by 587 as 134064930 = 587 * 228390
so p = (229957 * 587 ) - ( 587 * 228390)
==> p = (587 * (229957 - 228390))
==> p = (587 * 1567) ------- which is the required solution.
Here it is inefficient because it requires 587 - 4 no .of loops to factorize .
i.e . if a number n = n1 * n2 ,if n1 < n2 , and n-1 = (2^a0) * n3 , then it requires ( n1 - (2^a0) ) = lowest factor of p - lowest factor of (p-1) loops to factorize.
It is not necessarily to be difference of lowest factors. It may be "largest factor of p - largest factor of (p-1)) , if the difference is negative modulus of the number is the required loops , the least of the difference is the minimum no.of loops we are going to run .
also since there may be |negative difference|< +ve difference , we are going to check
total loops = (2 * the least difference ) * no.of.arrangements of divisors
Another cause for inefficiency is the no.of.arrangement of p-1 factors as the product of two divisors.
if there a "h" ways for the arrangement then the total no.of loops to factorize is = [ h * ( n1 - (2^a0) ) ]
The no.of.loops can be further decrease by , factorizing 229957. It can be done by taking p1 = 229957 and calculate p1 -1 and then proceeding the same steps as done above.
this must be continued until we get pn-1 = (2^an)*prime number , at some point of n.
Here 229957 can be factorized into = 7*7*13*19*19
for the above number 919829 the total number of loops decreased from 583 to 433 loops .
p-n method:
---------------
based on p0 = (p0 - n ) + n
The problem in above method is we have to do approximately the factor<sqrt(p) loops to factorize .
since the above number can be factorized even further we have decreased the no.of .loops .
But If numbers like 33250423 = 4363 * 7621= p0 has p0-1 = 6 * 5541737 . where 5541737 is a prime number then the total no.of .loops
to be run = 4363 - 6 = 4358 loops .
So replace (no.of.digits of p0 )/2 of p from left as zeros . i.e do p0 - 423 = 33250000 , now factorize this number using the same method for which you will get one of its divisors as 4375 , which means 33250000 = 4375 * 7600 ;
so the loops to be run = 2* |4363 - 4375 | * no.of.divisors arrangements = (12 * no.of.divisors arrangements ) loops.
Here also there exits an inefficiency ,
1. as the no.of.factors of p0 - n increases the no.of .ways of divisors arrangement increases. There by increasing the no.of.loops.
2. It is sure that by replacing (no.of.digits of p0 )/2 zeros will get one of the divisor of p0-n nearest to the divisor of p0 .
But I am not sure about the exact no.of zeros that has to be replaced . because,
---the number 694,891,321,868,591 = 15487811 * 44866981 will have the nearest divisor when no.of.zeros to be replaced is,
( (no.of.digits of p0 )/2 - 1 ) , i.e for 694,891,321,000,000 having divisor 15446320 . giving a difference of 41491 ;
---and for number 49976497 = 6343 * 7879 ; we will get minimum when zeros = ( (no.of.digits of p0 )/2 - 1 )
i.e ., at 49976000 have divisor 6247 , giving a difference of 91;