Bug(s) in my Ada program for Number Sequence (OEIS:A033919 - Odd k for which k+2^m is composite for all m < k) Rosetta Code

Hi;

Bug(s) in my Ada program for Number Sequence (OEIS:A033919 - Odd k for which k+2^m is composite for all m < k) Rosetta Code

Here’s my code. Please show me where I screwed up!

-- Has bug(s)!

-- Rosetta Code Task written in Ada
-- Smallest number k such that k+2^m is composite for all m less than k
-- https://rosettacode.org/wiki/Smallest_number_k_such_that_k%2B2%5Em_is_composite_for_all_m_less_than_k
-- loosely translated from the Python solution
-- November 2024, R. B. E.

pragma Ada_2022;
with Ada.Text_IO; -- use Ada.Text_IO;
with Ada.Integer_Text_IO; -- use Ada.Integer_Text_IO;
with Ada.Numerics.Big_Numbers.Big_Integers; use Ada.Numerics.Big_Numbers.Big_Integers;

procedure Smallest_Number_K is

  function Is_Prime (N : in Big_Integer) return Boolean is
    Big_0 : Big_Natural := To_Big_Integer (0);
    Big_2 : Big_Natural := To_Big_Integer (2);
    Big_3 : Big_Natural := To_Big_Integer (3);
    Big_Temp : Big_Natural := To_Big_Integer (5);
  begin
    if N < Big_2 then
      return False;
    end if;
    if N mod Big_2 = Big_0 then
      return N = Big_2;
    end if;
    if N mod Big_3 = Big_0 then
      return N = Big_3;
    end if;
    while Big_Temp * Big_Temp <= N loop
      if N mod Big_Temp = Big_0 then
        return False;
      end if;
      Big_Temp := Big_Temp + Big_2;
      if N mod Big_Temp = Big_0 then
        return False;
      end if;
      Big_Temp := Big_Temp + 4;
    end loop;
    return True;
  end Is_Prime;

  type Powers_of_Two_Table is array (0..5200) of Big_Positive; -- 5200 is just a rough upper limit guess of how many I need
  Powers_of_Two : Powers_of_Two_Table;

  procedure Load_Powers_of_Two (Powers_of_Two : in out Powers_of_Two_Table) is
  begin
    for I in Powers_of_Two'Range loop
      if I = 0 then
        Powers_of_Two (I) := To_Big_Integer (1);
      elsif I = 1 then
        Powers_of_Two (I) := To_Big_Integer (2);
      else
        Powers_of_Two (I) := Powers_of_Two (I-1) * To_Big_Integer (2);
      end if;
    end loop;
  end Load_Powers_of_Two;

  procedure Show_Powers_of_Two (Powers_of_Two : in Powers_of_Two_Table) is
  begin
    for I in Powers_of_Two'Range loop
      Ada.Text_IO.Put_Line (To_String (Powers_of_Two (I)));
    end loop;
  end Show_Powers_of_Two;

  function Is_A033919 (Powers_of_Two : in Powers_of_Two_Table; K : in Positive) return Boolean is
    N : Big_Positive;
  begin
    if K = 1 then
      return False;
    else
      for M in 1..K loop
        N := Powers_of_Two (M) + To_Big_Integer (K);
        Ada.Text_IO.Put ("DEBUG: (function Is_A033919) : N is ");
        Ada.Text_IO.Put_Line (To_String (N));
        if Is_Prime (N) then
          return False;
        end if;
      end loop;
      return True;
    end if;
  end Is_A033919;

  Sequence_Number : Natural := 0;
  Max_Sequence_Number : Positive := 5;
  I : Positive := 1;

begin
  Load_Powers_of_Two (Powers_of_Two); 
--  Show_Powers_of_Two (Powers_of_Two);
  loop
    Ada.Text_IO.Put ("DEBUG: (main program): I is ");
    Ada.Integer_Text_IO.Put (I, 0);
    Ada.Text_IO.New_Line;
    if Is_A033919 (Powers_Of_Two, I) then
      Max_Sequence_Number := Max_Sequence_Number + 1;
      Ada.Text_IO.Put ("*****An answer was found!  ");
      Ada.Integer_Text_IO.Put (I, 5);
