Help speedup a brute-force solution

General Usage Performance
12

Well, thank you all for your contributions, I learned from this a lot. Now when I think about it again, I realize that I was doing too many permutations prior to partitioning which resulted in too many repeated sets, most of them are not prime. Here I reversed that order and permuted only needed subsets. It is significantly faster now with few allocations.

using Primes 
using Combinatorics

mprime(k) = isprime(evalpoly(10,k))

function brute1180(n)
    total = 0
    for i in partitions(1:n)
        mul = 1
        for j in i
            mul *= sum(mprime, permutations(j))
            mul == 0 && break
        end 
        total += mul
    end 
    total
end

@btime brute1180(7)
  4.647 ms (77712 allocations: 6.37 MiB)
1205
1 Like