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

  • Context:
  • Thread starter Thread starter SlurrerOfSpeech
  • Start date Start date
  • Tags Tags
    Algorithm
Click For Summary

Discussion Overview

The discussion revolves around finding non-negative integer pairs (i, j) such that their product equals the square of an integer k (i*j = k^2) for all k in a specified range. Participants explore various methods for generating these pairs, including brute force approaches and more complex mathematical techniques.

Discussion Character

  • Exploratory, Technical explanation, Debate/contested

Main Points Raised

  • One participant shares a brute force method using an iterative approach to find pairs (i, j) for squares of integers up to n, but expresses uncertainty about the efficiency of this method.
  • Another participant suggests a more complex method involving prime factorization, proposing to generate pairs by combining prime factors while considering their multiplicity.
  • A third participant points out potential symmetry in the pairs generated, arguing that some pairs may have been overlooked in the initial listing.
  • One participant emphasizes the importance of understanding the prime factorization of k^2 to derive all possible divisors and thus the pairs (i, j).

Areas of Agreement / Disagreement

Participants do not reach a consensus on the best method for finding the pairs (i, j). There are multiple competing views on the efficiency and completeness of the proposed approaches.

Contextual Notes

Some methods rely on the completeness of prime factorization and the understanding of divisor generation, which may not be fully resolved in the discussion.

SlurrerOfSpeech
Messages
141
Reaction score
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
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.
 
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)
 
What you need is the prime factorization of k^2. (which 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)
 
willem2 said:
What you need is the prime factorization of k^2. (which 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   Reactions: mfb
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)