What language would they have used

[JohnNichols]

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.pdf

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 --

[JohnNichols]

144 = 3*3*2*2*2*2

I made a mistake back soon

[JohnNichols]

if a = 2^5

b = 3^5

c = 5^5

d = 7^5

e = 11^5

f = 19^5

b*b*b + b*a*a*d + ace + df = b*b*a*a*a*a

The next ones are related by n  1,2,3,4 to the 5th power 

There are no common factors in the equation and they are all primes as expected

Interesting 13 and 17 are missing 

[JohnNichols]

if n = 1,2,3, etc

m = n^5

27^5*m = 54^5

and so on I think

[JohnNichols]

55	11	5
3183	1061	3
28969	491	59
85282	42641	2
85359	28453	37

This is the next one according to Wikipedia and the primes are -- so this is a primitive solution as is the first one I confirmed - the rest are non primitive.   These are really random weird primes 

I had to stop the program I was searching the range to 1000 and the 7th one has a rhs of 1008. 

I had a quick look online -- there are a lot of people using a lot of computer power to solve these problems. 

One of the interesting methods is to assume that 7 is a element of the some of the numbers and use mod arithmetic to reduced the loops.  Neat idea - would not have caught the one above. 

I would be willing to bet a steak dinner that the first element of the next one is 

5* 19 

7 * 19

11 * 19 

and that some had factors of 2 or 3 in them 

so the search could be limited to search on primes,  

The primes only have 7% of the density of composite numbers 

Ah well a good way to relax and wile away a few hours 

[mecej4]

@JohnNichols :

You asked, Can you take a look at the code and show me how to thread it or OMP?

It is usually inappropriate to take a code that implements an inefficient/brute force algorithm and try to improve its performance by parallelizing the code. It is more profitable to structure the calculation to avoid unnecessary recalculations, as AndrewP noted, and to use better algorithms when those are available.

The attached program is about 150 lines of Fortran code, and uses OpenMP. On an i5-8400, it takes about 15 minutes in sequential mode, and about 5 minutes in multithreaded mode, to search for all the solutions of the (5. 1. 4) problem, for x1 from 1 to 999.  As expected, the program outputs only the lone known primitive solution, which is  (144)_5 = (27, 84, 110, 133)_5.

I rarely work on parallelization of code, so there is probably room for improvement -- I saw only a factor of 3 speed up with 6 cores.

P.S.: By readjusting the loop splits as integer :: iu(7) = [999,955,900,840,760,640,1], I found that I can reduce the run time to 150 seconds, which matches the sought sixfold speed increase with six cores.

Modified to solve the (5. 1. 5) problem, the OpenMP program reproduced the results of Table III of the paper by L.J. Lander, T.R. Parkin and J.L. Selfridge in Mathematics of Computation. Vol. 21, No. 99 (Jul., 1967), pp. 446-459. The run time on a six core i5-8400 was 31 minutes.

[JohnNichols]

mecej4 -- you are a treasure 

[mecej4]

@JohnNichols 

If one aspires to become a number theorist, there are many tradesperson's secrets and tricks to have in one's toolbox.

Since we spend quite a bit of time testing whether a given integer is the fifth power of an integer, there is a special partial test that can be made.

The last nybble (4 least significant bits) of a fifth power of an integer must be 0000 or the least significant bit of the integer must be 1. This property is necessary but not sufficient.

We can apply this test to dispose of failing candidates in short order. If the candidate fails the test, we give up the search and go on to the next number to test. If the candidate passes, we process it as we do at present to find if it has an integer as its fifth root.

In Subroutine SEARCH, add the following lines:

integer nyb0
...
!search for n integers whose 5th power equals s
if(n == 1)then
   nyb0=iand(s,15)   !new
   if(nyb0 == 0 .or. btest(nyb0,0))then !new
      call search1(s,found,im,nv,vals) !old
   else !new
      found=.false. !new
   endif !new

With this enhancement, the (5. 1. 4) run takes about 2 minutes, and the (5. 1. 5) run takes 8 minutes.

[mecej4]

Two years ago, I reported:

---

Modified to solve the (5. 1. 5) problem, the OpenMP program reproduced the results of Table III of the paper by L.J. Lander, T.R. Parkin and J.L. Selfridge in Mathematics of Computation. Vol. 21, No. 99 (Jul., 1967), pp. 446-459. The run time on a six core i5-8400 was 31 minutes.

---

This week, I found a web page where James Waldby reports many results and other information about the "(5. 1. 5) problem". He provides source code in C for a calculation that uses better algorithms than the brute force methods discussed in this thread.

His C program, running on a single core with no OpenMP, with n limited to values less than 600, produces the results of Table III of the Lander, Parkin and Selfridge paper in less than 10 seconds.

[JohnNichols]

This is a nice find.  Although my second grade teacher at Belmont Infants School hammered into my young brain, nice is not a word with any meaning, use a real adjective.  

The human mind finds interesting shortcuts.  

I have been thinking about multiply two matrices, and the shortcuts to reduce the multiplication number. 

Interesting to play in your mind. 

[JohnNichols]

An aside note:

So as I was doing this stuff, just to take the boredom away from a terrible proposal -- a minute ago I was shelling a boiled egg, I was absentmindedly counting primes in my mind, and without thinking I used the back of the spoon handle to shell the egg. 

 I also was looking at the views on this stream, so that got me thinking I wonder if someone has done a video on spooning eggs, answer a couple of hundred. 

I then looked for poaching eggs, this lady has 11m views, and she does some really nifty science lessons - I was impressed - if you have grandchildren this is an excellent science lesson - do it in the kitchen

I apologize for non-Fortran, but I was thinking of Fortran when I thought about this problem. 

Does that count?

The presenter cannot pronounce sieve. 

POACHED EGGS | how to poach an egg (perfectly)

11,163,321 views

•Jul 1, 2018

228K8.8KSHARESAVE

https://www.youtube.com/watch?v=yifZtA3uF-E