Given a positive integer, how to find next larger integer that's a product of given prime factors

Question

I'm trying to write a function to estimate a good FFT size, which boils down to finding a number, $M \geq N$ s.t. $M$ is a product of prime factors (in particular $2,3,5,7,11,13$). Does anyone know an algorithm for doing this?

Answer 1

Multiple loop. If we have a partial product, one of the "sofar" numbers, that is already larger than the target $n,$ we can only do worse by multiplying by another one of the primes (by increasing that exponent). All the primes are below 20, so it suffices to consider partial products up to $20n.$

BETTER: on reflection, we may take the tighter bound $2n.$ We know that we may get an answer no worse than that using just a power of $2.$

==========================================

  n = 2 * 3 * 5 * 7 * 11 * 13;
  n *= 17 * 19 * 23 * 29;
  n *= 31 * 37 * 41 * 43 * 47;
  n *= 53 * 59 * 61 * 67 *71;
----------------------------------------
  target  n = 557940830126698960967415390

950551829131524428824142413  =   11^12 13^13   :   0,0,0,0,12,13
804313086188212978235812811  =   11^13 13^12   :   0,0,0,0,13,12
680572611390026366199533917  =   11^14 13^11   :   0,0,0,0,14,11
575869132714637694476528699  =   11^15 13^10   :   0,0,0,0,15,10
570389064953586206121040247  =   7^2 11^23 13   :   0,0,0,2,23,1
564735647321977610130979327  =   7^3 11^4 13^18   :   0,0,0,3,4,18
559361527685078641337745931  =   7^5 11^12 13^9   :   0,0,0,5,12,9
558040721244263815738365185  =   5 7^4 11^10 13^11   :   0,0,1,4,10,11
558024051986000542605257595  =   3^5 5 7^9 11^9 13^6   :   0,5,1,9,9,6
558007383225665396344586265  =   3^10 5 7^14 11^8 13   :   0,10,1,14,8,1
557975702410928445496978125  =   3^29 5^5 7^2 11 13^6   :   0,29,5,2,1,6
557959035094845525129909375  =   3^34 5^5 7^7 13   :   0,34,5,7,0,1
557947432080954688960687500  =   2^2 3^14 5^6 7^4 11^5 13^6   :   2,14,6,4,5,6
557941472774676767041705440  =   2^5 3^4 5 7^23 11^2 13   :   5,4,1,23,2,1
557941063680000000000000000  =   2^31 3^5 5^16 7^2 11 13   :   31,5,16,2,1,1

557940830126698960967415390  is target n 

====================================

==============================================================

  n = 1024 * 1024;
  n *= 1024;

  n += 153;
----------------------------------------------------
  target  n = 1073741977

10604499373  =   13^9   :   0,0,0,0,0,9
8973037931  =   11 13^8   :   0,0,0,0,1,8
7592570557  =   11^2 13^7   :   0,0,0,0,2,7
6424482779  =   11^3 13^6   :   0,0,0,0,3,6
5436100813  =   11^4 13^5   :   0,0,0,0,4,5
4599777611  =   11^5 13^4   :   0,0,0,0,5,4
3892119517  =   11^6 13^3   :   0,0,0,0,6,3
3293331899  =   11^7 13^2   :   0,0,0,0,7,2
2786665453  =   11^8 13   :   0,0,0,0,8,1
2357947691  =   11^9   :   0,0,0,0,9,0
2095756663  =   7 11^6 13^2   :   0,0,0,1,6,2
1773332561  =   7 11^7 13   :   0,0,0,1,7,1
1500512167  =   7 11^8   :   0,0,0,1,8,0
1333663331  =   7^2 11^5 13^2   :   0,0,0,2,5,2
1128484357  =   7^2 11^6 13   :   0,0,0,2,6,1
1096135733  =   7^7 11^3   :   0,0,0,7,3,0
1093547455  =   5 7^6 11 13^2   :   0,0,1,6,1,2
1091179089  =   3^2 7^2 11^4 13^2   :   0,2,0,2,4,2
1088602515  =   3^2 5 7 11^2 13^4   :   0,2,1,1,2,4
1086032025  =   3^2 5^2 13^6   :   0,2,2,0,0,6
1084620537  =   3^5 7^4 11 13^2   :   0,5,0,4,1,2
1083647565  =   3^9 5 7 11^2 13   :   0,9,1,1,2,1
1081088775  =   3^9 5^2 13^3   :   0,9,2,0,0,3
1076168025  =   3^16 5^2   :   0,16,2,0,0,0
1074218750  =   2 5^11 11   :   1,0,11,0,1,0
1073765616  =   2^4 3 7^5 11^3   :   4,1,0,5,3,0

