# Euler Conjecture and CDC 6600 **URL:** \ **Category:** Uncategorized\ **Created:** [November 18, 2025, 10:59am UTC](https://fortran-lang.discourse.group/t/euler-conjecture-and-cdc-6600/10501 "2025-11-18T10:59:45Z")\ **Posts on this page:** 1\ **Showing post:** 60
**Author:** ![RonShepard](https://avatars.discourse-cdn.com/v4/letter/r/a3d4f5/32.png) [@RonShepard](https://fortran-lang.discourse.group/u/RonShepard)\ **Post date:** [November 25, 2025, 8:35am UTC](https://fortran-lang.discourse.group/t/euler-conjecture-and-cdc-6600/10501/60 "2025-11-25T08:35:59Z")
> [@RonShepard](#): > > Also, there are many cases where `mod(i,n)` and `mod(i**5,n)` are just permutations of each other. For `n=10`, that permutation happens to be the identity permutation. I don’t really know why that happens. 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. ```auto $ 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. ```fortran 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. --- _[View the full topic](https://fortran-lang.discourse.group/t/euler-conjecture-and-cdc-6600/10501)._