title: Given primes and exponents, generating all possible integers smaller than N
body: <p>I am looking to write a function that, given a set of exponents and a set of primes, it would generate all possible integers that may be formed using primes from the given set, and raising them to exponents found in the given set of exponents, with the restriction that the integers may not exceed a limit <code>N</code>. The set of primes contains a number of elements not less than the number of elements in the exponents' set. All exponents have to be used, and they are not necessarily distinct. The set of primes is sorted, and so is the list of exponents, from lowest to biggest.</p>
  <p>For example, say our set of primes is <code>{11,19,29,31}</code>. The set of exponents is <code>{1,4}</code>, and <code>N = 20,000,000</code>. So, we're talking about products satisying <code>P = a^1*b^4</code>.</p>
  <p><code>P = 11^1 * 19^4 = 1,433,531</code></p>
  <p><code>P = 11^1 * 29^4 = 7,780,091</code></p>
  <p><code>P = 11^1 * 31^4 = 10,158,731</code></p>
  <p><code>P = 19^1 * 29^4 = 13,438,339</code></p>
  <p><code>P = 19^1 * 31^4 = 17,546,899</code></p>
  <p><code>P = 29^1 * 31^4 = 26,782,109</code> ---- discarded due to limit restriction</p>
  <p><code>P = 19^1 * 11^4 = 278,179</code></p>
  <p><code>P = 29^1 * 11^4 = 424,589</code></p>
  <p><code>P = 29^1 * 19^4 = 3,779,309</code></p>
  <p><code>P = 31^1 * 11^4 = 453,871</code></p>
  <p><code>P = 31^1 * 19^4 = 4,039,951</code></p>
  <p><code>P = 31^1 * 29^4 = 21,925,711</code> ---- discarded due to limit restriction</p>
  <p>Note that every prime may have any exponent, and it is not necessary for example that the lower prime would have the lower exponent, because exchanging the exponents between the primes would result in different integers. This is not the case however if the set of exponents were <code>{1,1}</code> because then exchanging them between any 2 primes would not change the result, I.E <code>11^1 * 31^1 = 31^1 * 11^1</code>.</p>
  <p>For my purposes, the set of exponents contains very few elements, about <code>5</code>, but <code>N</code> is very large, more than <code>10^13</code>, and the set of primes contains many primes, over <code>50,000</code> say. It is therefore challenging to create all possible integers efficiently.</p>
  <p>The code I have come up with uses recursion. It generates all possible such integers, keeping track of: an arraylist which represents the set of exponents, called <code>partition</code> , <code>used</code>=number of exponents used in our current product, <code>partitionIndex</code> = the index of the exponent we're going to use in the current function call, an arraylist of the primes we have used thus far - <code>primesUsed</code> (to avoid using the same prime twice in the product) and finally, <code>prod</code> = our current product. The recursion will stop when <code>used</code> is as big as our exponents list, meaning we have used all the exponents and our product is viable. Pruning is done when our current product is too big to multiply by any other prime number. Every viable integer is added to an arraylist of <code>products</code>. Here's the code:</p>
  <pre><code>import java.util.ArrayList;
  import java.util.Collections;
  import java.util.HashSet;
  import java.util.List;
  import java.util.Set;
  
  public class test3 {
  
      public static long N;
      public static long [] primes;
      public static ArrayList &lt;Long&gt; products;
      
      public static void main(String[] args) 
      {
          N = 20000000;
          primes = new long [] {11,19,29,31};
          products = new ArrayList &lt;Long&gt;();
          
          ArrayList &lt;Long&gt; partition = new ArrayList &lt;Long&gt;();
          partition.add(1L);
          partition.add(4L);
          
          generateProducts(partition , 0 , 0 , new ArrayList &lt;Long&gt;() , 1);
          
          //Set &lt;Long&gt; discardDups = new HashSet&lt;&gt;(products);   --- for list {1,4}, can be skipped.
          //products.clear();                                   --- but for {1,1} has to be used, otherwise there are duplicates
          //products.addAll(discardDups);
          
          Collections.sort(products);
          
          System.out.println(products);
          System.out.println(products.size());
      }
      
      public static void generateProducts (List &lt;Long&gt; partition , int used , int partitionIndex , ArrayList &lt;Long&gt; primesUsed , long prod)
      {
          if (used == partition.size())
          {
              products.add(prod);
              return;
          }
  
          for (int i = 0 ; i &lt; primes.length &amp;&amp; primes.length - i + 1 &gt;= partition.size() - partitionIndex &amp;&amp; prod * Math.pow(primes[i], partition.get(partitionIndex)) &lt;= N ; i++)
          {
              if (!primesUsed.contains(primes[i]))
              {
                  primesUsed.add(primes[i]);
                  generateProducts(partition , used + 1 , partitionIndex + 1 , primesUsed , (long) (prod * Math.pow(primes[i], partition.get(partitionIndex))));
                  primesUsed.remove(primesUsed.size() - 1);
              }
          }
      }
  
  }
  
  </code></pre>
  <p>The drawbacks of this function are:</p>
  <ol>
  <li><p>It generates many duplicates. Because the counter in the function starts from <code>0</code> everytime, and it checks we're not reusing any prime, then when the exponents are the same, it generates a duplicate, I.E it treats <code>11^1 * 31^1</code> and <code>31^1 * 11^1</code> differently.</p>
  </li>
  <li><p>The algorithm overall takes a very long time. Again, I assume, because the counter starts from 0 over and over.</p>
  </li>
  </ol>
  <p>I am well aware I can get rid of the duplicates using a <code>Set</code> but this is extremely time consuming. Also, keeping track of the highest prime index used and starting from it with every function call makes the algorithm faster, but then products with the bigger prime having the lower exponent are not generated.</p>
  <p>What I am interested in is a way to generate all such products efficiently. I am not sure if my code can be altered to it. If it can, then it should be able to generate all possible such integers, it should avoid generating duplicates in the first place, and the &quot;stopping&quot; conditions, or pruning, should be better to spare as many redundant function calls as possible.</p>
  <p>Perhaps another approach altogether is necessary, but the goal remains the same. I would appreciate any direction as to how to change my code to avoid duplicates in the first place without skipping any possible integer, and making it faster. If duplicates cannot be avoided, then atleast a direction how to reduce the amount of function calls. Any other approach to achieve the same goal is most welcome!</p>