# Julia vs. Python: Euler's sum of powers conjecture

**URL:** <https://discourse.julialang.org/t/julia-vs-python-eulers-sum-of-powers-conjecture/83262>\
**Category:** Performance\
**Tags:** performance, speed-optimization\
**Created:** [June 23, 2022, 5:22pm UTC](https://discourse.julialang.org/t/julia-vs-python-eulers-sum-of-powers-conjecture/83262 "2022-06-23T17:22:51Z")\
**Posts on this page:** 17\
**Page:** 1

<div class="post-metadata">

**Author:** ![jgforbes](https://avatars.discourse-cdn.com/v4/letter/j/9de0a6/32.png) [@jgforbes](https://discourse.julialang.org/u/jgforbes)\
**Post date:** [June 23, 2022, 5:22pm UTC](https://discourse.julialang.org/t/julia-vs-python-eulers-sum-of-powers-conjecture/83262/1 "2022-06-23T17:22:51Z")

</div>

The Julia code on this page is much slower than the Python examples.  
[Euler’s sum of powers conjecture with code examples](https://rosettacode.org/wiki/Euler%27s_sum_of_powers_conjecture#Julia)  
I wrote a Julia program similar to the fastest Python example:  
Julia

```julia
function main()
  MAX = 250  
  p5 = Dict()
  sum2 = Dict()
  sk = []

  for i in range(1, MAX)
       p5[i^5] = i
       for j in range(i, MAX)
               sum2[i^5 + j^5] = (i, j)
       end
  end

  sk = sort(collect(keys(sum2)))

  for p in sort(collect(keys(p5)))
       for s in sk
               if p <= s ; break ; end
               if p - s in keys(sum2)
                       println(p5[p], sum2[s], sum2[p-s])   
# exit()
               end
       end
  end
end

main()

```

~]$ time julia euler2.jl  
144(27, 84)(110, 133)  
144(27, 110)(84, 133)  
144(84, 110)(27, 133)  
144(27, 133)(84, 110)  
144(84, 133)(27, 110)  
144(110, 133)(27, 84)

real 0m0.996s  
user 0m0.982s  
sys 0m0.222s

Python

```julia
MAX = 250
p5, sum2 = {}, {}
sk = []

for i in range(1, MAX):
       p5[i**5] = i
       for j in range(i, MAX):
               sum2[i **5 + j** 5] = (i, j)
 
sk = sorted(sum2.keys())

for p in sorted(p5.keys()):
       for s in sk:
               if p <= s: break
               if p - s in sum2:
                       print(p5[p], sum2[s] + sum2[p-s])
# exit()

```

]$ time python euler2.py  
144 (27, 84, 110, 133)  
144 (27, 110, 84, 133)  
144 (84, 110, 27, 133)  
144 (27, 133, 84, 110)  
144 (84, 133, 27, 110)  
144 (110, 133, 27, 84)

real 0m0.559s  
user 0m0.546s  
sys 0m0.009s

I was surprised that the speed of these basic loop algorithm differed by almost a factor of two.  
The Python can also be made faster by putting the nested loop into a method, like so:

```julia
MAX = 250
p5, sum2 = {}, {}
sk = {}
for i in range(1, MAX):
    p5[i**5] = i
    for j in range(i, MAX):
        sum2[i **5 + j** 5] = (i, j)
 
sk = sorted(sum2.keys())
def methodC ():
    for p in sorted(p5.keys()):
        for s in sk:
            if p <= s: break
            if p - s in sum2:
                yield p5[p], sum2[s] + sum2[p-s]

for v1, v2 in methodC ():
    print (v1, v2)

```

~]$ time python euler3.py  
144 (27, 84, 110, 133)  
144 (27, 110, 84, 133)  
144 (84, 110, 27, 133)  
144 (27, 133, 84, 110)  
144 (84, 133, 27, 110)  
144 (110, 133, 27, 84)

real 0m0.368s  
user 0m0.351s  
sys 0m0.014s

Does anyone have any suggestions on how to optimize this Julia program to make it faster?

---

<div class="post-metadata">

**Author:** ![math\_opt](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/math_opt/32/25317_2.png) [@math\_opt](https://discourse.julialang.org/u/math_opt)\
**Post date:** [June 23, 2022, 5:29pm UTC](https://discourse.julialang.org/t/julia-vs-python-eulers-sum-of-powers-conjecture/83262/2 "2022-06-23T17:29:32Z")

</div>

I guess the question is better suited for the [performance](https://discourse.julialang.org/c/usage/perf) category. You can just add a tag to your question. 🙂

---

<div class="post-metadata">

**Author:** ![Jeff\_Emanuel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeff_emanuel/32/15440_2.png) [@Jeff\_Emanuel](https://discourse.julialang.org/u/Jeff_Emanuel)\
**Post date:** [June 23, 2022, 6:11pm UTC](https://discourse.julialang.org/t/julia-vs-python-eulers-sum-of-powers-conjecture/83262/3 "2022-06-23T18:11:33Z")

</div>

> [@jgforbes](#):
>
> `p - s in keys(sum2)`

`haskey(sum2, p - s)` should be faster, O(1) vs O(n).

You are measuring Julia startup time and compilation time. That may be fair in your case, but fast startup is not where Julia excels. Benchmarking is usually done with `@btime` to show the best case.

---

<div class="post-metadata">

**Author:** ![jgforbes](https://avatars.discourse-cdn.com/v4/letter/j/9de0a6/32.png) [@jgforbes](https://discourse.julialang.org/u/jgforbes)\
**Post date:** [June 23, 2022, 7:07pm UTC](https://discourse.julialang.org/t/julia-vs-python-eulers-sum-of-powers-conjecture/83262/4 "2022-06-23T19:07:50Z")

</div>

With @btime on a slower computer, need to use same system for comparison with above results  
~]$ julia euler2.jl  
144(27, 84)(110, 133)  
144(27, 110)(84, 133)  
144(84, 110)(27, 133)  
144(27, 133)(84, 110)  
144(84, 133)(27, 110)  
144(110, 133)(27, 84)  
0.649362 seconds (8.53 M allocations: 140.497 MiB, 6.06% gc time, 20.67% compilation time)

And changing to haskey  
~]$ julia euler2.jl  
144(27, 84)(110, 133)  
144(27, 110)(84, 133)  
144(84, 110)(27, 133)  
144(27, 133)(84, 110)  
144(84, 133)(27, 110)  
144(110, 133)(27, 84)  
0.612808 seconds (6.04 M allocations: 102.580 MiB, 4.02% gc time, 21.72% compilation time)

~30 ms faster

---

<div class="post-metadata">

**Author:** ![dmolina](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dmolina/32/5246_2.png) [@dmolina](https://discourse.julialang.org/u/dmolina)\
**Post date:** [June 23, 2022, 7:08pm UTC](https://discourse.julialang.org/t/julia-vs-python-eulers-sum-of-powers-conjecture/83262/5 "2022-06-23T19:08:17Z")

</div>

You should check the suggestion from @math_opt. A simple definition of types:

```julia
function main()
    MAX = 250
    p5 = Dict{Int,Int}()
    sum2 = Dict{Int,Tuple{Int, Int}}()
    sk = Int64[]

    for i in range(1, MAX)
        p5[i^5] = i
        for j in range(i, MAX)
            sum2[i^5 + j^5] = (i, j)
        end
    end

    sk = sort(collect(keys(sum2)))

    @inbounds for p in sort(collect(keys(p5)))
        for s in sk
            if p <= s ; break ; end
            if p - s in keys(sum2)
                println(p5[p], sum2[s], sum2[p-s])   
                # exit()
            end
        end
    end
end

main()

```

Give me similar results than using Python.

```nohighlight
time python euler.py
144 (27, 84, 110, 133)
144 (27, 110, 84, 133)
144 (84, 110, 27, 133)
144 (27, 133, 84, 110)
144 (84, 133, 27, 110)
144 (110, 133, 27, 84)

real	0m0.696s
user	0m0.686s
sys	0m0.009s

```

And using Julia:

```julia
time julia euler2.jl 
144(27, 84)(110, 133)
144(27, 110)(84, 133)
144(84, 110)(27, 133)
144(27, 133)(84, 110)
144(84, 133)(27, 110)
144(110, 133)(27, 84)

real	0m0.625s
user	0m0.695s
sys	0m0.257s

```

However, the source code can be improved a lot.

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [June 23, 2022, 7:39pm UTC](https://discourse.julialang.org/t/julia-vs-python-eulers-sum-of-powers-conjecture/83262/6 "2022-06-23T19:39:11Z")

</div>

> [@math\_opt](#):
>
> I guess the question is better suited for the [performance](https://discourse.julialang.org/c/usage/perf) category

I’ve moved it to performance.

---

<div class="post-metadata">

**Author:** ![Jeff\_Emanuel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeff_emanuel/32/15440_2.png) [@Jeff\_Emanuel](https://discourse.julialang.org/u/Jeff_Emanuel)\
**Post date:** [June 23, 2022, 8:17pm UTC](https://discourse.julialang.org/t/julia-vs-python-eulers-sum-of-powers-conjecture/83262/7 "2022-06-23T20:17:00Z")

</div>

> [@dmolina](#):
>
> A simple definition of types

For OP’s reference, that’s the fifth tip here [Performance Tips · The Julia Language](https://docs.julialang.org/en/v1/manual/performance-tips).

---

<div class="post-metadata">

**Author:** ![aplavin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/aplavin/32/222056_2.png) [@aplavin](https://discourse.julialang.org/u/aplavin)\
**Post date:** [June 23, 2022, 8:39pm UTC](https://discourse.julialang.org/t/julia-vs-python-eulers-sum-of-powers-conjecture/83262/8 "2022-06-23T20:39:43Z")

</div>

Note that types don’t have to be specified by hand. For example, the for-loop

```julia
  p5 = Dict()
  sum2 = Dict()
  sk = []

  for i in range(1, MAX)
       p5[i^5] = i
       for j in range(i, MAX)
               sum2[i^5 + j^5] = (i, j)
       end
  end

```

can be replaced with

```julia
p5 = Dict([i^5 => i for i in 1:MAX])
sum2 = Dict([i^5 + j^5 => (i, j) for i in 1:MAX for j in i:MAX])

```

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [June 23, 2022, 8:41pm UTC](https://discourse.julialang.org/t/julia-vs-python-eulers-sum-of-powers-conjecture/83262/9 "2022-06-23T20:41:46Z")

</div>

> [@Jeff\_Emanuel](#):
>
> > [@jgforbes](#):
> >
> > `p - s in keys(sum2)`
> 
> `haskey(sum2, p - s)` should be faster, O(1) vs O(n).

`x in keys(dict)` is O(1). The `keys(dict)` object is just a lazy wrapper, and has a [specialized `in` method](https://github.com/JuliaLang/julia/blob/master/base/dict.jl#L556) that is equivalent to `haskey`.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [June 23, 2022, 8:44pm UTC](https://discourse.julialang.org/t/julia-vs-python-eulers-sum-of-powers-conjecture/83262/10 "2022-06-23T20:44:40Z")

</div>

> [@dmolina](#):
>
> `sk = sort(collect(keys(sum2)))`

(Using `sort!` here would eliminate a temporary array.)

If you want to sort dictionaries by keys, you might consider using a [`SortedDict` data structure](https://juliacollections.github.io/DataStructures.jl/v0.9/sorted_containers.html#DataStructures.SortedDict-Union%7BTuple%7BOrd%7D,%20Tuple%7BOrd%7D%7D%20where%20Ord%3C:Base.Order.Ordering). However, in this case, since you only need to sort it once, I tried it and it is faster just to use an ordinary `Dict` and `sort!` at the end.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [June 23, 2022, 8:46pm UTC](https://discourse.julialang.org/t/julia-vs-python-eulers-sum-of-powers-conjecture/83262/11 "2022-06-23T20:46:23Z")

</div>

> [@aplavin](#):
>
> `p5 = Dict([i^5 => i for i in 1:MAX])`

This constructs an array, then copies it to a dictionary, then throws away the array. You can instead do `p5 = Dict(i^5 => i for i in 1:MAX)` to construct the dictionary directly with no intermediate array.

---

<div class="post-metadata">

**Author:** ![aplavin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/aplavin/32/222056_2.png) [@aplavin](https://discourse.julialang.org/u/aplavin)\
**Post date:** [June 23, 2022, 8:52pm UTC](https://discourse.julialang.org/t/julia-vs-python-eulers-sum-of-powers-conjecture/83262/12 "2022-06-23T20:52:16Z")

</div>

> [@stevengj](#):
>
> You can instead do `p5 = Dict(i^5 => i for i in 1:MAX)` to construct the dictionary directly with no intermediate array.

For `p5` - yes, it’s likely better to use the generator.  
But for `sum2`, creating the array first

```julia
sum2 = Dict([i^5 + j^5 => (i, j) for i in 1:MAX for j in i:MAX])

```

is better for the function as a whole. This way is typestable, while

```julia
sum2 = Dict(i^5 + j^5 => (i, j) for i in 1:MAX for j in i:MAX)

```

is not, and `sum2` wouldn’t fully infer in the remaining part of the function. Maybe, this will be made more inferrable in a future julia version…

---

<div class="post-metadata">

**Author:** ![Jeff\_Emanuel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeff_emanuel/32/15440_2.png) [@Jeff\_Emanuel](https://discourse.julialang.org/u/Jeff_Emanuel)\
**Post date:** [June 23, 2022, 8:55pm UTC](https://discourse.julialang.org/t/julia-vs-python-eulers-sum-of-powers-conjecture/83262/13 "2022-06-23T20:55:23Z")

</div>

Good to know. Thanks. I read a doc string for `keys` that said it returned an iterator. I must not have looked closely enough to find the specialized method.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [June 23, 2022, 8:57pm UTC](https://discourse.julialang.org/t/julia-vs-python-eulers-sum-of-powers-conjecture/83262/14 "2022-06-23T20:57:37Z")

</div>

> [@aplavin](#):
>
> This way is typestable, while
> 
> ```julia-auto
> sum2 = Dict(i^5 + j^5 => (i, j) for i in 1:MAX for j in i:MAX)
> 
> ```
> 
> is not, and `sum2` wouldn’t fully infer in the remaining part of the function. Maybe, this will be made more inferrable in a future julia version…

Yes, you have to do:

```julia-auto
sum2 = Dict{Int,Tuple{Int,Int}}(i^5 + j^5 => (i, j) for i in 1:MAX for j in i:MAX)

```

---

<div class="post-metadata">

**Author:** ![jgforbes](https://avatars.discourse-cdn.com/v4/letter/j/9de0a6/32.png) [@jgforbes](https://discourse.julialang.org/u/jgforbes)\
**Post date:** [June 23, 2022, 8:59pm UTC](https://discourse.julialang.org/t/julia-vs-python-eulers-sum-of-powers-conjecture/83262/15 "2022-06-23T20:59:20Z")

</div>

I had already tried the [`SortedDict`](https://juliacollections.github.io/DataStructures.jl/v0.9/sorted_containers.html#DataStructures.SortedDict-Union%7BTuple%7BOrd%7D,%20Tuple%7BOrd%7D%7D%20where%20Ord%3C:Base.Order.Ordering) and found that it was slower. I will compare sort with sort!.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [June 23, 2022, 10:23pm UTC](https://discourse.julialang.org/t/julia-vs-python-eulers-sum-of-powers-conjecture/83262/16 "2022-06-23T22:23:15Z")

</div>

```julia
function main(MAX=250)
    p5 = Dict(i^5=>i for i in 1:MAX)
    sum2 = Dict{Int,Tuple{Int,Int}}((i^5 + j^5) => (i, j) for i in 1:MAX, j in 1:MAX)
    
    sk = sort!(collect(keys(sum2)))
    for p in sort!(collect(keys(p5)))
        for s in sk
            p <= s && break
            if p - s in keys(sum2)
                println(p5[p], sum2[s], sum2[p-s])   
            end
        end
    end
    return nothing
end

```

```julia
julia> main()
144(27, 84)(110, 133)
144(27, 110)(84, 133)
144(84, 110)(27, 133)
144(27, 133)(84, 110)
144(84, 133)(27, 110)
144(110, 133)(27, 84)

```

```julia
julia> @btime main()
⋮ (omitted output)
48.210 ms (362 allocations: 3.39 MiB)

```

---

<div class="post-metadata">

**Author:** ![jgforbes](https://avatars.discourse-cdn.com/v4/letter/j/9de0a6/32.png) [@jgforbes](https://discourse.julialang.org/u/jgforbes)\
**Post date:** [June 24, 2022, 12:13am UTC](https://discourse.julialang.org/t/julia-vs-python-eulers-sum-of-powers-conjecture/83262/17 "2022-06-24T00:13:50Z")

</div>

The last response contained all of the previous suggestions to which I added a test  
to not print the duplicate results:

```julia
function main(MAX=250)
   p5 = Dict(i^5 => i for i in 1:MAX)
   sum2 = Dict{Int,Tuple{Int,Int}}((i^5 + j^5) => (i, j) for i in 1:MAX, j in 1:MAX)
   sk = sort!(collect(keys(sum2)))

   p5old=0
   for p in sort!(collect(keys(p5)))
        for s in sk
                p <= s && break
                if haskey(sum2, p - s)
                        if p5[p] != p5old
                           println(p5[p], sum2[s], sum2[p-s])
                           p5old=p5[p]
                        end
                end
        end
   end
   return nothing
end

@time main()
@time main()

```

~]$ julia euler4.jl  
144(27, 84)(110, 133)  
0.107246 seconds (96.74 k allocations: 8.776 MiB, 68.72% compilation time)  
144(27, 84)(110, 133)  
0.033693 seconds (75 allocations: 3.378 MiB)

For a comparison with python:

```julia
from time import perf_counter

tBeg = perf_counter ()

MAX = 250
p5, sum2 = {}, {}
 
for i in range(1, MAX):
    p5[i**5] = i
    for j in range(i, MAX):
        sum2[i **5 + j** 5] = (i, j)
 
sk = sorted(sum2.keys())
def methodC ():
    p5old=0
    for p in sorted(p5.keys()):
        for s in sk:
            if p <= s: break
            if p - s in sum2:
                if p5[p] != p5old:
                   yield p5[p], sum2[s] + sum2[p-s]
                   p5old = p5[p]

for v1, v2 in methodC ():
    print (v1, v2)
tEnd = perf_counter ()
print ("D", "MAX", MAX, "In", tEnd - tBeg, "seconds")

```

~]$ python euler4.py  
144 (27, 84, 110, 133)  
D MAX 250 In 0.3231038339999941 seconds  
Not sure if this Python is optimized, but it is slower by an order of magnitude.  
I will have to send these result to one of my friends who is a Python expert to see if they can  
squeeze more performance out of python.

Thanks to everyone who responded, The discussion was enlightening.  
I have much more to learn about using Julia efficiently.