--      Ada.Text_IO.Put (" ");
      Ada.Text_IO.New_Line;
    end if;
    exit when Sequence_Number >= Max_Sequence_Number;
    I := I + 2;
  end loop;
end Smallest_Number_K;

Thank you!
R. B. E. (Retired Build Engineer)

Hi R.B.E,

Shouldn’t this line be using Sequence_Number instead of the Max? Otherwise the exit when condition will never be true…

I am rewriting your code to use slightly newer Ada syntax which I think makes things cleaner :slight_smile:

Best,
Fer

1 Like

In the Is_Prime function

Isn’t this while loop wrong? Shouldn’t the condition be somewhat backwards? Like: Big_Temp < N.

For example, if in the input N is 7, then your code will produce initially 5 * 5 <= 7 which leads to an exit and then it returns True, but the same happens if I feed an 15. That would return that 15 is a prime number, which it is not :slight_smile:

Edit: for very large numbers, such as 1001, then the condition initially is 5 * 5 <= 1001 which is always false, therefore the while loop is not executed and 10001 is marked as a prime.

You only need to check up to Sqrt (N), because any successful candidate greater than that would have been the quotient of a smaller divisor.

15 is divisible by 3, so wouldn’t enter the loop, nor would 21. 17, 19, and 23 wouldn’t enter the loop either, and be declared prime.

Why is Big_Temp incremented by 4?

Sadly Big_Ints do not have Sqrt declared for them… So it cannot be used (and I am not going to implement it).

To be honest, I have been hacking on this problem the entire morning. It is great fun since I had a few hours just for this…

I think I have a perfectly working program but… It seems to get stuck with Big_Ints requiring more and more memory and some exceptions taking place… sight…

Okay, so here is what I am seeing… (I will post my code in the following post).

From 1 to 286, the execution of the code is extremely quick… But then when the number being checked is 287, it takes like 30 seconds only for it… But then, the next numbers are extremely quick to compute (until we get to the actual first A033919 sequence number).

We could say that the reason things are this way is because we need to check for more primes, but that is not the reason… The runtime cost of Big_Ints suddenly explodes in deterministic ways (at least I can reproduce it always with the same values).

While debugging I saw some exception code being raised when doing simple stuff…

ada.numerics.big_numbers.big_integers.to_big_integer (arg=arg@entry=287) at a-nbnbin.adb:154
warning: 154    a-nbnbin.adb: No such file or directory
(gdb) 
155     in a-nbnbin.adb
(gdb) 
ada.exceptions.triggered_by_abort () at a-except.adb:1850
warning: 1850   a-except.adb: No such file or directory
(gdb) 
1851    in a-except.adb
(gdb) 
system.soft_links.get_current_excep_nt () at s-soflin.adb:162
warning: 162    s-soflin.adb: No such file or directory
(gdb) 
ada.exceptions.triggered_by_abort () at a-except.adb:1854
warning: 1854   a-except.adb: No such file or directory
(gdb) 
ada.exceptions.exception_identity (x=...) at a-except.adb:932
932     in a-except.adb
(gdb) 
933     in a-except.adb
(gdb) 
ada.exceptions.triggered_by_abort () at a-except.adb:1855
1855    in a-except.adb
(gdb) 
system.soft_links.abort_defer_nt () at s-soflin.adb:53
warning: 53     s-soflin.adb: No such file or directory
(gdb) 
system.soft_links.abort_undefer_nt () at s-soflin.adb:68
68      in s-soflin.adb
(gdb) 
ada.numerics.big_numbers.big_integers.to_big_integer (arg=arg@entry=287) at a-nbnbin.adb:155
warning: 155    a-nbnbin.adb: No such file or directory

Is this expected? Are exceptions being used to detect the need of more memory allocation for some numbers?

Here is my current code:

--  Rosetta Code Task written in Ada
--  Smallest number k such that k+2^m is composite for all m less than k
--  https://rosettacode.org/wiki/Smallest_number_k_such_that_k%2B2%5Em_is_composite_for_all_m_less_than_k
--  loosely translated from the Python solution
--  November 2024, R. B. E. and Fernando Oleo Blanco

pragma Ada_2022;
pragma Debug_Policy (Off);

