1

I have solved Euler 14 problem in Python, and I wanted to see how much time it would take for the same calculation to take place in Fortran. In python, I wrote:

def main(n):                                                                                                                                                                                                                                                              
     '''Counts the elements of the sequence starting at n and finishing at 1 ''' 
     count = 1
     while True:
         if n == 1:
             return count
         if (n % 2 == 0):
             n = n/2
         else:
             n = 3*n + 1
         count += 1
 
 
 if __name__ == '__main__':
     limit = 10**6
     # limit = 14
     n = 1
     result = 0
     while n < limit:
         sequence = main(n)
         if sequence > result:
             result = sequence
             solution = n
         n += 1
     print("Number that gives the longest chain: ", solution)

This works well but it is not very efficient (it takes about 23 seconds to complete). I wanted to see how long it would take for the same calculation in Fortran. Then I wrote the same in Fortran (below). However, in the do while loop in the main programme, the value of n does not go above 2.

  subroutine euler14(n,counter)
     integer :: n, counter
     counter = 1
     do
             if (n.eq.1) EXIT
             !end if
             if (mod(n,2).eq.0) then
             n = n/2
             else
             n = 3*n + 1
             end if
             counter = counter + 1
             !print *, "Counter: ", counter
     end do
     !print *, 'Made it'
     RETURN
   end
 
 
 
 
   program main
     implicit none
     integer, parameter :: limit = 1000000
     integer :: n, counter,solution,rf
     real :: start_time, stop_time
     call cpu_time(start_time)
     n = 1
     rf = 0 ! result
     do while(n.lt.limit)
             !print *, n
             call euler14(n,counter)
             if(counter.gt.rf) then
             rf = counter
             solution = n
             end if
             n = n + 1
     end do
 
     call cpu_time(stop_time)
     print *, "Time taken: ",
 a  stop_time - start_time, " seconds."
 
   end program main

Do you have any idea of what it could've gone wrong with my programme in Fortran?

Many thanks in advance

paulanueno
  • 31
  • 2

3 Answers3

2

Not what you asked for, but maybe informative. If you keep information about the length of smaller collatz sequences you can reuse them as your n increase. Here is a python version that uses memoization. It runs in about 1s.

import functools


@functools.lru_cache(maxsize=None)
def collatz(n):
    if n == 1:
        return 1

    if n & 1:
        return 1 + collatz(3 * n + 1)
    else:
        return 1 + collatz(n // 2)


print(max(((collatz(i), i) for i in range(1, 10 ** 6)))[1])
Christian Sloper
  • 7,440
  • 3
  • 15
  • 28
1

Fortran passes arguments by reference. Your main passes n to euler14 by reference, and euler14 sets it to 1 by the time it's done.

user2357112
  • 260,549
  • 28
  • 431
  • 505
  • Thanks for your reply. What do you mean by "n is passed by reference"? Why does euler14 set it to 1 after each iteration? Sorry if this sounds stupid, I am quite new with Fortran... Thanks again!! – paulanueno Jul 08 '20 at 14:44
  • 1
    @paulanueno: `euler14` is working with the caller's `n` variable, not a separate copy. See https://stackoverflow.com/questions/373419/whats-the-difference-between-passing-by-reference-vs-passing-by-value – user2357112 Jul 08 '20 at 16:57
  • Thank you, this is very helpful. Is there a way to pass "n" by value instead of reference in Fortran? – paulanueno Jul 08 '20 at 18:58
  • Add keyword Value when declaring n in the function: integer, value :: n – Emilio Jul 09 '20 at 07:02
0

There's a couple of issues here. As noted elsewhere n gets reset in the subroutine. Also the sequence generates some VERY large numbers which can't be represented by 32 bit integers. You need to account for that.

Here's a quick solution (I've made euler14 a function too)

 program main
 use iso_fortran_env
 implicit none
 integer, parameter :: limit = 1000000
 integer :: n, counter,solution,rf
 real :: start_time, stop_time
 call cpu_time(start_time)
 rf = 0 ! result
 do n=1,limit
         counter= euler14(n)
         if(counter.gt.rf) then
         rf = counter
         solution = n
         write(*,*) rf,solution
         end if
 end do

 call cpu_time(stop_time)
 print *, solution
 print *, "Time taken: ", stop_time - start_time, " seconds."
contains

integer function euler14(n_in) result(counter)
integer,intent(in) :: n_in
 integer(int64) :: n64  ! this can get big
 counter = 1
 n64=n_in
 do
         if (n64.eq.1_int64) EXIT
         !end if
         if (mod(n64,2_int64).eq.0_int64) then
         n64 = n64/2
         else
         n64 = 3*n64 + 1
         end if
         counter = counter + 1
 end do
end function euler14

end program main

gfortran -O e14.f90

./a.out

...

    525      837799
  837799
Time taken:   0.226117998      seconds.
RussF
  • 711
  • 3
  • 4