There are several cases where this identity permutation happens, for n={2,3,5,6,10,15,30}. It does not happen for n=31 or 32, and it cannot happen for any larger value because mod(2**5,n)==32 in all those cases. I was thinking how to use that information, and it occurred to me that if you know ahead of time what mod(m**5,n) is for the target value, then you could start the m loop index at that value and increment by n each step. You know ahead of time that nothing in between can possibly match. So if you take n=30, the largest value, you could go through the m loop 30 times faster than normal.
Then it occurred to me that you don’t have to settle for just the identity permutation cases. You can take any n value for any of the other permutation cases. That little modn5.f90 code I posted earlier shows that many values of n could be used, even values over 1000. Those values would let you go through the m loop n times faster. If n is larger than l, then it allows you to test that single value and then exit the loop. Maybe this is cheating a little, but we know the smallest solution has i=144, so if we pick a value larger than 144, we are guaranteed to find that solution with a single pass through the m loop every time. This eliminates the binary search problem entirely. It just so happens that n=145, only one value beyond 144, results in a permutation mapping between mod(i,n) and mod(i**5,n). So the only problem left is to compute that permutation array ahead of time, and then proceed with the brute force search over j, k, and l as before. When I do that, I get these timings.
$ gfortran -O3 sum_conjecture3.F90
$ time a.out
i5 = 61917364224
133 110 84 27 144
real 0m0.016s
user 0m0.014s
sys 0m0.001s
These are Apple M2 times. Those are basically as good as any previous results, but the algorithm is aesthetically cleaner than, say the binary search versions. I also experimented a little with some of the other values, and they all result in good timings, so the general idea is sound. I also set findmax to values larger than 1, and the code continues to perform well for the larger solutions too. Here is the code.
program sum_conjecture
! sum_conjecture.f90
!
! 27^5 + 84^5 + 110^5 + 133^5 = 144^5
!
use, intrinsic :: iso_fortran_env, only: ik => int64
implicit none
integer, parameter :: nmax = 6208 ! mmax integer range to search.
integer, parameter :: findmax = 1 ! max number of solutions to find.
integer, parameter :: lk = selected_logical_kind(1) ! f2023 and later.
!integer, parameter :: lk = 1 ! logical kind with the smallest storage_size() value.
integer(ik) :: i5, sk, sl, diff
integer(ik) :: n5(nmax)
! nperm is not arbitrary, but there are many values that work.
! 10, 30, 42, 65, 87, 105, 130, 145, 249, 510, 709, 995 are some acceptable values.
integer, parameter :: nperm = 145
integer :: perm(0:nperm-1) ! integer m permutation array.
integer :: i, j, k, l, m, mapT11, mapT31, mmin, nfound
logical(lk), parameter :: t=.true., f=.false.
integer, parameter :: map_11(0:10) = [1,2,0,0,0,0,0,0,0,0,3] ! map T11={0,1,10} to a contiguous domain.
logical(lk), parameter :: exclude_k11(0:10,1:3) = reshape([ &
& f,f,f,t,t,t,t,t,t,f,f, & ! T11 = 0
& f,f,f,t,t,t,t,t,t,t,f, & ! T11 = 1
& f,f,t,t,t,t,t,t,t,f,f],& ! T11 = 10
& shape(exclude_k11) )
logical(lk), parameter :: exclude_l11(0:10,1:3) = reshape([ &
& f,f,t,t,t,t,t,t,t,t,f, & ! T11 = 0
& f,f,f,t,t,t,t,t,t,t,t, & ! T11 = 1
& f,t,t,t,t,t,t,t,t,f,f],& ! T11 = 10
& shape(exclude_l11) )
integer, parameter :: map_31(0:30) = &
& [1,2,0,0,0,3,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,6,0,0,0,7] ! map T11={0,1,5,6,25,26,30} to a contiguous domain.
logical(lk), parameter :: exclude_l31(0:30,1:7) = reshape([ &
& f,f,t,t,t,f,f,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,f,f,t,t,t,f, & ! T31 = 0
& f,f,f,t,t,t,f,f,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,f,f,t,t,t, & ! T31 = 1
& f,t,t,t,f,f,f,t,t,t,f,f,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,f, & ! T31 = 5
& f,f,t,t,t,f,f,f,t,t,t,f,f,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t, & ! T31 = 6
& f,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,f,f,t,t,t,t,f,f,f,t,t,t,f, & ! T31 = 25
& f,f,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,f,f,t,t,t,t,f,f,f,t,t,t, & ! T31 = 26
& f,t,t,t,f,f,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,t,f,f,t,t,t,f,f],& ! T31 = 30
& shape(exclude_l31) )
character(*), parameter :: cfmt = '(*(g0,1x))'
intrinsic :: int, mod
! set up the perm(:) permutation array.
perm = 0
do m = 1, nperm
k = mod(m*m,nperm) ! m*2
k = mod(k*k,nperm) ! m**4
k = mod(m*k,nperm) ! m**5
perm(k) = m ! perm(k) gives the lowest index m to match a given m**5 value.
enddo
!if ( any(perm==0) ) then
! print cfmt, 'invalid nperm results in perm(k)==0, nperm=', nperm
! error stop 1
!endif
nfound = 0
outer: do i = 1, nmax
i5 = int(i,ik)**5
n5(i) = i5
mapT11 = map_11(mod(i5,11_ik)) ! target modulus; T11 = 0, 1, or 10.
mapT31 = map_31(mod(i5,31_ik)) ! target modulus; T31 = 0, 1, 5, 6, 25, 26, or 30.
do j = 1, i
do k = 1, j
sk = n5(j) + n5(k)
if ( sk > i5 ) exit
if ( exclude_k11( mod(sk,11_ik), mapT11 ) ) cycle
do l = 1, k
sl = sk + n5(l)
diff = i5 - sl ! target m**5 value.
if ( diff < 0 ) exit
if ( n5(l) < diff ) cycle ! no possible solution in (1...l).
!if ( exclude_l11( mod(sl,11_ik), mapT11 ) ) cycle
!if ( exclude_l31( mod(sl,31_ik), mapT31 ) ) cycle
mmin = perm(mod(diff,nperm)) ! mod(m**5,nperm) == mod(diff,nperm) is required,
do m = mmin, l, nperm ! mmin is the smallest such value.
if ( n5(m) < diff ) then
cycle
elseif ( n5(m) > diff ) then
exit
else ! n5(m) == diff
print cfmt, "i5 =", i5
print cfmt, j, k, l, m, i
nfound = nfound + 1
if ( nfound >= findmax ) then
exit outer
else
exit ! continue searching.
endif
endif
enddo
enddo
enddo
enddo
enddo outer
end program sum_conjecture
I left a test in the code to verify that the permutation array is valid. If you change the value of nperm, then you should probably uncomment that if block at least once to make sure you have a good nperm value. I left it commented out just because it might affect the times.
You might also notice that I commented out the two l loop exclude tests. Uncommenting those tests increases the run time a little. I still don’t understand why that happens. And it may not happen for other cpu+compiler combinations.
I think the next thing to try to improve the code would be to exclude more of the outer k loop passes.