1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889 |
- #!/usr/bin/julia
- # Trizen
- # 17 September 2016
- # https://github.com/trizen
- # A decently efficient algorithm for computing the results of the Kempner/Smarandache function.
- # See also: https://projecteuler.net/problem=549
- # https://en.wikipedia.org/wiki/Kempner_function
- # https://mathworld.wolfram.com/SmarandacheFunction.html
- # ∑S(i) for 2 ≤ i ≤ 10^2 == 2012
- # ∑S(i) for 2 ≤ i ≤ 10^6 == 64938007616
- # ∑S(i) for 2 ≤ i ≤ 10^8 == 476001479068717
- using Primes
- function smarandache(n::Int64, cache)
- isprime(n) && return n
- f = factor(n)
- count = 0
- distinct = true
- for v in values(f)
- count += v
- if (distinct && v != 1)
- distinct = false
- end
- end
- distinct && return maximum(keys(f))
- if (length(f) == 1)
- k = collect(keys(f))[1]
- (count <= k) && return k*count
- if haskey(cache, n)
- return cache[n]
- end
- max = k*count
- ff = factorial(BigInt(max - k))
- while (ff % n == 0)
- max -= k
- ff /= max
- end
- cache[n] = max
- return max
- end
- arr = Int64[]
- for (k,v) in f
- push!(arr, v == 1 ? k : smarandache(k^v, cache))
- end
- maximum(arr)
- end
- #
- ## Tests
- #
- function test()
- cache = Dict{Int64, Int64}()
- limit = 10^2
- sumS = 0
- for k in 2:limit
- sumS += smarandache(k, cache)
- end
- println("∑S(i) for 2 ≤ i ≤ $limit == $sumS")
- if (limit == 100 && sumS != 2012)
- warn("However that is incorrect! (expected: 2012)")
- end
- end
- test()
|