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

Tags:
1. May 19, 2017

### SlurrerOfSpeech

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 (Text):

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 (Text):

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)]

2. May 19, 2017

### FactChecker

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. May 19, 2017

### Staff: Mentor

Code (Text):
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. May 19, 2017

### willem2

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. Jun 25, 2017

### Baluncore

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.

6. Jun 29, 2017

### .Scott

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