Re-posted from: https://blog.kdheepak.com/the-egg-tower-puzzle/index.html
Here is a fun puzzle:
Re-posted from: https://blog.kdheepak.com/the-egg-tower-puzzle/index.html
Here is a fun puzzle:
While watching the Mathologer masterclass on power sums
I came across a challenge to evaluate the following sum
This can be easily evaluated via brute force in Julia to yield
function power_cal(n) a=big(0) for i=1:n a+=big(i)^10 end a end julia> power_cal(1000) 91409924241424243424241924242500
Note the I had to use big
to makes sure we are using BigInt
in the computation. Without that, we would be quickly running in into an overflow issue and we will get a very wrong number.
In the comment section of the video I found a very elegant solution to the above sum, expressed as
(1/11) * 1000^11 + (1/2) * 1000^10 + (5/6) * 1000^9 – 1000^7 + 1000^5-(1/2) * 1000^3 + (5/66) * 1000 = 91409924241424243424241924242500
If I try to plug this into the Julia, I get
julia> (1/11) * 1000^11 + (1/2) * 1000^10 + (5/6) * 1000^9 - 1000^7 + r1000^5-(1/2) * 1000^3 + (5/66) * 1000 -6.740310541071357e18
This negative answer is not surprising at all, because we obviously ran into an overflow. We can, of course, go through that expression and modify all instances of Int64
with BigInt
by wrapping it in the big
function. But that would be cumbersome to do by hand.
In Julia, metaprogramming allows you to write code that creates code, the idea here to manipulate the abstract syntax tree (AST) of a Julia expression. We start to by “quoting” our original mathematical expressing into a Julia expression. In the at form it is not evaluated yet, however we can always evaluate it via eval
.
julia> ex1=:((1/11) * 1000^11 + (1/2) * 1000^10 + (5/6) * 1000^9 - 1000^7 + 1000^5-(1/2) * 1000^3 + (5/66) * 1000) :((((((1 / 11) * 1000 ^ 11 + (1 / 2) * 1000 ^ 10 + (5 / 6) * 1000 ^ 9) - 1000 ^ 7) + 1000 ^ 5) - (1 / 2) * 1000 ^ 3) + (5 / 66) * 1000) julia> dump(ex1) Expr head: Symbol call args: Array{Any}((3,)) 1: Symbol + 2: Expr head: Symbol call args: Array{Any}((3,)) 1: Symbol - 2: Expr head: Symbol call args: Array{Any}((3,)) 1: Symbol + 2: Expr head: Symbol call args: Array{Any}((3,)) 1: Symbol - 2: Expr 3: Expr 3: Expr head: Symbol call args: Array{Any}((3,)) 1: Symbol ^ 2: Int64 1000 3: Int64 5 3: Expr head: Symbol call args: Array{Any}((3,)) 1: Symbol * 2: Expr head: Symbol call args: Array{Any}((3,)) 1: Symbol / 2: Int64 1 3: Int64 2 3: Expr head: Symbol call args: Array{Any}((3,)) 1: Symbol ^ 2: Int64 1000 3: Int64 3 3: Expr head: Symbol call args: Array{Any}((3,)) 1: Symbol * 2: Expr head: Symbol call args: Array{Any}((3,)) 1: Symbol / 2: Int64 5 3: Int64 66 3: Int64 1000 julia> eval(ex1) -6.740310541071357e18
The output of dump
show the follow AST in all its glory (…well almost the depth is a bit truncated). Notice that here all our numbers are interpreted as Int64
.
Now we walk through the is AST and change all occurrences of Int64
with BigInt
by using the big
function.
function makeIntBig!(ex::Expr) args=ex.args for i in eachindex(args) if args[i] isa Int64 args[i]=big(args[i]) end if args[i] isa Expr makeIntBig!(args[i]) end end end julia> ex2=copy(ex1) :((((((1 / 11) * 1000 ^ 11 + (1 / 2) * 1000 ^ 10 + (5 / 6) * 1000 ^ 9) - 1000 ^ 7) + 1000 ^ 5) - (1 / 2) * 1000 ^ 3) + (5 / 66) * 1000) julia> makeIntBig!(ex2) julia> eval(ex2) 9.14099242414242434242419242425000000000000000000000000000000000000000000000014e+31
We see an improvement here, but the results are not very satisfactory. The divisions yield BigFloat
results, which had a tiny bit of floating point errors. Can we do better?
Julia has support for Rational
expressions baked in. We can use that improve the results. We just need to search for call
expressions the /
symbol and replace it by the //
symbol. For safety we just have to makes sure the operands are as subtype of Integer
.
function makeIntBig!(ex::Expr) args=ex.args if ex.head == :call && args[1]==:/ && length(args)==3 && all(x->typeof(x) <: Integer,args[2:end]) args[1]=:// args[2]=big(args[2]) args[3]=big(args[3]) else for i in eachindex(args) if args[i] isa Int64 args[i]=big(args[i]) end if args[i] isa Expr makeIntBig!(args[i]) end end end end julia> ex2=copy(ex1); julia> makeIntBig!(ex2) julia> eval(ex2) 91409924241424243424241924242500//1
Now that is much better! We have not lost any precision and we ended us with a Rational
expression.
Finally, we can build a macro
so the if we run into such expressions in the future and we want to evaluate them, we could just conveniently call it.
macro eval_bigInt(ex) makeIntBig!(ex) ex end
and we can now simply evaluate our original expression as
julia> @eval_bigInt (1/11) * 1000^11 + (1/2) * 1000^10 + (5/6) * 1000^9 - 1000^7 + 1000^5-(1/2) * 1000^3 + (5/66) * 1000 91409924241424243424241924242500//1
Recently I came across a fascinating Numberphile video on truncatable primes
I immediately thought it would be cool to whip a quick Julia code to get the full enumeration of all left truncatable primes, count the number of branches and also get the largest left truncatable prime.
using Primes function get_left_primes(s::String) p_arr=Array{String,1}() for i=1:9 number_s="$i$s" if isprime(parse(BigInt, number_s)) push!(p_arr,number_s) end end p_arr end function get_all_left_primes(l) r_l= Array{String,1}() n_end_points=0 for i in l new_l=get_left_primes(i) isempty(new_l) && (n_end_points+=1) append!(r_l,new_l) next_new_l,new_n=get_all_left_primes(new_l) n_end_points+=new_n # counting the chains append!(r_l,next_new_l) end r_l, n end
The first function just prepends a number (expressed in String for convenience) and checks for it possible primes that can emerge from a single digit prepending. For example:
julia> get_left_primes("17") 2-element Array{String,1}: "317" "617"
The second function, just makes extensive use of the first to get all left truncatable primes and also count the number of branches.
julia> all_left_primes, n_branches=get_all_left_primes([""]) (String["2", "3", "5", "7", "13", "23", "43", "53", "73", "83" … "6435616333396997", "6633396997", "76633396997", "963396997", "16396997", "96396997", "616396997", "916396997", "396396997", "4396396997"], 1442) julia> n_branches 1442 julia> all_left_primes 4260-element Array{String,1}: "2" "3" "5" "7" "13" "23" ⋮ "96396997" "616396997" "916396997" "396396997" "4396396997"
So we the full list of possible left truncatable primes with a length 4260. Also the total number of branches came to 1442.
We now get the largest left truncatable primes with the following one liner:
julia> largest_left_prime=length.(all_left_primes)|>indmax|> x->all_left_primes[x] "357686312646216567629137"
After this fun exploration, I found an implementation in Julia for just getting the largest left truncatable prime for any base in Rosseta Code.