# 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:** 20\
**Page:** 1

<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 21, 2019, 1:22pm UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/1 "2019-10-21T13:22:33Z")

</div>

Hi,

I am doing some small algorithmic puzzles from the Euler Project. I have a working solution in code for P164 but it is so slow that I fear that I am doing something wrong. Could someone give me tips how to make my code perform better?

```julia
function iterate_3(number)
    truth_array = []
    array = reverse(digits(number))
    for i in 1:(length(array) - 2)
       +(array[i],array[i+1],array[i+2]) <= 9 ? continue : push!(truth_array,1000)
    end
    if isempty(truth_array) 
        return number
    end
end
function consecutive_3(begin_point,end_point)
    results = []
    for i in begin_point:end_point
        if iterate_3(i) != nothing
            push!(results,i)
        end
    end
    return length(results)
end

```

This is the execution code

```julia
consecutive_3(10000000000000000000,19999999999999999999)

```

This is the link:

> **[\#164 Three Consecutive Digital Sum Limit - Project Euler](https://projecteuler.net/problem=164)**
>
> A website dedicated to the fascinating world of mathematics and programming

thanks in advance!

---

<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 21, 2019, 1:36pm UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/2 "2019-10-21T13:36:04Z")

</div>

Don’t push to array just keep a counter for one.

---

<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 21, 2019, 1:56pm UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/3 "2019-10-21T13:56:07Z")

</div>

thanks running the new code now!

---

<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 21, 2019, 2:16pm UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/4 "2019-10-21T14:16:21Z")

</div>

First of all, I suggest checking your performance with `@btime` from `BenchmarkTools`. This way you can see if you are making any performance improvements with your code changes.  
If I do that with `n = 1000000`, you clock in at `345.713 ms (4348978 allocations: 422.86 MiB)` … wait what, 4 million allocations for counting something?

If you have a function like `iterate_3` the usual way to do something like that is

```julia
for a in b
    if the_thing_is_not_like_I_want_it
        return false
    end
end
# if we are still here that means the thing must be fine!
return true

```

Currently you use an array, but you push a value you don’t care about (`1000`) to the array, and you only ever check if _anything_ is there.

Also, why do you reverse your array? This allocates a new array every time you do it. If you really need to reverse it, you can use `reverse!`, which reverses in place without allocating a new array. Speaking of which, the same is possible for `digits -> digits!`.

All of that aside. You want to count through roughly `1e19` numbers. Lets say you can do each check in 1ns (not true, but let’s assume). That means you need `1e10` seconds or roughly 300 years to do this.  
This means (as it is almost always the case with Euler Project problems) you need to think of a clever algorithm to do this. Simply going through every number won’t cut it.

As a pointer: you go from `10000000000000000000` to `19999999999999999999`. By just looking at the last number, I know that you will be checking roughly `999999999999999999` numbers too many, because if your number starts with `19` we are done already. You can only go up to `180...`. Also, what’s up with `20000000000000000000`? You stop just shy of that, but this number is okay, no?  
Instead of thinking about the performance of your code snippet, you’ll have to look more closely at your algorithm first.

---

<div class="post-metadata">

**Author:** ![tamasgal](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamasgal/32/27946_2.png) [@tamasgal](https://discourse.julialang.org/u/tamasgal)\
**Post date:** [October 21, 2019, 2:32pm UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/5 "2019-10-21T14:32:02Z")

</div>

Btw. just a tiny remark: you are more or less doing the _bruteforce solution_ for the problem, basically transforming the problem description one by one to computer instructions. Project Euler problems can be solved quite nicely by doing some maths first which often highly reduce the computational complexity by redefining the way you address the problem.

---

<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 22, 2019, 6:28am UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/6 "2019-10-22T06:28:49Z")

</div>

I agree, finding ways to abstract my thinking about the problem.

---

<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 22, 2019, 6:36am UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/7 "2019-10-22T06:36:17Z")

</div>

In regards to the range, I was testing. It would go further. I will update the code, I am interested to see the gain. However, I agree with @tamasgal that the brute force approach is ineffective.

---

<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 22, 2019, 8:07am UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/8 "2019-10-22T08:07:02Z")

</div>

@AlexanderChen I was having fun with this problem and I think the largest you need to count up to is

```julia
largest = Int128(sum(Int128.(exp10.(0:19)).*8)) |> digits

largest[1:2:end-1] .= 0

sum([largest[k]*Int128(10)^(k-1) for k=1:length(largest)])

```

which is

```julia-repl
80808080808080808080

```

This should cut down 10% of running time in the brute-force approach. Any number larger than the above is automatically failing the condition (I think).

Also, any number with a 9 in it is automatically out. So you just need to count the number with 9 as a digit? Actually, it’s easier to count the number of number WITHOUT 9 and deduce the number with 9.

