Euler's sum of powers conjecture: Difference between revisions

There is a conjecture in mathematics that held for over two hundred years before it was disproved by the finding of a counterexample in 1966 by [http://www.ams.org/journals/mcom/1967-21-097/S0025-5718-1967-0220669-3/S0025-5718-1967-0220669-3.pdf Lander and Parkin].

 

 

 

 

 

 

 

 

=={{header|11l}}==

{{trans|Python}}

V max_n = 250

V pow_5 = (0 .< max_n).map(n -> Int64(n) ^ 5)

 

V r = eulers_sum_of_powers()

 

{{out}}

In the program we do not user System/360 integers (31 bits) unable to handle the problem, but System/360 packed decimal (15 digits). 250^5 needs 12 digits.<br>

This program could have been run in 1964. Here, for maximum compatibility, we use only the basic 360 instruction set. Macro instruction XPRNT can be replaced by a WTO.

USING EULERCO,R13

B 80(R15)

BUF DS CL80

YREGS

{{out}}

<pre>

27 84 110 133 144

</pre>

 

=={{header|Ada}}==

 

 

procedure Sum_Of_Powers is

Ada.Text_IO.New_Line;

{{output}}

<pre> 27 84 110 133 144

=={{header|ALGOL 68}}==

{{works with|ALGOL 68G|Any - tested with release 2.8.win32}}

INT max number = 250;

 

OD

OD

Output:

<pre>

<br>

Algol W integers are 32-bit only, so we simulate the necessary 12 digit arithmetic with pairs of integers.

% find a, b, c, d, e such that a^5 + b^5 + c^5 + d^5 = e^5 %

% where 1 <= a <= b <= c <= d <= e <= 250 %

found :

end

{{out}}

<pre>

{{trans|Nim}}

 

p5: map 0..top => [& ^ 5]

 

]

 

 

{{out}}

 

=={{header|AWK}}==

# syntax: GAWK -f EULERS_SUM_OF_POWERS_CONJECTURE.AWK

BEGIN {

}

}

{{out}}

<pre>

133^5 + 110^5 + 84^5 + 27^5 = 144^5

15 seconds

</pre>

 

=={{header|Bracmat}}==

& whl

' ( 1+!x0:<250:?x0

)

)

'''Output'''

<pre>x0 133 x1 110 x2 84 x3 27 y 144</pre>

=={{header|C}}==

The trick to speed up was the observation that for any x we have x^5=x modulo 2, 3, and 5, according to the Fermat's little theorem. Thus, based on the Chinese Remainder Theorem we have x^5==x modulo 30 for any x. Therefore, when we have computed the left sum s=a^5+b^5+c^5+d^5, then we know that the right side e^5 must be such that s==e modulo 30. Thus, we do not have to consider all values of e, but only values in the form e=e0+30k, for some starting value e0, and any k. Also, we follow the constraints 1<=a<b<c<d<e<N in the main loop.

#include <stdio.h>

#include <time.h>

printf("time=%d milliseconds\r\n", (int)((clock() - tm) * 1000 / CLOCKS_PER_SEC));

return 0;

{{output}}

The fair way to measure the speed of the code above is to measure it's run time to find all possible solutions to the problem, given N (and not just a single solution, since then the time may depend on the way and the order we organize for-loops).

===Loops===

{{trans|Java}}

 

namespace EulerSumOfPowers {

}

}

===Paired Powers, Mod 30, etc...===

{{trans|vbnet}}

using System.Collections.Generic;

using System.Linq;

}

}

{{out}}(no command line arguments)<pre>Mod 30 shortcut with threading, checking from 1 to 250...

27^5 + 84^5 + 110^5 + 133^5 = 144^5

===First version===

The simplest brute-force find is already reasonably quick:

#include <iostream>

#include <cmath>

cout << "time=" << (int)((clock() - tm) * 1000 / CLOCKS_PER_SEC) << " milliseconds\r\n";

return 0;

