Is there an easy way to find ints i,j,k satisfying i*j=k^2?

  • Thread starter SlurrerOfSpeech
  • Start date
  • Tags
    Algorithm
In summary, i, j, and k are variables representing integers in the equation i*j = k^2. It is important to find a solution to this equation because it can be used in various mathematical problems and has practical applications in fields like computer science and engineering. There are multiple methods for finding solutions, but no single formula or method that works for all cases. This equation can only be solved for integer values and has limitations and restrictions, such as the values of i, j, and k must be positive integers and there may not be a solution for every combination of values.
  • #1
SlurrerOfSpeech
141
11
Long-story short, as part of a larger problem I'm trying to solve, I need all i,j>=0 such that i*j=k2 for all k in [1, ..., n]. What I'm doing currently is iterating through [12, 22, ..., n2] and for each value m I'm using

Code: 
        public static IEnumerable<Tuple<int, int>> Multipliers(ulong m)
        {
            ulong i = 1;
            ulong lastVal = m / 2;
            for(; i <= lastVal; i++)
            {
                if(m % i == 0)
                {
                    lastVal = m / i;
                    if(lastVal <= limit)
                    {
                        yield return Tuple.Create((int)i, (int)lastVal);
                    }
                }
            }
        }

to find the i,j pairs. But I think there may be some trick for finding them faster. Here are some I've printed out but I can't see the pattern.