So you can choose from nine digits (0, 1, 2, …, 8) and place them into 20 digits, so that’s 9^20 choices, but the first digit can only be (1,…8) so that’s 8\*9^19.

Hopefully that’s not too many hints. Actually there is no guarantee these hints are useful. But those are my first thoughts. Hope it’s at least another perspective for you to consider. Have fun!

---

<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:** [October 22, 2019, 8:56am UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/9 "2019-10-22T08:56:19Z")

</div>

I agree that you should not create an array, unless you care about its contents (which you don’t do here). But whenever you _are_ using arrays, don’t do this:

> [@AlexanderChen](#):
>
> ```julia
> truth_array = []
> 
> ```

If your code contains a line like this, it’s a bad sign for performance. This creates a `Array{Any, 1}` which is the _slow_ kind of array. Make sure that the array is appropriately typed, in this case it should be

```julia
truth_array = Int[]

```

---

<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 22, 2019, 10:41am UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/10 "2019-10-22T10:41:58Z")

</div>

@DNF: Thank you! This is a very helpful tip. Since I do that a lot 🙂

---

<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 22, 2019, 10:46am UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/11 "2019-10-22T10:46:38Z")

</div>

> Also, any number with a 9 in it is automatically out.

The sum can’t be _greater_ than 9, so 1009001 would be fine, for example.

---

<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 22, 2019, 11:00am UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/12 "2019-10-22T11:00:19Z")

</div>

I misrea the question  
Should ve

900900…

---

<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 22, 2019, 12:56pm UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/13 "2019-10-22T12:56:42Z")

</div>

I thought so, just wanted to make sure no one goes off on the wrong track 😃

By the way @AlexanderChen , thanks for getting me back into Euler problems, fun problem!

---

<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 22, 2019, 2:43pm UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/14 "2019-10-22T14:43:59Z")

</div>

@Karajan, your welcome! I have implemented your adjustments and I see a gain in performance. But I need to find a more abstract solution because, thinking recursive but not sure if that is the right approach yet.

---

<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 23, 2019, 4:47am UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/15 "2019-10-23T04:47:53Z")

</div>

Hehe. Happy to share my solution if u want. It’s sub second performance

---

<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 23, 2019, 9:43am UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/16 "2019-10-23T09:43:23Z")

</div>

I also can share my solution which is unbelievably fast, `25 μs`, but contains some black magic of course 😉 .

---

<div class="post-metadata">

**Author:** ![non-Jedi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/non-jedi/32/3645_2.png) [@non-Jedi](https://discourse.julialang.org/u/non-Jedi)\
**Post date:** [October 23, 2019, 3:39pm UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/17 "2019-10-23T15:39:52Z")

</div>

@xiaodai @Seif_Shebl as an FYI Project Euler requests that you not share your answers to questions in public so that others can have the experience of solving them themselves. I think they said somewhere on the site that accounts can be banned for violating that rule. Looking around the internet, that ship has probably sailed, but do with this info as you will.

---

<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 23, 2019, 9:34pm UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/18 "2019-10-23T21:34:07Z")

</div>

Thanks. Wouldnt hurt to DM to share a soln in private to provide another perspective

---

<div class="post-metadata">

**Author:** ![klaff](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/klaff/32/7637_2.png) [@klaff](https://discourse.julialang.org/u/klaff)\
**Post date:** [October 23, 2019, 11:53pm UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/19 "2019-10-23T23:53:00Z")

</div>

I agree, don’t post the 25 microsecond solution. I wrote one that takes on the order of an hour. Much better than 300 years, but I’ve got some ideas to crank up the speed and don’t want a spoiler!

---

<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 24, 2019, 6:50am UTC](https://discourse.julialang.org/t/euler-project-p-164/30135/20 "2019-10-24T06:50:56Z")

</div>

@Seif_Shebl: I agree with @xiaodai that it wouldn’t hurt to see another perspective.

Having said that I have formulate two possible approaches.

1. randomly choose the first two digits 1-9, 0-9 which combined less or equal to 9 and than randomly add a digit from a selected range. e.g. if we begin with 14 then we randomly select between the range [0:4]. this continues until we have 20 digits which will be stored. Repeat X times.

2. starting point is identical but the main difference is that all valid permutations will be calculated. E.g. if we begin with 14 than all the elements of the range of [0:4] will be calculated until we reach the 20 digits. So you get a very dense tree structure.

In option 1, I think the main problem is that we leave to much over to randomness and as a result it needs to run a lot.

in option 2, this way I think you can truly calculate all the possibilities. But I am not sure how this should be coded + if this type of recursive method is something Julia will like to do.

feedback? Please be gentle 🙂

best,

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