subroutine FindCounterExamples(uLimit)
integer(INT64), intent(in) :: uLimit
logical :: found
integer(INT64) :: maxRoot, m
integer(INT64) :: iterations
integer(INT64) :: a, b, c, d, n
integer(INT64) :: sum
real(REAL64) :: seconds
integer(INT64), rank(1), allocatable :: powers
integer(INT64), rank(1), allocatable :: roots
type(TTimer) :: timer
call timer % Start()
call DisplayHeader(uLimit)
maxRoot = LargestRoot(uLimit)
m = HashTableSize(uLimit)
call BuildFifthPowers(maxRoot, powers)
call BuildFifthRoots(maxRoot, m, powers, roots)
iterations = 0
do a = 1, uLimit
do b = a, uLimit
do c = b, uLimit
do d = c, uLimit
iterations = iterations + 1
sum = powers(a) + powers(b) + powers(c) + powers(d)
call TestFifthPower(sum, powers, roots, n, found)
if (found) then
call DisplayResult(a, b, c, d, n)
end if
end do
end do
end do
end do
call timer % Stop()
seconds = timer % Elapsed()
call DisplaySummary(iterations, seconds)
end subroutine FindCounterExamples
This is the main loop. Hopefully the gist is fairly clear. I'll endeavour to attach the Visual Studio solution so you can see all the details, and maybe leave in my comments at the top of the file EulersConjecture.f90 that records a summary of the changes I made.
I call a couple of subroutines before the loops to set up some data that is used in the main loop. The 5th powers are all pre-computed and stored in powers, e.g powers(i) = i**5. Similarly, roots is a hash table that is the inverse of powers, e.g. given an integer 5th power i**5, use roots to recover the value i. This is used in the subroutine TestFifthPowers to determine if the sum of 5th powers is itself a 5th power. The function HashTableSize is used to determine a smallish hash table size that also ensures there are no hash collisions.
Finally, the subroutine TestFifthPowers also makes use of the number theorist's trade secret posted above by (at that time) Mr Mecej4, to avoid testing numbers that cannot be 5th powers.
I tried a couple of additional things that are not present in the attached code.
- A running total of the 5th power partial sums in the outer loops. This saved an additional 0.2s
- Inlining the functionality from the subroutine TestFifthPower. This saved an additional 0.4s.
But it made the source code too ugly, so I reverted those changes.
Here are the details for TestFifthPowers...
subroutine TestFifthPower(n, powers, roots, i, found)
! Test if n is a 5th power.
! If it is, return the value i such that i**5 = n.
integer(INT64), intent(in) :: n
integer(INT64), rank(1), intent(in) :: powers
integer(INT64), rank(1), intent(in) :: roots(0:)
integer(INT64), intent(out) :: i
logical, intent(out) :: found
integer(INT64) :: m
integer(INT32) :: k
! Early exit. If n does not meet the requirements for a 5th power, no need to test further.
if (.not. IsPotentialFifthPower(n)) then
found = .false.
return
end if
! Use the roots lookup table to get a candidate root, then test it.
m = Size(roots)
k = Modulo(n, m)
i = roots(k)
found = (powers(i) == n)
end subroutine TestFifthPower