Code: 
1->[(1,1)]
4->[(4,1),(2,2)]
9->[(9,1),(3,3)]
16->[(16,1),(8,2),(4,4)]
25->[(25,1),(5,5)]
36->[(36,1),(18,2),(12,3),(9,4),(6,6)]
49->[(49,1),(7,7)]
64->[(64,1),(32,2),(16,4),(8,8)]
81->[(81,1),(27,3),(9,9)]
100->[(100,1),(50,2),(25,4),(20,5),(10,10)]
121->[(121,1),(11,11)]
144->[(144,1),(72,2),(48,3),(36,4),(24,6),(18,8),(16,9),(12,12)]
169->[(169,1),(13,13)]
196->[(196,1),(98,2),(49,4),(28,7),(14,14)]
225->[(225,1),(75,3),(45,5),(25,9),(15,15)]
256->[(256,1),(128,2),(64,4),(32,8),(16,16)]
289->[(289,1),(17,17)]
324->[(324,1),(162,2),(108,3),(81,4),(54,6),(36,9),(27,12),(18,18)]
361->[(361,1),(19,19)]
400->[(400,1),(200,2),(100,4),(80,5),(50,8),(40,10),(25,16),(20,20)]
441->[(441,1),(147,3),(63,7),(49,9),(21,21)]
484->[(484,1),(242,2),(121,4),(44,11),(22,22)]
529->[(529,1),(23,23)]
576->[(576,1),(288,2),(192,3),(144,4),(96,6),(72,8),(64,9),(48,12),(36,16),(32,18),(24,24)]
625->[(625,1),(125,5),(25,25)]
676->[(676,1),(338,2),(169,4),(52,13),(26,26)]
729->[(729,1),(243,3),(81,9),(27,27)]
784->[(784,1),(392,2),(196,4),(112,7),(98,8),(56,14),(49,16),(28,28)]
841->[(841,1),(29,29)]
900->[(900,1),(450,2),(300,3),(225,4),(180,5),(150,6),(100,9),(90,10),(75,12),(60,15),(50,18),(45,20),(36,25),(30,30)]
961->[(961,1),(31,31)]
1024->[(1024,1),(512,2),(256,4),(128,8),(64,16),(32,32)]
1089->[(1089,1),(363,3),(121,9),(99,11),(33,33)]
1156->[(1156,1),(578,2),(289,4),(68,17),(34,34)]
1225->[(1225,1),(245,5),(175,7),(49,25),(35,35)]
1296->[(1296,1),(648,2),(432,3),(324,4),(216,6),(162,8),(144,9),(108,12),(81,16),(72,18),(54,24),(48,27),(36,36)]
1369->[(1369,1),(37,37)]
1444->[(1444,1),(722,2),(361,4),(76,19),(38,38)]
1521->[(1521,1),(507,3),(169,9),(117,13),(39,39)]
1600->[(1600,1),(800,2),(400,4),(320,5),(200,8),(160,10),(100,16),(80,20),(64,25),(50,32),(40,40)]
1681->[(1681,1),(41,41)]
1764->[(1764,1),(882,2),(588,3),(441,4),(294,6),(252,7),(196,9),(147,12),(126,14),(98,18),(84,21),(63,28),(49,36),(42,42)]
1849->[(1849,1),(43,43)]
1936->[(1936,1),(968,2),(484,4),(242,8),(176,11),(121,16),(88,22),(44,44)]
2025->[(2025,1),(675,3),(405,5),(225,9),(135,15),(81,25),(75,27),(45,45)]
2116->[(2116,1),(1058,2),(529,4),(92,23),(46,46)]
2209->[(2209,1),(47,47)]
2304->[(2304,1),(1152,2),(768,3),(576,4),(384,6),(288,8),(256,9),(192,12),(144,16),(128,18),(96,24),(72,32),(64,36),(48,48)]
2401->[(2401,1),(343,7),(49,49)]
2500->[(2500,1),(1250,2),(625,4),(500,5),(250,10),(125,20),(100,25),(50,50)]
2601->[(2601,1),(867,3),(289,9),(153,17),(51,51)]
2704->[(2704,1),(1352,2),(676,4),(338,8),(208,13),(169,16),(104,26),(52,52)]
2809->[(2809,1),(53,53)]
2916->[(2916,1),(1458,2),(972,3),(729,4),(486,6),(324,9),(243,12),(162,18),(108,27),(81,36),(54,54)]
3025->[(3025,1),(605,5),(275,11),(121,25),(55,55)]
3136->[(3136,1),(1568,2),(784,4),(448,7),(392,8),(224,14),(196,16),(112,28),(98,32),(64,49),(56,56)]
3249->[(3249,1),(1083,3),(361,9),(171,19),(57,57)]
3364->[(3364,1),(1682,2),(841,4),(116,29),(58,58)]
3481->[(3481,1),(59,59)]
3600->[(3600,1),(1800,2),(1200,3),(900,4),(720,5),(600,6),(450,8),(400,9),(360,10),(300,12),(240,15),(225,16),(200,18),(180,20),(150,24),(144,25),(120,30),(100,36),(90,40),(80,45),(75,48),(72,50),(60,60)]
3721->[(3721,1),(61,61)]
3844->[(3844,1),(1922,2),(961,4),(124,31),(62,62)]
3969->[(3969,1),(1323,3),(567,7),(441,9),(189,21),(147,27),(81,49),(63,63)]
4096->[(4096,1),(2048,2),(1024,4),(512,8),(256,16),(128,32),(64,64)]
4225->[(4225,1),(845,5),(325,13),(169,25),(65,65)]
4356->[(4356,1),(2178,2),(1452,3),(1089,4),(726,6),(484,9),(396,11),(363,12),(242,18),(198,22),(132,33),(121,36),(99,44),(66,66)]
4489->[(4489,1),(67,67)]
4624->[(4624,1),(2312,2),(1156,4),(578,8),(289,16),(272,17),(136,34),(68,68)]
4761->[(4761,1),(1587,3),(529,9),(207,23),(69,69)]
4900->[(4900,1),(2450,2),(1225,4),(980,5),(700,7),(490,10),(350,14),(245,20),(196,25),(175,28),(140,35),(100,49),(98,50),(70,70)]
5041->[(5041,1),(71,71)]
5184->[(5184,1),(2592,2),(1728,3),(1296,4),(864,6),(648,8),(576,9),(432,12),(324,16),(288,18),(216,24),(192,27),(162,32),(144,36),(108,48),(96,54),(81,64),(72,72)]
5329->[(5329,1),(73,73)]
5476->[(5476,1),(2738,2),(1369,4),(148,37),(74,74)]
5625->[(5625,1),(1875,3),(1125,5),(625,9),(375,15),(225,25),(125,45),(75,75)]
5776->[(5776,1),(2888,2),(1444,4),(722,8),(361,16),(304,19),(152,38),(76,76)]
5929->[(5929,1),(847,7),(539,11),(121,49),(77,77)]
6084->[(6084,1),(3042,2),(2028,3),(1521,4),(1014,6),(676,9),(507,12),(468,13),(338,18),(234,26),(169,36),(156,39),(117,52),(78,78)]
6241->[(6241,1),(79,79)]
6400->[(6400,1),(3200,2),(1600,4),(1280,5),(800,8),(640,10),(400,16),(320,20),(256,25),(200,32),(160,40),(128,50),(100,64),(80,80)]
6561->[(6561,1),(2187,3),(729,9),(243,27),(81,81)]
6724->[(6724,1),(3362,2),(1681,4),(164,41),(82,82)]
6889->[(6889,1),(83,83)]
7056->[(7056,1),(3528,2),(2352,3),(1764,4),(1176,6),(1008,7),(882,8),(784,9),(588,12),(504,14),(441,16),(392,18),(336,21),(294,24),(252,28),(196,36),(168,42),(147,48),(144,49),(126,56),(112,63),(98,72),(84,84)]
7225->[(7225,1),(1445,5),(425,17),(289,25),(85,85)]
7396->[(7396,1),(3698,2),(1849,4),(172,43),(86,86)]
7569->[(7569,1),(2523,3),(841,9),(261,29),(87,87)]
7744->[(7744,1),(3872,2),(1936,4),(968,8),(704,11),(484,16),(352,22),(242,32),(176,44),(121,64),(88,88)]
7921->[(7921,1),(89,89)]
8100->[(8100,1),(4050,2),(2700,3),(2025,4),(1620,5),(1350,6),(900,9),(810,10),(675,12),(540,15),(450,18),(405,20),(324,25),(300,27),(270,30),(225,36),(180,45),(162,50),(150,54),(135,60),(108,75),(100,81),(90,90)]
8281->[(8281,1),(1183,7),(637,13),(169,49),(91,91)]
8464->[(8464,1),(4232,2),(2116,4),(1058,8),(529,16),(368,23),(184,46),(92,92)]
8649->[(8649,1),(2883,3),(961,9),(279,31),(93,93)]
8836->[(8836,1),(4418,2),(2209,4),(188,47),(94,94)]
9025->[(9025,1),(1805,5),(475,19),(361,25),(95,95)]
9216->[(9216,1),(4608,2),(3072,3),(2304,4),(1536,6),(1152,8),(1024,9),(768,12),(576,16),(512,18),(384,24),(288,32),(256,36),(192,48),(144,64),(128,72),(96,96)]
9409->[(9409,1),(97,97)]
9604->[(9604,1),(4802,2),(2401,4),(1372,7),(686,14),(343,28),(196,49),(98,98)]
9801->[(9801,1),(3267,3),(1089,9),(891,11),(363,27),(297,33),(121,81),(99,99)]
 
