Covering natural numbers with geometric progressions

/*
 Helper program for https://oeis.org/A309095
 Find the smallest number of geometric progressions that cover the numbers 1, 2, ... N
 https://math.stackexchange.com/questions/1385991/what-is-known-about-the-minimal-number-fn-of-geometric-progressions-needed-t?lq=1

 Dmitry Kamenetsky, 17th July 2019
*/


import java.util.*;


public class CoveringGP
{
    static int N;
    static List<GP> GPs = new ArrayList<GP>();

    public static void main(String[] args)
    {
        if (args.length!=1)
        {
            System.out.println("usage: java CoveringGP N");
            System.out.println("Finds the smallest number of geometric progressions that cover the numbers 1, 2, ..., N");
            System.out.println("Only prints progressions with 3 or more terms, the remaining numbers can be covered with one progression for each two numbers");
            System.exit(0);
        }
        N=Integer.parseInt(args[0]);


        generateGPSrational();
        solve();
    }

    public static void generateGPSrational()
    {
        //first,second
        boolean[][] seen=new boolean[N+1][N+1];

        System.out.println("progressions with 3 or more terms:");

        for (int i=1; i<=N; i++)
        {
            for (int k=i+1; k<=N; k++)
            {
                if (seen[i][k]) continue;


                int div=getMinDivisor(i,k);
                if (div==-1) continue;
                int mult=k/(i/div);

                int cur=i;
                GP gp=new GP();

                while(true)
                {
                    gp.a.add(cur);

                    if (cur%div!=0) break;
                    cur/=div;
                    cur*=mult;
                    if (cur>N) break;
                }

                if (gp.a.size()>=3)
                {
                    for (int a : gp.a) System.out.print(a+" ");
                    System.out.println();

                    GPs.add(gp);

                    //update seen
                    for (int p=0; p<gp.a.size(); p++)
                        for (int q=p+1; q<gp.a.size(); q++)
                            seen[gp.a.get(p)][gp.a.get(q)]=true;
                }
            }
        }

        System.out.println("total number of progressions: "+GPs.size()+"\n");
    }

    //b>a
    public static int getMinDivisor(int a, int b)
    {
        for (int i=1; i<=Math.min(a,b); i++)
            if (a%i==0 && b%i==0 && b%(a/i)==0) return i;
        return -1;
    }


    public static void solve()
    {
    int n=GPs.size();
    int maxChanges=5;
    int bestScore=Integer.MAX_VALUE;

    if (n==0)
    {
        System.out.println("progressions needed: "+(N+1)/2);
        return;
    }


    boolean[] bestA=new boolean[n];
    for (int i=0; i<n; i++) bestA[i]=(Math.random()<0.5);

    boolean[] a=new boolean[n];

    while(true)
    {
      for (int i=0; i<n; i++) a[i]=bestA[i];

      int changes=(int)(Math.random()*maxChanges+1);
      for (int i=0; i<changes; i++)
      {
        int pos=(int)(Math.random()*n);
        a[pos]=!a[pos];
      }

      int score=score(a);
      if (score<=bestScore)
      {
        if (score<bestScore && score<=N/2)
        {
          System.out.println("progressions needed: "+score);
          print(a);
          System.out.println("progressions needed: "+score);
          System.out.println();
        }
        bestScore=score;

        for (int i=0; i<n; i++) bestA[i]=a[i];
      }
    }
    }


    //computes number of sets needed to cover all numbers
    public static int score(boolean[] a)
    {
    Set<Integer> covered=new HashSet<Integer>();    //integers that are covered

    int sets=0;
    for (int i=0; i<GPs.size(); i++)
      if (a[i])
      {
        sets++;
        for (int k : GPs.get(i).a) covered.add(k);
      }

    int missing=N-covered.size();
    int extraSets=(missing+1)/2;      //extra sets can cover up to 2 numbers each

    return sets+extraSets;
  }


  public static void print(boolean[] a)
  {
    for (int i=0; i<GPs.size(); i++)
    {
      if (a[i])
      {
        GPs.get(i).print();
        System.out.print(", ");
      }
    }
    System.out.println();
  }



    static class GP
    {
        List<Integer> a;
        public GP()
        {
            a=new ArrayList<Integer>();
        }

        void print()
        {
      System.out.print("(");
      for (int i=0; i<a.size(); i++)
      {
        System.out.print(a.get(i));
        if (i<a.size()-1) System.out.print(",");
      }
      System.out.print(")");
        }
    }
}