with Ada.Text_IO; -- use Ada.Text_IO;
with Ada.Integer_Text_IO; -- use Ada.Integer_Text_IO;
with Ada.Numerics.Big_Numbers.Big_Integers; use Ada.Numerics.Big_Numbers.Big_Integers;

procedure A033919
  with SPARK_Mode => On
is

   function Is_Prime (N : Big_Positive) return Boolean
   is
      Big_Temp : Big_Positive := 7;
   begin

      if N mod 2 = 0 then
         return N = 2;
      end if;

      if N mod 3 = 0 then
         return N = 3;
      end if;

      if N mod 5 = 0 then
         return N = 5;
      end if;

      while Big_Temp < N / 2 loop
         if N mod Big_Temp = 0 then
            return False;
         end if;
         Big_Temp := Big_Temp + 2;
      end loop;
      return True;

   end Is_Prime;

   subtype Big_Prime is Big_Positive
     with Dynamic_Predicate => Is_Prime (Big_Prime);

   --  The following subtype is not valid as Big_Positive cannot be used in the `for all` range
   --  subtype Big_Prime is Big_Positive
   --     with Dynamic_Predicate => (for all Divisor in 2 .. Big_Prime / 2 => Big_Prime mod Divisor /= 0);

   Upper_Table_Bound : constant Positive := 5200; -- R.B.E: 5200 is just a rough upper limit guess of how many I need
                                                  --  Irvise: this bound will not be enough for the larger numbers.
   
   type Powers_of_Two_Table is array (Positive'First .. Upper_Table_Bound) of Big_Positive -- Changed based index from 0 to 1, that simplifies things
     with Dynamic_Predicate => (for all I in Powers_Of_Two_Table'Range => Powers_Of_Two_Table (I) = To_Big_Integer (2)**I);

   Powers_of_Two : constant Powers_of_Two_Table := [for I in Powers_of_Two_Table'Range => To_Big_Integer (2)**I]; -- We initialise the table and make it constant

   procedure Show_Powers_of_Two (Powers_of_Two : Powers_of_Two_Table) is
   begin
      for I of Powers_of_Two loop
         Ada.Text_IO.Put_Line (I'Image);
      end loop;
   end Show_Powers_of_Two;

   function Is_A033919 (K : Positive) return Boolean is
      N : Big_Positive;
      M : Positive := Powers_Of_Two_Table'First;
   begin
      while M < K and then M < Powers_Of_Two_Table'Last loop
         N := Powers_of_Two (M) + To_Big_Integer (K);
         pragma Debug (Ada.Text_IO.Put_Line("Iteration " & M'Image & " for number " & K'Image));
         pragma Debug (Ada.Text_IO.Put_Line ("DEBUG: (function Is_A033919) : N is " & To_String (N)));
         if Is_Prime (N) then
            return False;
         end if;
         M := M + 1;
      end loop;
      return True;
   end Is_A033919;
   
   subtype Odd is Positive with Dynamic_Predicate => Odd mod 2 /= 0;
   Sequence_Number : Odd;
   Max_Sequence_Number : constant Positive := 800; -- First integer must be 773
   I : Odd := 3;

begin
   pragma Debug (Show_Powers_of_Two (Powers_of_Two));
   loop
      pragma Debug (Ada.Text_IO.Put ("DEBUG: (main program): I is "));
      pragma Debug (Ada.Integer_Text_IO.Put (I, 0));
      pragma Debug (Ada.Text_IO.New_Line);
      Ada.Text_IO.Put ("DEBUG: (main program): I is ");
      Ada.Integer_Text_IO.Put (I, 0);
      Ada.Text_IO.New_Line;
      if Is_A033919 (I) then
         Sequence_Number := I; -- 
         Ada.Text_IO.Put ("*****An answer was found!  ");
         Ada.Integer_Text_IO.Put (Sequence_Number, 5);
         Ada.Text_IO.New_Line;
      end if;
      exit when I >= Max_Sequence_Number;
      I := I + 2;
   end loop;
end A033919;

The first number that makes Is_A033919 explode is 287. You can check this by running the program in gdb and setting the breakpoint break A033919.adb:94 if I = 287 and then stepping the program.

Here is the valgrind --tool=calgrind output visualized with kcachegrind. As it can be seen, exceptions are being called a brutal amount of times. There is also a brutal amount of allocation…

Edit: this version was compiled using alr build --development, so basically in debug mode and checks enabled.

And this is compiled with -O3 -flto -gnatp… Basically no change, so the slowdown is not caused by Ada’s checks…

No, but x < sqrt (n) has the same result as x * x < n

1 Like

Irvise facepalms hard…

Oh, wow… I just applied this little change to the code and it is orders of magnitude faster!!! And it is not just the testing of primes that has become smaller (as now less tests are performed), the allocations have become much lower!

Is Big_Num division that brutally expensive??

However, even with this change, the code still gets stuck severely in

Iteration  195 for number  773
DEBUG: (function Is_A033919) : N is  50216813883093446110686315385661331328818843555712276103941

Same here.

Running under lldb (no gdb, this is a Mac), doing C-c/bt/c several times, it’s stuck in Is_Prime; on one occasion I saw an execption call to Ada.Exceptions.Triggered_By_Abort - WTF?

I suspect it’s in System.Generic_Bignums.Div_Rem at Algorithm D: the comment is

      --  The complex full multi-precision case. We will employ algorithm
      --  D defined in the section "The Classical Algorithms" (sec. 4.3.1)
      --  of Donald Knuth's "The Art of Computer Programming", Vol. 2, 2nd
      --  edition. The terminology is adjusted for this section to match that
      --  reference.

      --  We are dividing X.Len digits of X (called u here) by Y.Len digits
      --  of Y (called v here), developing the quotient and remainder. The
      --  numbers are represented using Base, which was chosen so that we have
      --  the operations of multiplying to single digits (SD) to form a double
      --  digit (DD), and dividing a double digit (DD) by a single digit (SD)
      --  to give a single digit quotient and a single digit remainder.

      --  Algorithm D from Knuth

so it’s not entirely outside the realms of possibility that there might be an error here.

(I would have posted a link to gcc-mirror at github, but the libgnat directory listing has been limited at 1000 entries)

I personally try to always use the main GCC-Git repo specifically due to this issue :slight_smile:

I remember reading or watching a video from AdaCore and how they modeled the Algorithm D from Knuth in SPARK and how they were able to detect some of the issue there. Knuth released a revised version a few years later and that is the one that is implemented in Big_Num, so it should be fully correct AFAIK…

I am still debugging things here. It has been a while since I went on a nasty bug-hunt :smiley:

From a-nbnbin.adb

   -----------------
   -- From_String --
   -----------------

   function From_String (Arg : String) return Valid_Big_Integer is
      procedure Scan_Decimal
        (Arg : String; J : in out Natural; Result : out Big_Integer);
      --  Scan decimal value starting at Arg (J). Store value in Result if
      --  successful, raise Constraint_Error if not. On exit, J points to the
      --  first index past the decimal value.

      ------------------
      -- Scan_Decimal --
      ------------------

      procedure Scan_Decimal
        (Arg : String; J : in out Natural; Result : out Big_Integer)
      is
         Initial_J : constant Natural := J;
         Ten       : constant Big_Integer := To_Big_Integer (10);
      begin
         Result := To_Big_Integer (0);

         while J <= Arg'Last loop
            if Arg (J) in '0' .. '9' then
               Result :=
                 Result * Ten + To_Big_Integer (Character'Pos (Arg (J))
                                                  - Character'Pos ('0'));

            elsif Arg (J) = '_' then
               if J in Initial_J | Arg'Last
                 or else Arg (J - 1) not in '0' .. '9'
                 or else Arg (J + 1) not in '0' .. '9'
               then
                  raise Constraint_Error with "invalid integer value: " & Arg;
               end if;
            else
               exit;
            end if;

            J := J + 1;
         end loop;
      end Scan_Decimal;

      Result : Big_Integer;

   begin
      --  First try the fast path via Long_Long_Long_Integer'Value

      Set_Bignum (Result, To_Bignum (Long_Long_Long_Integer'Value (Arg)));
      return Result;

   exception
      when Constraint_Error =>
         --  Then try the slow path

Yup, exceptions are used in order to perform handling of “normal” code… This is not great, it is not too bad either… I picked this function as it takes about 30% of all execution time from the program. And of course, now it makes sense that exception handling is taking so long: most numbers will not fit in Long_Long_Long_Integer

It does not help that Big_Nums are implemented via access types/pointers… Finding their true value with gdb is a failed battle for now… But… I found something potentially interesting… I wanted to know if Big_Temp was changing value (aka, being reallocated) during the prime check loop:

      Big_Temp := 7;
      while Big_Temp * Big_Temp <= N loop
         if N mod Big_Temp = 0 then
            return False;
         end if;
         Big_Temp := Big_Temp + 2;
      end loop;
      return True;

So I did a watch Big_Temp in gdb which would indicate when the value of the System.Address (the underlying data in a Big_Int; aka pointer) would change. Here is what I found:

(gdb) n 1

Hardware watchpoint 5: Big_Temp

Old value = (value => (c => (system.address) 0x55d600))
New value = (value => (c => (system.address) 0x545860))
0x000000000040ce1d in ada__numerics__big_numbers__big_integers__big_integerDA ()
(gdb) 
Single stepping until exit from function ada__numerics__big_numbers__big_integers__big_integerDA,
which has no line number information.
a033919.is_prime (n=...) at a033919.adb:38
38            while Big_Temp * Big_Temp <= N loop
(gdb) 
39               if N mod Big_Temp = 0 then
(gdb) 
42               Big_Temp := Big_Temp + 2;
(gdb) 

Hardware watchpoint 5: Big_Temp

Old value = (value => (c => (system.address) 0x545860))
New value = (value => (c => (system.address) 0x0))
0x000000000040ce5f in ada__numerics__big_numbers__big_integers__big_integerDF ()
(gdb) 
Single stepping until exit from function ada__numerics__big_numbers__big_integers__big_integerDF,
which has no line number information.

Hardware watchpoint 5: Big_Temp

Old value = (value => (c => (system.address) 0x0))
New value = (value => (c => (system.address) 0x55d600))
0x0000000000408440 in a033919.is_prime (n=...) at a033919.adb:42
42               Big_Temp := Big_Temp + 2;
(gdb) 

Hardware watchpoint 5: Big_Temp

Old value = (value => (c => (system.address) 0x55d600))
New value = (value => (c => (system.address) 0x545860))
0x000000000040ce1d in ada__numerics__big_numbers__big_integers__big_integerDA ()
(gdb) 
Single stepping until exit from function ada__numerics__big_numbers__big_integers__big_integerDA,
which has no line number information.
a033919.is_prime (n=...) at a033919.adb:38
38            while Big_Temp * Big_Temp <= N loop
(gdb) 
39               if N mod Big_Temp = 0 then
(gdb) 
42               Big_Temp := Big_Temp + 2;
(gdb) 

Hardware watchpoint 5: Big_Temp

Old value = (value => (c => (system.address) 0x545860))
New value = (value => (c => (system.address) 0x0))
0x000000000040ce5f in ada__numerics__big_numbers__big_integers__big_integerDF ()

Notice the lines: New value = (value => (c => (system.address) 0x0))… That means that, at least temporalily, Big_Temp is being set to null… So… What is happening to the data it held? If this is not a null issue, it is being copied somewhere, deallocated, reallocated and copied back… The fact that Big_Temp is being assigned and reassinged to the same set of addresses indicates such a thing… But I am not entirely sure about this…

[a few minutes later…]

Okay, so, here is the thing. I did a b a033919.adb:39 if Big_Temp.Value.C = System.Address(0) in gdb and it never triggered… I checked with some p Big_Int and indeed, the address is never null in the program context. GDB does detect deallocation and reallocation inside the libraries, but that never happens inside the program. So there is no null issue here…


EDIT: for transparency, I am debugging using: gnatmake -s -Og -ggdb -gnata -gnateE -fstack-check -fstack-usage a033919.adb -o a033919 -march=native -static -bargs -static -largs -static
I have also tested a release build with gnatmake -s -O3 -gnatp -flto a033919.adb -o optimized_a033919 -march=native -static -bargs -static -largs -static

It does seem that testing for prime in the

Iteration  195 for number  773
DEBUG: (function Is_A033919) : N is  50216813883093446110686315385661331328818843555712276103941

case is taking very long because the number is actually very difficult to factor… But that is just a guess…


EDIT 2:

The factor for the number 37778931862957161710341 is 88160341. Why am I saying this? Because, through some “printf” debugging, I saw that the program was taking quite long to find the factor of that number and continue with the rest. This indicates that it took a while to find the factor, 88160341. It should not be a surprise as that requires 88 million Big_Num operations. I am going to let the program run for a bit longer and see if it can find the factor of 50216813883093446110686315385661331328818843555712276103941

Looking at the Ada.Numerics.Big_Numbers.Big_Integers I wonder why there is no short operation? Normally an implementation of indefinite integers has

function "+" (L : Valid_Big_Integer; R : Unsigned) return Valid_Big_Integer;
function "-" (L : Valid_Big_Integer; R : Unsigned) return Valid_Big_Integer;
function "*" (L : Valid_Big_Integer; R : Unsigned) return Valid_Big_Integer;
function "/" (L : Valid_Big_Integer; R : Unsigned) return Valid_Big_Integer;
etc

These operations are normally much faster and primary candidates for using in Image (To_String) and Value (From_String) implementations.

Then the implementation of From_String is IMO bad. It should start with accumulating Long_Long_Long_Integer until (Long_Long_Long_Integer’Last - 9) / 10. reached. After that it must convert the accumulator to Big_Integer and continue without exceptions and starting over. You can implement it by yourself.

A more advanced version would parse log (Long_Long_Long_Integer’Last) chunks (the number of decimal places fitting into Long_Long_Long_Integer) and accumulate them in the Big_Integer result. The algorithm of accumulation is same with the base 10 ** (log (Long_Long_Long_Integer’Last)).

Yes, the Sequence_Number line is incorrect; thank you for catching a very elementary mistake. Fixed.

R. B. E.

I am no Ada expert and neither an AdaCore engineer, but as far as I saw in the LRM, it does not specify/require this operations. They went with the more generic/general ones…

I want to see how far baseline Ada can be pushed :slight_smile: If I need more performance, I will use gmp. Which, btw, is implemented for Big_Nums in GCC, but it is not enabled it seems…

And as an extra, the current factor being considered for 50216813883093446110686315385661331328818843555712276103941 in my current run is 2950000005. Therefore it seems that there is no issue with my code… It is just really, really, really slow…

After using a few websites to calculate prime factor, here is what I found:

The website Prime Factors Calculator does work (tested with 37778931862957161710341) and it is really fast. At least faster than my Ada code. The other websites I tested with 50216813883093446110686315385661331328818843555712276103941 died.

The one linked above is considering primes up-to 133 billion, for the aforementioned number, and still has not found an answer after 13 minutes of execution. My code, after even a longer time is just around 10_090_000_005. This means that my code will still take several hours and will most-likely still not find an answer… So… I am going to say that my code is somewhat correct but I will not see it run to completion (not even for the first sequence number).

Here is the final code that I was running (compiled with the performant flags):

--  Rosetta Code Task written in Ada
--  Smallest number k such that k+2^m is composite for all m less than k
--  https://rosettacode.org/wiki/Smallest_number_k_such_that_k%2B2%5Em_is_composite_for_all_m_less_than_k
--  loosely translated from the Python solution
--  November 2024, R. B. E. and Fernando Oleo Blanco

pragma Ada_2022;
--  pragma Debug_Policy (Off);

with Ada.Text_IO; -- use Ada.Text_IO;
with Ada.Integer_Text_IO; -- use Ada.Integer_Text_IO;
with Ada.Numerics.Big_Numbers.Big_Integers; use Ada.Numerics.Big_Numbers.Big_Integers;

procedure A033919
  with SPARK_Mode => On
is

   function Is_Prime (N : Big_Positive) return Boolean
     with Inline
   is
      --  Make the Big_Temp the input and then overwrite to see if there is only one allocation that takes place
      Big_Temp : Big_Positive := N; -- It does not seem to be helping... Maybe when we do Big_Temp := 7 below GNAT cleans the memory...
      Counter : Long_Long_Long_Integer := 1;
   begin
            
      if N mod 2 = 0 then
         return N = 2;
      end if;

      if N mod 3 = 0 then
         return N = 3;
      end if;

      if N mod 5 = 0 then
         return N = 5;
      end if;
      
      Big_Temp := 7;
      Ada.Text_IO.Put_Line("Testing for prime" & N'Image);
      while Big_Temp * Big_Temp <= N loop
         if N mod Big_Temp = 0 then
            return False;
         end if;
         Big_Temp := Big_Temp + 2;
         Counter := Counter + 1;
         if Counter mod 10_000_000 = 0 then
            Ada.Text_IO.Put_Line("Current Big_Temp value is " & Big_Temp'Image);
         end if;
      end loop;
      return True;

   end Is_Prime;

   subtype Big_Prime is Big_Positive
     with Dynamic_Predicate => Is_Prime (Big_Prime);

   --  The following subtype is not valid as Big_Positive cannot be used in the `for all` range
   --  subtype Big_Prime is Big_Positive
   --     with Dynamic_Predicate => (for all Divisor in 2 .. Big_Prime / 2 => Big_Prime mod Divisor /= 0);

   Upper_Table_Bound : constant Positive := 5200; -- R.B.E: 5200 is just a rough upper limit guess of how many I need
                                                  -- Irvise: this bound will not be enough for the larger numbers.
   
   type Powers_of_Two_Table is array (Positive'First .. Upper_Table_Bound) of Big_Positive -- Changed based index from 0 to 1, that simplifies things
     with Dynamic_Predicate => (for all I in Powers_Of_Two_Table'Range => Powers_Of_Two_Table (I) = To_Big_Integer (2)**I);

   Powers_of_Two : constant Powers_of_Two_Table := [for I in Powers_of_Two_Table'Range => To_Big_Integer (2)**I]; -- We initialise the table and make it constant

   procedure Show_Powers_of_Two (Powers_of_Two : Powers_of_Two_Table) is
   begin
      for I of Powers_of_Two loop
         Ada.Text_IO.Put_Line (I'Image);
      end loop;
   end Show_Powers_of_Two;

   function Is_A033919 (K : Positive) return Boolean
     with Inline
   is
      N : Big_Positive;
      M : Positive := Powers_Of_Two_Table'First;
   begin
      while M < K and then M < Powers_Of_Two_Table'Last loop
         N := Powers_of_Two (M) + To_Big_Integer (K);
         pragma Debug (Ada.Text_IO.Put_Line("Iteration " & M'Image & " for number " & K'Image));
         pragma Debug (Ada.Text_IO.Put_Line ("DEBUG: (function Is_A033919) : N is " & To_String (N)));
         if Is_Prime (N) then
            return False;
         end if;
         M := M + 1;
      end loop;
      return True;
   end Is_A033919;
   
   subtype Odd is Positive
     with Dynamic_Predicate => Odd mod 2 /= 0;
   
   Sequence_Number : Odd;
   Max_Sequence_Number : constant Positive := 800; -- First integer must be 773
   I : Odd := 3;

begin
   pragma Debug (Show_Powers_of_Two (Powers_of_Two));
   loop
      --  pragma Debug (Ada.Text_IO.Put ("DEBUG: (main program): I is "));
      --  pragma Debug (Ada.Integer_Text_IO.Put (I, 0));
      --  pragma Debug (Ada.Text_IO.New_Line);
      Ada.Text_IO.Put ("DEBUG: (main program): I is ");
      Ada.Integer_Text_IO.Put (I, 0);
      Ada.Text_IO.New_Line;
      if Is_A033919 (I) then
         Sequence_Number := I; -- 
         Ada.Text_IO.Put ("*****An answer was found!  ");
         Ada.Integer_Text_IO.Put (Sequence_Number, 5);
         Ada.Text_IO.New_Line;
      end if;
      exit when I >= Max_Sequence_Number;
      I := I + 2;
   end loop;
end A033919;

Thanks @Ret_Build_Engineer for the challenge! I had a ton of fun. I missed programming (in Ada) :smiley: But I just “waisted” the entire day x) Still very worth it!

Oh, and you may notice SPARK_Mode => On! I initially wanted to create a SPARK prove for this sequence of numbers. However, I did not know that it would take so long to compute them! Either way, I really liked annotating types with Dynamic_Predicate!