Generating Prime Factors

Let us denote the Set of Prime Factors by X = {(n,f)} where n is integer and f is a set of prime numbers that makes up n by multiplication.

Multiplying the set X, upto N by an integer z = w^u is defined as z.X = {z.(n,f)} = {(z.n, f union w)} where w is prime, u is a positive integer and z.n <= N.

z.(n,f) returns void, if z.n > N.

generate_prime_factors(P, N) // P is the set of prime numbers upto N, N is a positive integer
{

initialize a Set of Prime Factors, X = {(1,{1})}

for all the prime numbers i in the set P in ascending order do
j= 1;
while i^j <= N do
Y = i^j.X;
X = X union Y;
j++;
end while
end for
return X

}


let us find the prime factorization of all the numbers upto N = 10:

inital state:
X = {(1,{1})}

step1: i = 2, j = 1
Y = 2.X ={(2,{1,2})}
X = X union Y = {(1,{1}), (2,{1,2})}

step2: i = 2, j=2
Y = 2^2.X = {(4,{1,2}), (8,{1,2})}
X = X union Y = {(1,{1}), (2,{1,2}), (4,{1,2}), (8,{1,2})}

step3:i = 2, j = 3
Y = 2^3.X = {(8,{1,2})}
X = X union Y = {(1,{1}), (2,{1,2}), (4,{1,2}), (8,{1,2})}

step4: i = 2, j = 4; i^j = 2^4 = 16 > N = 10
do nothing


step5: i = 3, j = 1
Y = 3.X = {(3,{1,3}), (6,{1,2,3})}
X = X union Y = {(1,{1}), (2,{1,2}), (3,{1,3}), (4,{1,2}), (6,{1,2,3}), (8,{1,2})}

step6: i = 3, j = 2
Y = 3^2.X = {(9,{1,3})}
X = X union Y = {(1,{1}), (2,{1,2}), (3,{1,3}), (4,{1,2}), (6,{1,2,3}), (8,{1,2}), (9,{1,3})}


step7: i = 3, j =3; 3^3 > 10
do nothing

step8: i = 5, j = 1
Y = 5.X = {(5,{1,5}), (10,{1,2,5})}
X = X union Y = {(1,{1}), (2,{1,2}), (3,{1,3}), (4,{1,2}), (5,{1,5}), (6,{1,2,3}), (8,{1,2}), (9,{1,3}), (10,{1,2,5})}


step9: i = 5, j = 2; 5^2 = 25
do nothing

step9: i = 7, j = 1
Y = 5.X = {(7,{1,7})}
X = X union Y = {(1,{1}), (2,{1,2}), (3,{1,3}), (4,{1,2}), (5,{1,5}), (6,{1,2,3}), (7,{1,7}), (8,{1,2}), (9,{1,3}), (10,{1,2,5})}

Juktibidda: মাছ গু খায়. মানুষ মাছ খায়. তার মানে মানুষ গু খায়

বাংলাদেশে ছোটবেলায় দেখতাম যুক্তিবিদ্দা বলে একটা বিষয় ইন্টারমিডিয়েট লেভেল এ পরানো হত. সবাই সাবজেক্ট টা নিয়া হাসি মস্করা করত. এই  সাবজেক্ট  এ  নাকি  এমন  জিনিস  শেখানো  হয়: "মাছ গু খায়. মানুষ মাছ খায়. তার মানে মানুষ  গু খায়.". দীর্ঘ পড়াশুনা বিরতির  পর  এই  বিদেশ  বিভুয়ে আবার  পড়তে  এসে  এই  যুক্তিবিদ্যা  সাবজেক্ট  টা  আমাকে  পড়তে  হচ্ছে  M.Sc. ডিগ্রী  পাওয়ার জন্য . এইখানে  এই বিষয় এ দুইটা কোর্স আছে. একটার নাম হলো Advanced Course In Computational Logic, অন্যটার নাম হলো Answer Set Programming . এই দুইটা কোর্স পড়তে গিয়ে বুঝলাম যুক্তিবিদ্যা সাবজেক্ট টাকে অহেতুক পচানো হত. মাছ গু খায় বলে মানুষ ও গু খায় প্রমান করতে হলে প্রমান করতে হবে যে মানুষ আসলে মাছ. কিন্তু মানুষ আসলে মাছ না, বরং মানুষ মাছ খায়. কেউ যদি প্রমান করতে পারে যে মানুষ আসলে মাছ তাহলেই শুধুমাত্র প্রমানিত হবে যে মানুষ গু খায়. 

If X = x1 mod m1; X = x2 mod m2; Where m1 and m2 are co-prime, x1 < m1, x2 < m2. Then there is at most one X in the interval 0 <= X < m1*m2

Solution:

X is greater than some multiple of m1 by x1, and greater than some multiple of m2 by x2. That means, we need to find out multiple of m1 and m2 which has the difference of x1 - x2 when x1 > x2. Otherwise we need to find out multiple of m1 and m2 which has the difference of x2 - x1. That means, If there exists an X, then there exists two integers r and s such that

m2*s - m1*r = x1 - x2 if x1 > x2

m1*r - m2*s = x2 - x1 otherwise

And for both of the cases X = m2*s + x2 = m1*r + x1;

Now,the next such pair of multiple of m1 and m2 can be found by adding some multple of m1 to m1*r and by adding some multiple of m2 to m2*s. But to preserve the equality these two multiples need to be equal. That means they need to be common multiple of m1 and m2. The lowest common multiple of m1 and m2 are m1*m2 as they are co-prime. 

Lets say there exist one X such that 0 <= X < m1*m2 (actually at least one such X exist which is provable but not mentioned here); Then the next possible value of X will be, X = m2*s + m1*m2 + x2 = m1*r + m1*m2 + x1 >= m1*m2

That means there exist at most one X such that 0 <= X < m1*m2