Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

Tags:
  1. May 19, 2017 #1
    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. jcsd
  3. May 19, 2017 #2

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

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

    Mark44

    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)
     
  5. May 19, 2017 #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)
     
  6. Jun 25, 2017 #5

    Baluncore

    User Avatar
    Science Advisor

    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.
     
  7. Jun 29, 2017 #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)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Is there an easy way to find ints i,j,k satisfying i*j=k^2?
Loading...