[欧拉计划]Julia尝试 21:30 停更

综合讨论区
1

solution 21

ans: 40284

function solution_21() #这个算法太慢，需要优化
    d(a) = reduce(+,filter(x->a%x==0,1:a-1);init=0)

    iter = function iter(a,res)
        if a == 10000
            res
        else
            b = d(a)
            if a == d(b)
                iter(a+1,res+a)
            else
                iter(a+1,res)
            end
        end
    end

    iter(1,0)
end

solution 22

ans 871198282

function solution_22()  # 这里有个笔记，最好用Iterators.drop而不是Iterators.rest,
在这种尾递归里rest容易出错
    num_of_char(ch) = Int(lowercase(ch)) - Int('a') + 1
    name_score(name,index) = reduce(+,map(num_of_char,collect(name));init=0) * index
    names = sort(split(replace(read(open("names.txt"),String),"\""=>""),","))

    iter = function iter(n,names,res=name_score(first(names),n))
        if n == length(names)
            res
        else
            iter(n+1,Iterators.drop(names,1),res + name_score(first(Iterators.drop(names,1)),n+1))
        end
    end

    iter(1,names)
end

solution 25

ans 4782

function solution_25()
    first(first(Iterators.filter(has_1000_length,collect(Iterators.enumerate(Iterators.take(fib,10000))))))
end

Or

    @thread_as(Iterators.take(fib,10000), _ ,
               Iterators.enumerate(_),
               collect(_),
               Iterators.filter(has_1000_length,_),
               first(_),
               first(_))

好了，其他我实在没能力写下去了，学习是个慢慢积累的过程，我去积累知识了

2

solution 21

ans 40284

function solution21(n=10000)
    d(n)::Int=sum(x for x in 1:n-1 if n%x==0) # n>=2
    s=0
    for i in 2:n
        t=d(i)
        if t >1 && t <=n && d(t)==i
            s+=i
        end
    end
    s
end

看下我写的这个版本，速度比你的快一些，但是也只是快一些。

julia> @benchmark solution21()
BenchmarkTools.Trial: 
  memory estimate:  0 bytes
  allocs estimate:  0
  --------------
  minimum time:     252.120 ms (0.00% GC)
  median time:      252.237 ms (0.00% GC)
  mean time:        252.462 ms (0.00% GC)
  maximum time:     253.964 ms (0.00% GC)
  --------------
  samples:          20
  evals/sample:     1

julia> @benchmark solution_21()
BenchmarkTools.Trial: 
  memory estimate:  300.13 KiB
  allocs estimate:  19208
  --------------
  minimum time:     280.056 ms (0.00% GC)
  median time:      280.325 ms (0.00% GC)
  mean time:        280.356 ms (0.00% GC)
  maximum time:     280.745 ms (0.00% GC)
  --------------
  samples:          18
  evals/sample:     1

solution 22

ans 871198282

这个题我和你的答案不一样。用你的代码运行的结果是201407989.

function solution22()
    char2num(s)=Int(lowercase(s))-Int('a')+1
    name_score(name,idx)=sum(char2num(c) for c in name)*idx
    names = sort(split(replace(read("names.txt",String),"\""=>""),","))
    sum(name_score(names[i],i) for i in 1:length(names))
end

性能比较

julia> @benchmark solution22()
BenchmarkTools.Trial: 
  memory estimate:  452.08 KiB
  allocs estimate:  5206
  --------------
  minimum time:     1.325 ms (0.00% GC)
  median time:      1.354 ms (0.00% GC)
  mean time:        1.386 ms (1.98% GC)
  maximum time:     4.658 ms (66.18% GC)
  --------------
  samples:          3587
  evals/sample:     1

julia> @benchmark solution_22()
BenchmarkTools.Trial: 
  memory estimate:  1.23 MiB
  allocs estimate:  20180
  --------------
  minimum time:     3.207 ms (0.00% GC)
  median time:      3.310 ms (0.00% GC)
  mean time:        3.447 ms (3.18% GC)
  maximum time:     8.444 ms (52.85% GC)
  --------------
  samples:          1446
  evals/sample:     1

solution 23

ans: 4179871

function solution23()
    function is_abundant(n)
        n>=12 || return false
        s=0
        for i in 1:n-1
            if n%i==0
                s+=i
                if s>n
                    return true
                end
            end
        end
        return false
    end
    function is_sum_of_two_abundant(n,abundants=(x for x in 12:n-12 if is_abundant(x)))
        n>=24 || return false
        for i in abundants
            if i<=floor(Int,n/2) && is_abundant(n-i)
                return true
            end
        end
        return false
    end
    abundants=(x for x in 12:28123-12 if is_abundant(x))
    sum(1:28123)-sum(x for x in 24:28123 if is_sum_of_two_abundant(x,abundants))
