# Euler project - P 164

**URL:** <https://discourse.julialang.org/t/euler-project-p-164/30135>\
**Category:** Performance\
**Tags:** question\
**Created:** [October 21, 2019, 1:22pm UTC](https://discourse.julialang.org/t/euler-project-p-164/30135 "2019-10-21T13:22:33Z")\
**Posts on this page:** 11\
**Page:** 2

<div class="post-metadata">

**Author:** ![Karajan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/karajan/32/8545_2.png) [@Karajan](https://discourse.julialang.org/u/Karajan)\
**Post date:** [October 24, 2019, 4:00pm UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/21 "2019-10-24T16:00:47Z")

</div>

I agree that using randomness makes this difficult since you want an exact result and randomness doesn’t really lend itself towards that.

Yes, implementation can be tricky. I suggest starting with the most straight forward implementation you can think of and only optimize after you have confirmed that the algorithm is correct/promising and you need the increase in speed.

I will also remind you that you only care about the total count, not which numbers make up that count.  
I think most other things, including finding out if your idea is on the right track or not, should be in your hands. If you have a Julia specific question I’m sure we can help you out. Best of luck!

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [October 24, 2019, 10:39pm UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/22 "2019-10-24T22:39:06Z")

</div>

> [@AlexanderChen](#):
>
> option 2

When we think recursion we often think top to bottom like 5! = 5_4! etc. The other way to think of it is to build from bottom to top e.g. 0! = 1, 1 = 1_0!, 2 = 2_1! = 2, 3 = 3_2! = 3 \* 2 = 6 etc.

---

<div class="post-metadata">

**Author:** ![mhw](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mhw/32/8469_2.png) [@mhw](https://discourse.julialang.org/u/mhw)\
**Post date:** [October 24, 2019, 10:39pm UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/23 "2019-10-24T22:39:27Z")

</div>

For Haskell you can find a very elegant solution here:  
[https://wiki.haskell.org/Euler\_problems/161\_to\_170#Problem\_164](https://wiki.haskell.org/Euler_problems/161_to_170#Problem_164)  
Probably you have to invest some time for understanding the details as the program has no explanations. However it should be easy to transform this solution into a Julia program.

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [October 24, 2019, 10:42pm UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/24 "2019-10-24T22:42:51Z")

</div>

BTW my solution is about 40 lines long and not as fast others but just think that it can be very fast! Hope that will be the encourage to spur you on!

![image](https://global.discourse-cdn.com/julialang/original/3X/d/9/d9e04dd07633d3983caed94e70479bcd0dc6935c.png)

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [October 24, 2019, 10:43pm UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/25 "2019-10-24T22:43:13Z")

</div>

Please don’t post solutions out of respect for the project euler maintainers.

---

<div class="post-metadata">

**Author:** ![AlexanderChen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/alexanderchen/32/22007_2.png) [@AlexanderChen](https://discourse.julialang.org/u/AlexanderChen)\
**Post date:** [October 25, 2019, 10:35am UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/26 "2019-10-25T10:35:01Z")

</div>

@xiaodai: agreed.

---

<div class="post-metadata">

**Author:** ![AlexanderChen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/alexanderchen/32/22007_2.png) [@AlexanderChen](https://discourse.julialang.org/u/AlexanderChen)\
**Post date:** [October 25, 2019, 10:38am UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/27 "2019-10-25T10:38:48Z")

</div>

got the hint!

---

<div class="post-metadata">

**Author:** ![j2b2](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/j2b2/32/3387_2.png) [@j2b2](https://discourse.julialang.org/u/j2b2)\
**Post date:** [October 25, 2019, 5:33pm UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/28 "2019-10-25T17:33:07Z")

</div>

I think everyone gets essentially the same solution, after some reflection. But I noticed something weird with Julia. I wrote the following line inside my definition of the function `P` that solves the problem (I don’t give here the full code, because of the rules of the Euler project):

```julia
   beta[i, j] = sum(alpha[j, 1 : 12-i-j])

```

and got this benchmark:

```julia
  julia> using BenchmarkTools
  julia> @btime P(20);
  64.186 μs (993 allocations: 115.05 KiB)

```

These numerous allocations are due to the usage of the function `sum`, they disappear if I replace it by the explicit loop:

```julia
  beta[i, j] = 0
  for k in 1 : 12-i-j
     beta[i, j] += alpha[j, k]
  end

```

Benchmark:

```julia
julia> @btime P(20);
  12.315 μs (3 allocations: 2.55 KiB)

```

I understand the phenomenon, but I think it’s sad.

---

<div class="post-metadata">

**Author:** ![Seif\_Shebl](https://avatars.discourse-cdn.com/v4/letter/s/eada6e/32.png) [@Seif\_Shebl](https://discourse.julialang.org/u/Seif_Shebl)\
**Post date:** [October 25, 2019, 7:23pm UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/29 "2019-10-25T19:23:54Z")

</div>

Yes, I agree it’s very sad that array slices allocate in Julia. I occasionally revert to Fortran for array-heavy codes for this exact reason. But let’s hope that some day this issue could be resolved. At the moment, you can use `views` or generators.

```julia
beta[i, j] = sum( view(alpha, j, 1:12-i-j) )
# OR
beta[i, j] = sum( alpha[j, k] for k in 1:12-i-j )

```

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [October 25, 2019, 9:50pm UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/30 "2019-10-25T21:50:12Z")

</div>

> [@j2b2](#):
>
> beta[i, j] = sum(alpha[j, 1 : 12-i-j])

A less intrusive way of using views is with the macros `@view / @views`

```julia
@views beta[i, j] = sum(alpha[j, 1 : 12-i-j])
beta[i, j] = sum(@view alpha[j, 1 : 12-i-j])

```

---

<div class="post-metadata">

**Author:** ![j2b2](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/j2b2/32/3387_2.png) [@j2b2](https://discourse.julialang.org/u/j2b2)\
**Post date:** [October 27, 2019, 4:31pm UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/31 "2019-10-27T16:31:49Z")

</div>

@Seif_Shebl and @baggepinnen : thanks ! For the record, here is a benchmark for code modified along your suggestions; with:

```julia
  beta[i, j] = sum(@view alpha[j, 1 : 12-i-j])

```

I get:

```julia
  julia> using BenchmarkTools
  julia> @btime P(20);
  22.883 μs (993 allocations: 64.42 KiB)

```

Memory allocations are less expensive, but don’t disappear (the line of code I’m talking about is indeed executed 18\*55 = 990 times, and there are three obvious allocations in my code, e.g. when matrices `alpha`, `beta` are defined).

Solution with generator is worse:

```julia
  beta[i, j] = sum(alpha[j, k] for k in 1 : 12-i-j)

```

gives:

```julia
  julia> @btime P(20);
  28.449 μs (1983 allocations: 64.42 KiB)

```

(I don’t understand why the number of allocations is twice the preceeding one, whereas the amount of memory allocated is the same).

[Previous page](https://discourse.julialang.org/t/euler-project-p-164/30135.md?page=1)