{{out}}

<pre>

</pre>

We can accelerate this further by creating a parallel std::set<double> p5s containing the elements of the std::vector pow5, and using it to replace the call to std::binary_search:

for (auto i = 1; i < MAX; i++)

{

}

//...

This reduces the timing to 125 ms on the same hardware.

 

A different, more effective optimization is to note that each successive sum is close to the previous one, and use a bidirectional linear search with memory. We also note that inside the innermost loop, we only need to search upward, so we hoist the downward linear search to the loop over x2.

{

const auto MAX = 250;

// not found

return false;

This reduces the timing to around 25 ms. We could equally well replace rs with an iterator inside pow5; the timing is unaffected.

 

 

Fortunately, we can incorporate the same trick into the above code, by inserting a forward jump to a feasible solution mod 30 into the loop over x3:

{

// go straight to the first appropriate x3, mod 30

if (x3 >= x2)

break;

With this refinement, the exhaustive search up to MAX=1000 takes 16.9 seconds.

 

 

 

{

C_ retval(src);

}

return false;

 

Thanks, EchoLisp guys!

 

=={{header|Clojure}}==

(ns test-p.core

(:require [clojure.math.numeric-tower :as math])

(println (into #{} (map sort (solve-power-sum 250 1)))) ; MAX = 250, find only 1 value: Duration was 0.26 seconds

(println (into #{} (map sort (solve-power-sum 1000 1000))));MAX = 1000, high max-value so all solutions found: Time = 4.8 seconds

Output

<pre>

 

=={{header|COBOL}}==

IDENTIFICATION DIVISION.

PROGRAM-ID. EULER.

 

END PROGRAM EULER.

Output

<pre>

 

=={{header|Common Lisp}}==

(ql:quickload :alexandria)

(let ((fifth-powers (mapcar #'(lambda (x) (expt x 5))

(if (member x-sum fifth-powers)

(return-from outer (list x0 x1 x2 x3 (round (expt x-sum 0.2)))))))))))

{{out}}

<pre>(133 110 84 27 144)</pre>

===First version===

{{trans|Rust}}

 

auto eulersSumOfPowers() {

void main() {

writefln("%d^5 + %d^5 + %d^5 + %d^5 == %d^5", eulersSumOfPowers[]);

{{out}}

<pre>133^5 + 110^5 + 84^5 + 27^5 == 144^5</pre>

===Second version===

{{trans|Python}}

import std.stdio, std.range, std.algorithm, std.typecons;

 

}

}

{{out}}

<pre>144 Tuple!(uint, uint, uint, uint)(27, 84, 110, 133)</pre>

{{trans|C++}}

This solution is a brutal translation of the iterator-based C++ version, and it should be improved to use more idiomatic D Ranges.

 

alias Pair = Tuple!(double, int);

if (!dPFind(100))

printf("Search finished.\n");

{{out}}

<pre>133 110 27 84 : 144

 

=={{header|EasyLang}}==

len p5[] n

len h5[] 65537

.

.

.

 

=={{header|EchoLisp}}==

To speed up things, we search for x0, x1, x2 such as x0^5 + x1^5 + x2^5 = a difference of 5-th powers.

(define dim 250)

 

→ (27 84 110 133 144) ;; time 2.8 sec

 

=={{header|Elixir}}==

{{trans|Ruby}}

def sum_of_power(max \\ 250) do

{p5, sum2} = setup(max)

Enum.each(Euler.sum_of_power, fn {k,v} ->

IO.puts Enum.map_join(k, " + ", fn i -> "#{i}**5" end) <> " = #{v}**5"

 

{{out}}

 

=={{header|ERRE}}==

 

CONST MAX=250

END FOR

END FOR

{{output}}

<pre>

 

=={{header|F_Sharp|F#}}==

//Find 4 integers whose 5th powers sum to the fifth power of an integer (Quickly!) - Nigel Galloway: April 23rd., 2015

let G =

| _ -> gng(n,i,g,e+1)

gng (1, 1, 1, 1)

{{out}}

<pre>

=={{header|Factor}}==

This solution uses Factor's <code>backtrack</code> vocabulary (based on continuations) to simplify the reduction of the search space. Each time <code>xn</code> is called, a new summand is introduced which can only take on a value as high as the previous summand - 1. This also creates a checkpoint for the backtracker. <code>fail</code> causes the backtracking to occur.

math.ranges prettyprint sequences ;

 

 

250 xn xn xn xn drop 4array dup pow5 nths sum dup pow5

{{out}}

<pre>

=={{header|Forth}}==

{{trans|Go}}

: sq dup * ;

: 5^ dup sq sq * ;

euler

bye

{{out}}

<pre>

In 1966 all Fortrans were not equal. On IBM360, INTEGER was a 32-bit integer; on CDC6600, INTEGER was a 60-bit integer.

And Leon J. Lander and Thomas R. Parkin used the CDC6600.

C FIND I1,I2,I3,I4,I5 : I1**5+I2**5+I3**5+I4**5=I5**5

INTEGER I,P5(250),SUMX

6 CONTINUE

300 FORMAT(5(1X,I3))

{{out}}

<pre>

===Fortran 95===

{{works with|Fortran|95 and later}}

implicit none

 

end do outer

{{out}}

<pre> 27 84 110 133 144</pre>

 

 

 

 

 

 

=={{header|Go}}==

{{trans|Python}}

 

import (

log.Fatal("no solution")

return

{{output}}

<pre>

=={{header|Groovy}}==

{{trans|Java}}

static final int MAX_NUMBER = 250

 

}

}

{{out}}

<pre>27^5 + 84^5 + 110^5 + 133^5 + 144^5</pre>

 

=={{header|Haskell}}==

import Data.List.Ordered

 

 

-- which power of 5 is sum ?

{{output}}

<pre>

Or, using dictionaries of powers and sums, and thus rather faster:

{{Trans|Python}}

import Data.List (find, intercalate)

import Data.Maybe (maybe)

rangeString :: [Int] -> String

rangeString [] = "[]"

{{Out}}

<pre>Euler's sum of powers conjecture – a counter-example in range [1 .. 249]:

=={{header|J}}==

 

(#~ (= <.)@((+/"1)&.:(^&5)))1+4 comb 248

 

Explanation:

 

 

 

Only one possibility remains.

Here's a significantly faster approach (about 100 times faster), based on the echolisp implementation:

 

y=. 250

n=. i.y

x=. (t e. s)#t

|.,&<&~./|:(y,y)#:l#~a e. x

 

Use:

 

┌─────────────┬───┐

│27 84 110 133│144│

 

Note that this particular implementation is a bit hackish, since it relies on the solution being unique for the range of numbers being considered. If there were more solutions it would take a little extra code (though not much time) to untangle them.

{{trans|ALGOL 68}}

Tested with Java 6.

{

 

} // main

 

Output:

<pre>

=={{header|JavaScript}}==

===ES5===

 

var aPow5 = [];

 

console.log(oResult.i0 + '^5 + ' + oResult.i1 + '^5 + ' + oResult.i2 +

 

{{Out}}

133^5 + 110^5 + 84^5 + 27^5 = 144^5

'''This'''{{trans|D}} that verify: a^5 + b^5 + c^5 + d^5 = x^5

var ns={}, npv=[]

for (var n=0; n<=N; n++) {

var e='⁵', ep=e+' + '

document.write(c[0], ep, c[1], ep, c[2], ep, c[3], e, ' = ', c[4], e, '<br>')

'''Or this'''{{trans|C}} that verify: a^5 + b^5 + c^5 + d^5 = x^5

var npv=[], M=30 // x^5 == x modulo M (=2*3*5)

for (var n=0; n<=N; n+=1) npv[n]=Math.pow(n, 5)

var e='⁵', ep=e+' + '

document.write(c[0], ep, c[1], ep, c[2], ep, c[3], e, ' = ', c[4], e, '<br>')

'''Or this'''{{trans|EchoLisp}} that verify: a^5 + b^5 + c^5 = x^5 - d^5

var dxs={}, pow=Math.pow

for (var d=1; d<=N; d+=1)

var e='⁵', ep=e+' + '

document.write(c[0], ep, c[1], ep, c[2], ep, c[3], e, ' = ', c[4], e, '<br>')

'''Or this'''{{trans|Python}} that verify: a^5 + b^5 = x^5 - (c^5 + d^5)

var is={}, ipv=[], ijs={}, ijpv=[], pow=Math.pow

for (var i=1; i<=N; i+=1) {

var e='⁵', ep=e+' + '

document.write(c[0], ep, c[1], ep, c[2], ep, c[3], e, ' = ', c[4], e, '<br>')

 

{{output}}

===ES6===

====Procedural====

'use strict';

 

.join(' + ') + ` = ${soln[4]}^5` : 'No solution found.'

 

{{Out}}

<pre>133^5 + 110^5 + 84^5 + 27^5 = 144^5</pre>

{{Trans|Python}}

{{Trans|Haskell}}

'use strict';

 

// MAIN ---

return main();

{{Out}}

<pre>Counter-example found:

This version finds all non-decreasing solutions within the specified bounds,

using a brute-force but not entirely blind approach.

# and for each solution with x0<=x1<=...<x3, print [x0, x1, x3, x3, y]

#

end

else empty

'''The task:'''

{{out}}

 

=={{header|Julia}}==

const lim = 250

const pwr = 5

println("A solution is ", s, " = ", @sprintf("%d^%d", y, pwr), ".")

end

 

{{out}}

 

=={{header|Kotlin}}==

val p5 = LongArray(250){ it.toLong() * it * it * it * it }

var sum: Long

}

if (!found) println("No solution was found")

 

{{out}}

=={{header|Lua}}==

Brute force but still takes under two seconds with LuaJIT.

function binarySearch (t, n)

local start, stop, mid = 1, #t

else

print("Looks like he was right after all...")

{{out}}

<pre>133^5 + 110^5 + 84^5 + 27^5 = 144^5

Time taken: 1.247 seconds</pre>

 

x0^5 + x1^5 + x2^5 + x3^5 == y^5 && x0 > 0 && x1 > 0 && x2 > 0 &&

{{out}}

 

=={{header|Modula-2}}==

{{output?|Modula-2}}

FROM FormatString IMPORT FormatString;

FROM Terminal IMPORT WriteString,WriteLn,ReadChar;

WriteLn;

ReadChar

 

=={{header|Nim}}==

{{trans|PureBasic}}

# Brute force approach

 

if y == 0 :

echo "No solution was found"

 

{{out}}

=={{header|Oforth}}==

 

| i j k l ip jp kp |

250 loop: i [

]

]

 

{{out}}

=={{header|PARI/GP}}==

Naive script:

{{out}}

<pre>144 [27, 84, 110, 133]</pre>

 

Naive + caching (<code>setbinop</code>):

v2=setbinop((x,y)->[min(x,y),max(x,y),x^5+y^5],[0..250]); \\ sums of two fifth powers

for(i=2,#v2,

)

)

{{out}}

<pre>144 [27, 84, 110, 133]</pre>

{{works with|Free Pascal}}

slightly improved.Reducing calculation time by temporary sum and early break.

{$IFDEF FPC} {$MODE DELPHI}{$ELSE]{$APPTYPE CONSOLE}{$ENDIF}

type

end;

END.

;output:

<pre>

=={{header|Perl}}==

Brute Force:

my @p5 = (0,map { $_**5 } 1 .. MAX-1);

my $s = 0;

}

}

{{out}}

<pre>27 84 110 133 144</pre>

 

Adding some optimizations makes it 5x faster with similar output, but obfuscates things.

my @p5 = (0,map { $_**5 } 1 .. MAX-1);

my $rs = 5;

}

}

 

=={{header|Phix}}==

Quitting when the first is found drops the main loop to 0.7s, so 1.1s in all, vs 4.3s for the full search.<br>

Without the return 0, you just get six permutes (of ordered pairs) for 144.

{{out}}

<pre>

=={{header|PHP}}==

{{trans|Python}}

 

function eulers_sum_of_powers () {

echo "$n_0^5 + $n_1^5 + $n_2^5 + $n_3^5 = $y^5";

 

 

{{out}}

<pre>133^5 + 110^5 + 84^5 + 27^5 = 144^5</pre>

 

=={{header|PicoLisp}}==

(off S)

 

(cadr (lup S (car B)))

(cadr (lup S (- (car A) (car B))))

{{out}}

<pre>(27 84 110 133 144)</pre>

'''Brute Force Search'''<br>

This is a slow algorithm, so attempts have been made to speed it up, including pre-computing the powers, using an ArrayList for them, and using [int] to cast the 5th root rather than use truncate.

$max = 250

 

}

}

{{Out}}

<pre>PS > measure-command { .\euler.ps1 | out-default }

 

=={{header|Prolog}}==

makepowers :-

retractall(pow5(_, _)),

Y_5th is X0_5th + X1_5th + X2_5th + X3_5th,

pow5(Y, Y_5th).

{{out}}

<pre>

X3 = 27,

Y = 144 .

</pre>

 

=={{header|Python}}==

===Procedural===

max_n = 250

pow_5 = [n**5 for n in range(max_n)]

return (x0, x1, x2, x3, y)

 

 

{{out}}

The above can be written as:

{{works with|Python|2.6+}}

 

def eulers_sum_of_powers():

return (x0, x1, x2, x3, y)

 

 

{{out}}

 

It's much faster to cache and look up sums of two fifth powers, due to the small allowed range:

p5, sum2 = {}, {}

 

if p - s in sum2:

print(p5[p], sum2[s] + sum2[p-s])

{{out}}

<pre>144 (27, 84, 110, 133)</pre>

===Composition of pure functions===

{{Works with|Python|3.7}}

 

from itertools import (chain, takewhile)

# MAIN ---

if __name__ == '__main__':

{{Out}}

<pre>Euler's sum of powers conjecture – counter-example:

 

133^5 + 110^5 + 84^5 + 27^5 = 144^5</pre>

 

=={{header|Racket}}==

{{trans|C++}}

(define MAX 250)

(define pow5 (make-vector MAX))

(when (set-member? pow5s sum)

(displayln (list x0 x1 x2 x3 (inexact->exact (round (expt sum 1/5)))))

{{output}}

<pre>

=={{header|Raku}}==

(formerly Perl 6)

 

my %sum2{Int};

 

}

}

 

}

}