1073741977  is target n 

==============================================================

int main()
{

  mpz_class n;
  n = 2 * 3 * 5 * 7 * 11 * 13;
  n *= 17 * 19 * 23 * 29;
  n *= 31 * 37 * 41 * 43 * 47;

  cout << endl << "  target  n = "  << n << endl << endl;

  mpz_class best = n * n;

  mpz_class sofar2 = 1;

  for(int a = 0; sofar2 <= n * 2; ++a) 
  {
    mpz_class sofar3 = sofar2;
    for(int b =0;  sofar3 <= n * 2; ++b)
    {
       mpz_class sofar5 = sofar3;
    for(int c = 0; sofar5 <= n * 2; ++c) 
    {
      mpz_class sofar7 = sofar5;
      for(int d = 0; sofar7 <= n * 2; ++d) 
      {
        mpz_class sofar11 = sofar7;
        for(int e = 0; sofar11 <= n * 2; ++e) 
        {
          mpz_class sofar13 = sofar11;
          for(int f = 0; sofar13 <= n * 2; ++f) 
          {
                if ( sofar13 < best  && sofar13 >= n)
                {
                  best = sofar13;
                  cout << best << "  =  " << mp_Factored(best) << "   :   " <<  a << ","  << b << ","  << c << ","  << d << ","  << e << ","  << f <<    endl;
                }  // if

               sofar13 *= 13;
          } // 13
          sofar11 *= 11;
        } // 11
        sofar7 *= 7;
      } // 7
      sofar5 *= 5;
    } // 5
       sofar3 *= 3;
    } // 3
    sofar2 *= 2;
  } // 2

    cout << endl   << n  <<  "  is target n  " << endl << endl;

  return 0;
}

==============================================================

     n = 1024 * 1024;
      n *= 1024;
        n *= 1024;
      n -= 1;
    --------------------
  target  n = 1099511627775

1792160394037  =   13^11   :   0,0,0,0,0,11
1516443410339  =   11 13^10   :   0,0,0,0,1,10
1283144424133  =   11^2 13^9   :   0,0,0,0,2,9
1270933805449  =   7^2 11^10   :   0,0,0,2,10,0
1129612841357  =   7^3 11^7 13^2   :   0,0,0,3,7,2
1126945514695  =   5 7^2 11^5 13^4   :   0,0,1,2,5,4
1124284486325  =   5^2 7 11^3 13^6   :   0,0,2,1,3,6
1121629741375  =   5^3 11 13^8   :   0,0,3,0,1,8
1108332850625  =   5^4 7 11^7 13   :   0,0,4,1,7,1
1105715771875  =   5^5 11^5 13^3   :   0,0,5,0,5,3
1102876442745  =   3 5 7^3 11^8   :   0,1,1,3,8,0
1100272248075  =   3 5^2 7^2 11^6 13^2   :   0,1,2,2,6,2
1099805224518  =   2 3^6 7^4 11 13^4   :   1,6,0,4,1,4
1099598500000  =   2^5 5^6 7 11 13^4   :   5,0,6,1,1,4
1099535990784  =   2^14 3 7^5 11^3   :   14,1,0,5,3,0
1099511627776  =   2^40   :   40,0,0,0,0,0

1099511627775  is target n 

===========================================================