Intel® Fortran Compiler
Build applications that can scale for the future with optimized code designed for Intel® Xeon® and compatible processors.

What language would they have used

JohnNichols
Valued Contributor II
850 Views

I stumbled across this little gem, it is correct - checked it with excel -- did they likely do it in Fortran and what algorithm do you think they used?

https://www.ams.org/journals/mcom/1967-21-099/S0025-5718-1967-0222008-0/S0025-5718-1967-0222008-0.pd...

This paper sets out some of the findings as well from 1967,  this is a big search and overflow would be a real issue

The two are from the aerospace co - why would they be interested in this pure math --

main-qimg-6dcd42be2321a6a8c9d32e33e44b13a5.jpg

0 Kudos
28 Replies
JohnNichols
Valued Contributor II
701 Views

How do I make it threaded to speed up the analysis

!  Console100.f90 
!
!  FUNCTIONS:
!  Console100 - Entry point of console application.
!

!****************************************************************************
!
!  PROGRAM: Console100
!
!  PURPOSE:  Entry point for the console application.
!
!****************************************************************************

    program Console100

    implicit none
    double precision a(1000), b(1000), count, sum
    integer i,j,k,l,g,h
    

    ! Variables

    ! Body of Console100
    print *, 'Hello World'
    open(1,file="f.out",status="unknown")
    count = 1.0
    h = 144
    do 100 i = 1,h
        a(i) = count*count*count*count*count
        b(i) = a(i)
        write(2,*)i, a(i)
        count = count + 1.0
100 end do         
        
    do 200 i = 1, h
        write(1,*)i
        do 300 j = 1, h
            do 400 k = 1, h
                
               !   write(*,*)i,j,k
                do 500 l = 1,h
                    sum = a(i) + a(j) + a(k) + a(L)
                    write(1,*)(sum**0.2)
                    do 600 g = 1, h
                        if(sum .eq. b(g)) then 
                        
                         write(1,*)">>>>>>>>>>>>>>>>>>>>>>",g, sum
                         end if
600                 end do
                    
500             end do
400         end do
300     end do
200 end do         

    end program Console100

 - this i brute force - we should be able to speed it up - optimize operations  

mecej4
Black Belt
694 Views

Curiously, the same right hand value, i.e., 144^5, can be expressed as the sum of the 5th powers of 5 integers:

      a^5 + b^5 + c^5 + d^5 + f^5 = n^5 = p^5 + q^5 + r^5 + s^5

for a = 38, b = 86, c = 92, d = 94, f=134, and n = 144. As stated in the paper, p = 27, q = 84, r = 110, s = 133.

Furthermore, all the numbers a, b, c, d, f and n are even.

A related curious fact: The fifth power of any integer has the same last digit as the number itself does. This property can be used when testing if a given integer is the fifth power of an integer.

Wikipedia has an article on the conjecture, see https://en.wikipedia.org/wiki/Euler%27s_sum_of_powers_conjecture .

According to the article, the truth of the conjecture remains an open question when the exponent k > 5.

P.S. (3 Aug 2020):

Some additional information follows. The paper that JMN attached is one of the shortest published journal articles in existence (it consists of two sentences). A more detailed paper, of which Lander is also an author, is https://www.ams.org/journals/mcom/1967-21-099/S0025-5718-1967-0222008-0/S0025-5718-1967-0222008-0.pd... . In the notation introduced in that paper, the 2-sentence paper announces a (5. 1. 4)<sub>1</sub> "primitive" solution.

The solution that I gave above is a (5. 1. 5) solution, which I obtained from a program in which I started with n = 144 and searched for a few smaller values of n, but it is not primitive, and therefore is not to be found in Table III of the longer AMS paper. If we divide each of the numbers in the equality by 2, the result is the first entry, which IS primitive:

a = 19, b = 43, c = 46, d = 47,  f = 67 and n = 72

A distributed computing project targeting sums of sixth powers is described at http://euler.free.fr .

JohnNichols
Valued Contributor II
683 Views

I am of the opinion that the Lander solution actually should include 0 to the 5th paper, it is just the zero on the function can be represented with 4 integers > 0, it is really a zero, was one thought .  

So I am not sure Euler was theoretically wrong, just a way of expressing the answer.  

It is very slow for even 144. 

JohnNichols
Valued Contributor II
680 Views

 It is unknown whether the conjecture fails or holds for any value k ≥ 6.

We can show it fails, but I doubt we can prove it is true,  we cannot represent all the numbers in a computer accurately in a time that can be managed - is a suggestion -- proving it by pure math - not sure. 

 

 

JohnNichols
Valued Contributor II
679 Views

Actually for k> 6 we should work out an algorithm that finds each zero quickly 

JohnNichols
Valued Contributor II
677 Views

And the brute force solution finds 24 solutions for the set 0 -144 run 4 times

 

in about 10 minutes on a core i5

andrew_4619
Honored Contributor I
668 Views

I would guess looking at number theory will yield some smarter method. But why not to your example with I8  rather that real. Also as a<b<c<d why not have the finding loop i+1, h   and j+1, h etc at least then you look at less combos.

Also have found an answer you can exit the test  loop rather than continue 

JohnNichols
Valued Contributor II
621 Views

1. which is the bigger potential number the i8 or the double precision 