end

这个性能太差劲了，跑了半个小时

julia> @time solution23()
1913.442859 seconds (113.24 k allocations: 4.163 MiB)

@nesteiner 你别鸽啊，我还是边看边学边写。

1 个赞
3

不得不鸽啊，数学还没学到呢

4

第23题你有思路吗，我搞了半天，弄不出来

5

代码都写出来了 ，肯定是有思路啊。首先用 is_abundant 判断是否是盈数，然后用is_sum_of_two_abundant 判断能否写成两个盈数之和，参数 aboundants 用于存储查找的 list. 最后把所有能写成两个盈数之和的数的和算出来，再用总和减去他们，就得到要的答案了。缺点是性能太差了

6

要不把list改成set?,这样查找会快点

7

我觉得是算法本身慢。应该从算法层面优化。就像之前的12题

8

过了一年多, 暑假没事干,又开始做这个了.

solution 23

ans: 4179871

23优化了下,现在只要10s 左右了,但是看别人的 cpp 秒出结果.

function solution23()
    function is_abundant(n)
        n>=12 || return false
        s=1
        i=2
        while i*i <=n
            a= n%i
            b=div(n,i)
            if a==0 
                if i != b
                    s+=i+b
                else 
                    s+=i
                end 
            end
            i+=1
            if s > n
                return true
            end
        end
        return false
    end
    abundants=(1:28123)[is_abundant.(1:28123)]
    function is_sum_of_two_abundant(n)
        n>=24 || return false
        for i in abundants
            if   i <n && (n-i) in abundants
                return true
            end
        end
        return false
    end
    sum(x for x in 1:28123 if !is_sum_of_two_abundant(x))
end

solution 24

ans: 2783915460

function solution24(n=1000000)
    nums=collect(0:9)
    P=permutations(nums)
    i=0
    for p in P
        i+=1
        if i ==n
            return collect(p)
        end
    end
end

solution 25

ans: 4782

function solution25(dig=1000)
    a = BigInt(1)
    b = BigInt(1)
    n = 2
    digits_n=length(digits(b))
    while digits_n <dig
        a,b=b,a+b
        n+=1
        digits_n=length(digits(b))
    end
    return n
end

solution 26

ans: 983

function  solution26(n=1000)
    rems=zeros(n)
    function cyclelen(x::Integer)
        loc=1
        @assert x>=1
        r=1
        d,r=divrem(r,x)
        while r!=0
            rems[loc]=r
            r*=10
            d,r=divrem(r,x)
            t=findfirst(x->x==r,rems[1:loc]) #第一个相同位置
            loc+=1 # 当前位置
            if !isnothing(t)
                return loc-t
            end
        end
        return 0
    end
    lens=cyclelen.(1:1000)
    findmax(lens)[2]
end

solution 27

ans: -59231

function solution27(ub=1000)
    maxcnt=0
    a0=0
    b0=0
    for a in -(ub-1):(ub-1)
        for b in -(ub-1):(ub-1)
            mycnt = primecounter(n-> n*n+a*n+b)
            if mycnt >= maxcnt
                a0=a
                b0=b
                maxcnt=mycnt
            end
        end
    end
    return a0*b0
end
function primecounter(f::Function)
    x=0
    out=f(x)
    cnt=0
    while isprime(out)
        cnt+=1 
        x+=1
        out=f(x)
    end
    return cnt
end
function isprime(n::Integer)
    n<= 1 && return false
    if iseven(n) && n!=2 
        return false
    end
    if n==3 
        return true
    end
    i=3
    while i*i <=n
        if n%i ==0
            return false
        end
        i+=2
    end
    return true
end

solution 28

ans: 669171001

function solution28(w::Integer=1001)
    @assert isodd(w)
    a(n)=n*n # anti-clockwise
    b(n)=a(n)-n+1
    c(n)=b(n)-n+1
    d(n)=c(n)-n+1
    s=0
    for i in 1:div(w,2)+1
        s+=a(2i-1)+b(2i-1)+c(2i-1)+d(2i-1)
    end
    s-=3 # 1 has been added for 4 times
end

solution 29

ans: 9183


function solution29(n=100)
    list=zeros(BigInt,99*99)
    i=1
    for a in 2:100
        for b in 2:100
            list[i]=BigInt(a)^b
            i+=1
        end
    end
    length(unique(list))
end

solution29()

solution 30

ans: 443839

function solution30(k=5)
    d=length(digits(9^k))+1
    sp_nums=Int[]
    for i in 2:10^d
        if i== sum(x->x^k,digits(i))
            push!(sp_nums,i)
        end
    end
    sum(sp_nums)
end
9

@Sukanka 请问有github仓库吗？ 论坛里一个一个搜好麻烦233

10

有的,(刚刚传上去)

1 个赞