{{out}}

 

=={{header|REXX}}==

=== fast computation ===

:* &nbsp; [the &nbsp; left side of the above equation] &nbsp; sum any applicable three integer powers of five &nbsp;

:* &nbsp; [the &nbsp; <big><big>==</big></big> &nbsp; part of the above equation] &nbsp; see if any of the above left─side sums match any of the &nbsp; ≈30k &nbsp; right─side differences

parse arg L H N . /*get optional LOW, HIGH, #solutions.*/

if L=='' | L=="," then L= 0 + 1 /*Not specified? Then use the default.*/

if #<N then return /*return, keep searching for more sols.*/

exit # /*stick a fork in it, we're all done. */

{{out|output|text=&nbsp; when using the default input:}}

<pre>

 

Execution time on a fast PC for computing (alone) &nbsp; for &nbsp; '''23,686''' &nbsp; numbers is exactly &nbsp; '''1.⁰⁰''' &nbsp; seconds.

numeric digits 1000 /*ensure enough decimal digs for powers*/

parse arg N oFID . /*obtain optional arguments from the CL*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

commas: parse arg _; do jc=length(_)-3 to 1 by -3; _=insert(',', _, jc); end; return _

{{out|output|text=&nbsp; when using the default input of: &nbsp; &nbsp; <tt> 200 </tt>}}

(Shown at three-quarter size.)

 

=={{header|Ring}}==

# Project : Euler's sum of powers conjecture

 

next

next

Output:

<pre>

=={{header|Ruby}}==

Brute force:

result = power5.keys.repeated_combination(4).select{|a| power5[a.inject(:+)]}

{{out}}

<pre>

Faster version:

{{trans|Python}}

(1..max).each do |i|

p5[i**5] = i

end

end

The output is the same above.

 

=={{header|Rust}}==

 

fn eulers_sum_of_powers() -> (usize, usize, usize, usize, usize) {

let (x0, x1, x2, x3, y) = eulers_sum_of_powers();

println!("{}^5 + {}^5 + {}^5 + {}^5 == {}^5", x0, x1, x2, x3, y)

{{out}}

<pre>133^5 + 110^5 + 84^5 + 27^5 == 144^5</pre>

=={{header|Scala}}==

===Functional programming===

 

object EulerSopConjecture extends App {

println(sop)

 

{{Out}}Vector(27⁵ + 84⁵ + 110⁵ + 133⁵ = 144⁵)

 

=={{header|Seed7}}==

 

const func integer: binarySearch (in array integer: arr, in integer: aKey) is func

writeln("No solution was found");

end if;

 

{{out}}

 

=={{header|SenseTalk}}==

to findEulerSumOfPowers

set MAX_NUMBER to 250

end repeat

end repeat

 

=={{header|Sidef}}==

{{trans|Raku}}

 

var p5 = Hash()

say "#{t} = #{p5{p}}⁵"

break

{{out}}

<pre>

84⁵ + 27⁵ + 133⁵ + 110⁵ = 144⁵

</pre>

 

=={{header|Swift}}==

{{trans|Rust}}

 

@inlinable

public func power(_ n: Self) -> Self {

let (x0, x1, x2, x3, y) = sumOfPowers()

 

 

{{out}}

<pre>133^5 + 110^5 + 84^5 + 27^5 = 144^5</pre>

 

 

=={{header|VBScript}}==

{{trans|ERRE}}

 

For X0=1 To Max

Function fnP5(n)

fnP5 = n ^ 5

 

{{out}}

 

=={{header|Visual Basic .NET}}==

 

 

 

 

 

 

 

 

=={{header|Wren}}==

{{trans|C}}

var n = 250

var m = 30

}

}

 

{{out}}

<pre>

27⁵ + 84⁵ + 110⁵ + 133⁵ = 144⁵

</pre>

 

=={{header|Zig}}==

{{trans|Go}}

const std = @import("std");

const stdout = std.io.getStdOut().outStream();

try stdout.print("Sorry, no solution found.\n", .{});

}

{{Out}}

<pre>

=={{header|zkl}}==

Uses two look up tables for efficiency. Counts from 0 for ease of coding.

pow5r:=pow5s.enumerate().apply("reverse").toDictionary(); // [144^5:144, ...]

foreach x0,x1,x2,x3 in (249,x0,x1,x2){

.fmt(x3+1,x2+1,x1+1,x0+1,pow5r[sum]+1));

break(4); // the foreach is actually four loops

{{out}}<pre>27^5 + 84^5 + 110^5 + 133^5 = 144^5</pre>

Using the Python technique of caching double sums results in a 5x speed up [to the first/only solution]; actually the speed up is close to 25x but creating the caches dominates the runtime to the first solution.

{{trans|Python}}

foreach i in ([1..249]){

p5[i.pow(5)]=i;

break(2); // or get permutations

}

Note: dictionary keys are always strings and copying a read only list creates a read write list.

{{out}}<pre>27^5 + 84^5 + 110^5 + 133^5 = 144^5</pre>