Technology news on Phys.org
  • #2
I don't know if you would consider this easier. Certainly the logic is more complicated than brute force.
Get the list of primes less or equal to n. Combine them and ignore the combinations that multiply greater than n. Separate the set with two of each factor (counting multiplicity) into i and j.
 
  • #3
Code: 
1->[(1,1)]
4->[(4,1),(2,2)]
9->[(9,1),(3,3)]
.
.
.
There is some symmetry here that you are ignoring. The pairs (tuples) in brackets are (i, j) pairs such that their product is the square at the start of the row.
So I would think that for 4, you would have the two you list, as well as (1, 4), and similar for 9.

For 36, you show 36->[(36,1),(18,2),(12,3),(9,4),(6,6)]
For completeness, there are also, (4, 9), (3, 12), (2, 18), and (1, 36)
 
  • #4
What you need is the prime factorization of k^2. (wich is really easy to find from the factorization of k)
If you know k^2 = 2^4 * 3^2 for example, all the divisors in k^2, can be produced by multiplying all combinations of powers of 2 that are <= 2^4 and powers of 3 that are <= 3^2.

To find the prime factorization of k, there are a lot of advanced methods, but trial division will be ok if k<1000000. (max 168 primes to test)
 
  • #5
willem2 said:
What you need is the prime factorization of k^2. (wich is really easy to find from the factorization of k)
Correct.

Place all the prime factors of k in a pool, then duplicate the pool contents since you need all the prime factors of k2.
Draw unique selections of factors from the pool. Multiply each selection to get a different i.
Divide k2 by i, to get j, which is also the product of the un-selected prime factors in the pool.
 
  • Like
Likes mfb
  • #6
Here are the basic steps using k=63 as an example:
prime list (created at initialization time):
·· 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, ...
k factorization:
·· 2*2<63 so 63/2 - doesn't work
·· 3*3<63 so 63/3 = 21
·· 3*3<21 so 21/3 = 7
·· 3*3>7 so 7 is prime and we are done.
·· 0, 2, 0, 1, 0, 0, 0, ...
k*k factorization (double each number):
·· 0, 4, 0, 2, 0, 0, 0, ...
now process this sequence as if you were counting using digits that were different bases depending on their position - with the "ones" position on the left:
·· 0000 = 3^0*7^0 = 1
·· 0100 = 3^1*7^0 = 3
·· 0200 = 9
·· 0300 = 27
·· 0400 = 81 (but this is greater than k, so skip it. It will be handled by 0020 = 49)
·· 0001 = 7
·· 0101 = 21
·· 0201 = 63
·· 0301 = 189 (>k, so skip to next digit increment)
·· 0002 = 49
·· 0102 = 147 (>k, so skip to next digit increment, which ends the count)
 

Related to Is there an easy way to find ints i,j,k satisfying i*j=k^2?

1. What is the meaning of i, j, and k in this equation?

In this equation, i, j, and k are variables representing integers. The goal is to find values for these variables that satisfy the equation i*j = k^2, where ^2 represents squaring the value of k.

2. Why is it important to find a solution to this equation?

This equation is important because it can be used to solve various mathematical problems and can also have practical applications in fields such as computer science and engineering.

3. Is there a specific method or formula for finding the solution?

Yes, there are several methods for finding solutions to this equation, such as using prime factorization or the Pythagorean triple formula. However, there is no single formula or method that will work for all cases.

4. Can this equation be solved for non-integer values?

No, this equation is only solvable for integer values of i, j, and k. Non-integer values would not satisfy the equation.

5. Are there any limitations or restrictions to finding solutions to this equation?

Yes, there are some limitations and restrictions to finding solutions. For example, the values of i, j, and k must be positive integers and there may not be a solution for every combination of values.

Hot Threads

Recent Insights

Back
Top