Here is an alternative program that uses a packed bit representation of which cubes are included in the sum. If the sum contains 1^3, bit-0 is set; if the sum contains 2^3, bit-1 is set, and so on up to bit-12. The packed bit value is the index into an integer array S in which the sum of the selected cubes is stored. Then, for values of N within a selected range (such as 2000 to 2040), the indices of the S entries that fall within the range are noted. These entries are then sorted and output. Because every entry in array S is already known to be the sum of cubes, there is no time spent on attempting to split a test number into the sum of cubes, as is done in some other algorithms.
! Finds integers N that are cubes and are also equal to the sum of cubes of integers
! Only values of N between YLOW and YHIGH are covered.
! The count of the solutions is expected to be no more than KMAX
!
program cubem
implicit none
integer i, j, n, k, m, i0, i1, NMAX
integer, parameter :: IMAX = 13, KMAX = 100
integer, parameter :: YLOW = 2000, YHIGH = 2040
integer, parameter :: cubes(IMAX) = (/ (i*i*i,i=1,IMAX) /)
integer eul(KMAX), idx(KMAX),sol(KMAX)
logical first
k = 0
NMAX = ishft(1,IMAX)-1
do i = 1, NMAX
n = 0
do j = 0, iMAX-1
if (btest(i,j)) n = n+cubes(j+1)
end do
if(n >= YLOW .and. n <= YHIGH)then
k = k+1
eul(k) = n
idx(k) = k
sol(k) = i
endif
end do
print *,'Sorting ',k,' items'
call inssort(k,idx,eul)
do i = 1, k
j = idx(i)
i0 = sol(j)
write(*,"(I4,2x,'= sum of cubes of {')",advance='no')eul(j)
first = .true.
i1 = 0
do m = 0,IMAX-1
if(btest(i0,m))then
if(first)then
first = .false.
write(*,"(i3)",advance='no')(m+1)
else
write(*,"(',',i3)",advance='no')(m+1)
endif
i1 = i1+cubes(m+1)
endif
end do
print *,'}'
if(i1 .ne. eul(j))print *,'Error, sum of cubes does not equal ',i1
end do
end program
subroutine inssort(N,idx,A)
implicit none
integer, intent(in) :: N, A(N)
integer, intent(in out) :: idx(N)
integer :: i,j,itmp
!
do i = 2, N
j = i-1
do while (j > 0)
if (A(idx(j)) <= A(idx(j+1))) exit
itmp = idx(j+1)
idx(j+1) = idx(j)
idx(j) = itmp
j = j - 1
end do
end do
return
end subroutine inssort
The output of the program (run time should be less than a second) should include multiple solutions when they exist.
Sorting 29 items
2003 = sum of cubes of { 2, 3, 5, 8, 11}
2004 = sum of cubes of { 1, 2, 3, 5, 8, 11}
2007 = sum of cubes of { 3, 5, 7, 8, 10}
2008 = sum of cubes of { 4, 6, 12}
2008 = sum of cubes of { 1, 3, 5, 7, 8, 10}
2009 = sum of cubes of { 1, 4, 6, 12}
2009 = sum of cubes of { 4, 6, 9, 10}
2010 = sum of cubes of { 1, 4, 6, 9, 10}
2015 = sum of cubes of { 5, 6, 7, 11}
2015 = sum of cubes of { 2, 3, 5, 7, 8, 10}
2016 = sum of cubes of { 2, 4, 6, 12}
2016 = sum of cubes of { 1, 5, 6, 7, 11}
2016 = sum of cubes of { 1, 2, 3, 5, 7, 8, 10}
2016 = sum of cubes of { 3, 4, 5, 6, 7, 8, 9}
2017 = sum of cubes of { 1, 2, 4, 6, 12}
2017 = sum of cubes of { 2, 4, 6, 9, 10}
2017 = sum of cubes of { 1, 3, 4, 5, 6, 7, 8, 9}
2018 = sum of cubes of { 1, 2, 4, 6, 9, 10}
2023 = sum of cubes of { 2, 5, 6, 7, 11}
2024 = sum of cubes of { 1, 2, 5, 6, 7, 11}
2024 = sum of cubes of { 2, 3, 4, 5, 6, 7, 8, 9}
2025 = sum of cubes of { 1, 2, 3, 4, 5, 6, 7, 8, 9}
2032 = sum of cubes of { 4, 5, 8, 11}
2033 = sum of cubes of { 1, 4, 5, 8, 11}
2035 = sum of cubes of { 3, 4, 6, 12}
2036 = sum of cubes of { 1, 3, 4, 6, 12}
2036 = sum of cubes of { 3, 4, 6, 9, 10}
2037 = sum of cubes of { 1, 3, 4, 6, 9, 10}
2040 = sum of cubes of { 2, 4, 5, 8, 11}
P.S. Thanks to @JohnCampbell for correcting my initialization of NMAX.
) style suggestions when compiling code, so I converted the entire code in one go and have to say it looks better for it.