-- File OSequences.CoCoA5
-- Last update: July 30, 2025

-- by Francesca Cioffi

-- AIM:
-- Compution of the number of all O-Sequences with a given multiplicity d

-- Algorithm: 
-- see Algorithm 1 in the paper "Counting finite O-sequences of a given multiplicity" by F. Cioffi and M. Guida

define OSequenze(D)
  StartTime := CpuTime();

  N:=4;
  O:=[1,1,2,3];
  A:=[0,0,1,1];
  B:=[[[2]],[[3]],[]];

  H2:=1;
  H1:=2;
  H:=3;

  While N<D Do
    N:=N+1;
    L1:=Len(B[H1]);
    B[H]:=[ Concat(B[H2,K],[2]) | K In 1..A[N-2] ];
    L:=A[N-2];
    For K:=1 To L1 Do
      S:=Len(B[H1,K]);

      If S=1 Then
        B[H]:=Concat(B[H],[[B[H1,K,1]+1]]);
        L:=L+1;
      Else
        If B[H1,K,S-1]>B[H1,K,S] Then
          B[H]:=Concat(B[H],[B[H1,K]]);
          L:=L+1;
          B[H,L,S]:=B[H,L,S]+1;
        Else
          BE:=BinExp(B[H1,K,S-1],S-1);
          E:=EvalBinExp(BE,1,1);
          If B[H1,K,S]<E Then
            B[H]:=Concat(B[H],[B[H1,K]]);
            L:=L+1;
            B[H,L,S]:=B[H,L,S]+1;
          EndIf;
        EndIf;
      EndIf;
    EndFor;
    O:=Concat(O,[O[N-1]+L]);
    A:=Concat(A,[L]);
Print"O[", N ,"]=", O[N], ", A[", N, "]=", A[N], NewLine();

    App:=H2;
    H2:=H1;
    H1:=H;
    H:=App;
  EndWhile;

  EndTime := CpuTime();
  TimeTaken := EndTime - StartTime;
  PrintLn "Computation time: ", DecimalStr(TimeTaken);

  Return O;
EndDefine;