2. Yes, lying in bed last night, I was doing the loops in my head, if I follow your idea I will reduce the loop count by the factorial of k-1. 

3. I have a spare NUC I can turn the problem loose on or I can use a supercomputer 

4. I was then going to turn the problem loose on 6. 

 

 

JohnNichols
Valued Contributor II
620 Views

I wanted to test it all the way through - so yes I will put a stop in it.  

Thanks 

JohnNichols
Valued Contributor II
600 Views

Is there anything I can do to optimize the 4 do loops 

 !  Console100.f90
    !
    !  FUNCTIONS:
    !  Console100 - Entry point of console application.
    !

    !****************************************************************************
    !
    !  PROGRAM: Console100
    !
    !  PURPOSE:  Entry point for the console application.
    !
    !****************************************************************************

    program Console100

    implicit none
    double precision a(1000), b(1000), count, sum
    integer i,j,k,l,g,h,m,n,p


    ! Variables

    ! Body of Console100
    print *, 'Hello World'
    open(1,file="f.csv",status="unknown")
    count = 1.0
    h = 4
    m = 1
    n = 1
    p = 1
    k = 0
    l = 0
    j = 0
    sum = 0.0
    do 100 i = 1,h
        a(i) = count*count*count*count*count
        b(i) = a(i)
        !write(2,*)i, a(i)
        count = count + 1.0
100 end do
    i = 0

    do 200 i = 1, h
        if(i .gt. 1) then
            p = i
        end if
        do 300 j = p,h
            if(j .gt. 1) then
                m = j
            end if
            do 400 k = m,h
                if(k .gt. 1) then
                n = k
            end if
                do 500 l = n,h
                !sum = a(i) + a(j) + a(k) + a(l)
                write(1,1000)i,j,k,l, sum
                write(*,1001)i,j,k,l
1000            Format(i5,',',i5,',',i5,',',i5,',' f15.1)
1001            Format(i5,'  ',i5,'  ',i5,'  ',i5)
500   end do                
400         end do
300     end do
        write(*,*)'  '
200 end do

    end program Console100

JohnNichols
Valued Contributor II
598 Views
    do 200 i = 1, h
       ! if(i .gt. 1) then
       !     p = i
      !  end if
        do 300 j = i,h
       !     if(j .gt. 1) then
       !         m = j
       !     end if
            do 400 k = j,h
       !         if(k .gt. 1) then
       !!         n = k
       !     end if
                do 500 l = k,h
                !sum = a(i) + a(j) + a(k) + a(l)
                write(1,1000)i,j,k,l, sum
                write(*,1001)i,j,k,l
1000            Format(i5,',',i5,',',i5,',',i5,',' f15.1)
1001            Format(i5,'  ',i5,'  ',i5,'  ',i5)
500   end do                
400         end do
300     end do
        write(*,*)'  '
200 end do
JohnNichols
Valued Contributor II
597 Views

That is like the old code from the 1960s - you were lucky to understand it at all 

JohnNichols
Valued Contributor II
592 Views

It is just a random fluke of nature that the odd one works

The addition of four fifth order functions equated to a single fifth order function is an exercise, see picture in one function almost following the other -- there is an error between them -- I would guess likely Gaussian or log Gaussian and at one point the error = 0 

 

For some reason I could not insert a picture -- the grey is the fifth order function and the two dots are the first two sets of the four additions. 

 

JohnNichols
Valued Contributor II
583 Views

Hp Envy Corei5 65 seconds of cpu time - I wonder how long on the CDC 6600

JohnNichols
Valued Contributor II
566 Views

Found second one - after 4 hours -- 54 168 220 266 - it is the double of the first one, 

so next one is likely 108 336 440 532   = 576 

next one 216 672 880 1064 =  1152

JohnNichols
Valued Contributor II
563 Views

1. I am of the opinion that lander did not have enough computing time to find the second one-- it took forever, 

2. can I represent this number as an integer.

6.34034E+13
GVautier
New Contributor II
546 Views

I implemented unlimited length integer computation (add, sub, mul and div). Not very efficient in term of speed but it works.

 

JohnNichols
Valued Contributor II
554 Views

I was wrong, there are more, they are not common about 1 in a million combinations to the first 1000, after 12 hours I am 135 - not even cracked the 

it appears so far on second glance they are all integer multiples of the first one - or 

27 54 81 108 135                       

27 = 3*3*3   

54 = 3*3*3*2   

81 = 3*3*3*3 

135 = 3*3*3*5

81 252 330 339  - this is the addtion of the first two - 

135 420 550 665   - 135 seems weird - it is still going --  at the moment I have it searching to the first 1000 -- I can probbaly do to about 6000 on the rhs before we have an integer fail.  

Speed is not a problem - I have spare computers all over the place - some faster than this one --  

I want to try 6 next.  

I would appreciate the unlimited integer math 

 

There is a pattern to the numbers all based on 3.  let us see if we find more

JohnNichols
Valued Contributor II
557 Views

162 504 660 798  just popped up

next one is 

189 588 770 931 - should find it in about an hour 

JohnNichols
Valued Contributor II
467 Views

144 = 3*3*2*2*2

There is a simple beauty to them ==  

 

Trick is -- are there any others 

Guys: 

Can you take a look at the code and show me how to thread it or OMP -- 

Thanks 

 

Reply