Hi;
I am stubbornly running an Ada program using GNAT Big_Numbers with (obviously) a brute-force algorithm that has hidious performance. I don’t think I can blame this glacial slowness entirely on the Big_Number “wedging”; it must be a major flaw in my algorthm. It has been running for almost 38 hours. I suspect that it may take a couple more days. It is almost half-way complete (if the results are correct). The other entries that have tried the stretch goal are consuming 10-90 seconds to find 1,525,141 results. I have 532,952 results so far (assuming that the results are correct). This is the “stretch” goal. I have already posted an Ada solution for this task which is NOT the stretch goal.
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;
with Ada.Real_Time; use Ada.Real_Time;
procedure Primes_Whose_Sum_of_Digits_is_25 is
function Is_Prime (N : in Big_Positive) return Boolean is
Big_0 : Big_Integer := To_Big_Integer (0);
Big_2 : Big_Positive := To_Big_Integer (2);
Big_3 : Big_Positive := To_Big_Integer (3);
Temp : Big_Integer := To_Big_Integer (5);
begin
if N < Big_2 then
return False;
end if;
if N mod Big_2 = 0 then
return N = Big_2;
end if;
if N mod Big_3 = 0 then
return N = Big_3;
end if;
while Temp * Temp <= N loop
if N mod Temp = Big_0 then
return False;
end if;
Temp := Temp + Big_2;
if N mod Temp = Big_0 then
return False;
end if;
end loop;
return True;
end Is_Prime;
function Is_Sum_of_Digits_Equal_to_25 (N : Big_Positive) return Boolean is
Big_0 : Big_Integer := To_Big_Integer (0);
Big_10 : Big_Integer := To_Big_Integer (10);
Local_N : Big_Integer := N;
Sum : Natural := 0;
Current_Remainder : Natural;
begin
while Local_N > Big_0 loop
Current_Remainder := To_Integer (Local_N mod Big_10);
if Current_Remainder = 0 then
return False;
end if;
Sum := Sum + Current_Remainder;
Local_N := Local_N / Big_10;
end loop;
return Sum = 25;
end Is_Sum_of_Digits_Equal_to_25;
Prime_Count : Natural := 0;
-- Show the count of all such primes that do not contain any zeroes in the range:
-- (997 ≤ n ≤ 1,111,111,111,111,111,111,111,111).
Big_2 : Big_Positive := To_Big_Integer (2);
I : Big_Positive := To_Big_Integer (997);
Maximum_Prime_Candidate : Big_Positive := From_String ("1111111111111111111111111");
Start_Time, Stop_Time : Time;
Elapsed_Time : Time_Span;
begin
Start_Time := Clock;
loop
if Is_Sum_of_Digits_Equal_to_25 (I) then
if (Is_Prime (I)) then
Prime_Count := Prime_Count + 1;
Put ("DEBUG: I is ");
Put_Line (To_String (Arg => I));
if Prime_Count mod 10_000 = 0 then
Put (".");
end if;
end if;
end if;
I := I + Big_2;
exit when I >= Maximum_Prime_Candidate;
end loop;
New_Line;
Put ("There are ");
Put (Prime_Count, 0);
Put (" primes less than ");
Put (To_String (Arg => Maximum_Prime_Candidate));
Put_Line (" whose sum of digits is 25 and does not contain a zero.");
Stop_Time := Clock;
Elapsed_Time := Stop_Time - Start_Time;
Put_Line ("Elapsed time: " & Duration'Image (To_Duration (Elapsed_Time)) & " seconds");
New_Line;
end Primes_Whose_Sum_of_Digits_is_25;
My plan was to make sure that the results were correct and then try to optimize by tasking (take, perhaps, 1000 per task, how many concurrent tasks (?) and how to sum up the results from each task). Reading up on tasking now; as I haven’t used Ada tasking since when Ada 95 was very new…
Of course, there MUST be a permutation or something that is in the pattern of results that could/should reduce the number of calculations…
Thanks for any additional insights…
Retired Build Engineer
against all known primes 
). Then, before testing 
for primality with a large-scale method