versioninfo()

function fib_n(n::Integer)
    d = Dict(zero(n)=>big"0", one(n)=>big"1")
    fib_n(n, d)
end
function fib_n(n, d)
    if haskey(d, n)
        return d[n]
    end
    if n < 0
        result = iseven(n) ? -fib_n(-n, d) : fib_n(-n, d)
        d[n] = result
        return result
    end
    m = n ÷ 2
    result = if iseven(n)
        (2 * fib_n(m - 1, d) + fib_n(m, d)) * fib_n(m, d)
    else
        fib_n(m, d) ^ 2 + fib_n(m + 1, d) ^ 2
    end
    d[n] = result
    return result
end

struct FibType end
const Fib = FibType()

Base.getindex(::FibType, index::Integer) = fib_n(index)

Fib[10]

[Fib[n] for n=1:10]

Fib[5000]

struct FibRange{R<:AbstractRange{<:Integer}}
    range::R
end

Base.getindex(::FibType, r::AbstractRange{<:Integer}) = FibRange(r)

Fib[1:10]

Base.IteratorEltype(::Type{<:FibRange}) = Base.HasEltype()

# Base.eltype(fr::FibRange) = BigInt
Base.eltype(::Type{<:FibRange}) = BigInt

Base.IteratorSize(::Type{<:FibRange}) = Base.HasShape{1}()

Base.length(fr::FibRange) = length(fr.range)

Base.size(fr::FibRange) = size(fr.range)

function Base.iterate(fr::FibRange{<:UnitRange})
    index = fr.range.start
    start = Fib[index]
    prev = Fib[index - 1]
    len = length(fr)
    iterate(fr, (start, prev, len))
end
function Base.iterate(fr::FibRange{<:UnitRange}, (current, prev, len)::Tuple{BigInt, BigInt, Int})
    len <= 0 && return nothing
    (current, (current + prev, current, len - 1))
end

fib_1_10 = Fib[1:10]

for v in fib_1_10
    println(v)
end

collect(fib_1_10)

collect(fib_1_10) == [Fib[n] for n=1:10]

sum(fib_1_10)

print(collect(Fib[-5:5]))

@time [Fib[n] for n=1:100]

@time collect(Fib[1:100])

function Base.iterate(fr::FibRange{<:StepRange})
    n = fr.range.start
    m = oftype(n, fr.range.step)
    d = Dict(zero(n)=>big"0", one(n)=>big"1")
    fₙ = fib_n(n, d)
    fₙ₋₁ = fib_n(n - one(n), d)
    fₘ = fib_n(m, d)
    fₘ₋₁ = fib_n(m - one(n), d)
    len = length(fr)
    iterate(fr, (fₙ, fₙ₋₁, fₘ, fₘ₋₁, len))
end

function Base.iterate(fr::FibRange{<:StepRange}, (fₙ, fₙ₋₁, fₘ, fₘ₋₁, len)::Tuple{BigInt, BigInt, BigInt, BigInt, Int})
    len <= 0 && return nothing
    fₙ₊ₘ = fₙ * fₘ + fₙ₋₁ * fₘ + fₙ * fₘ₋₁
    fₙ₊ₘ₋₁ = fₙ * fₘ + fₙ₋₁ * fₘ₋₁
    (fₙ, (fₙ₊ₘ, fₙ₊ₘ₋₁, fₘ, fₘ₋₁, len - 1))
end

fr2 = Fib[0:2:20]

for v in fr2
    println(v)
end

collect(Fib[10:-1:1])

sum(Fib[1:2:19]) == Fib[20]

collect(Fib[0:10:100])

collect(Fib[0:10:1000]) == [Fib[n] for n=0:10:1000]

@time [Fib[n] for n=0:10:1000]

@time collect(Fib[0:10:1000])

struct EndOfFib end

Base.lastindex(::FibType) = EndOfFib()

abstract type AbstractSequence{I<:Integer} end

struct UnitSequence{I<:Integer} <: AbstractSequence{I}
    start::I
end

struct StepSequence{I<:Integer} <: AbstractSequence{I}
    start::I
    step::I
end

Base.:(:)(start::Integer, ::EndOfFib) = UnitSequence(start)
Base.:(:)(start::I, step::I, ::EndOfFib) where {I<:Integer} = StepSequence(start, step)
Base.:(:)(start::Integer, step::Integer, ::EndOfFib) = StepSequence(promote(start, step)...)

struct FibSequence{S<:AbstractSequence}
    sequence::S
end

Base.getindex(::FibType, s::AbstractSequence) = FibSequence(s)

Base.IteratorEltype(::Type{<:FibSequence}) = Base.HasEltype()

# Base.eltype(fr::FibSequence) = BigInt
Base.eltype(::Type{<:FibSequence}) = BigInt

Base.IteratorSize(::Type{<:FibSequence}) = Base.IsInfinite()

function Base.iterate(fr::FibSequence{<:UnitSequence})
    index = fr.sequence.start
    start = Fib[index]
    prev = Fib[index - 1]
    iterate(fr, (start, prev))
end
function Base.iterate(fr::FibSequence{<:UnitSequence}, (current, prev)::Tuple{BigInt, BigInt})
    (current, (current + prev, current))
end

fibseq1 = Fib[0:end]

for v in fibseq1
    println(v)
    v >= 1000 && break
end

collect(Iterators.take(fibseq1, 21))

function Base.iterate(fr::FibSequence{<:StepSequence})
    n = fr.sequence.start
    m = oftype(n, fr.sequence.step)
    d = Dict(zero(n)=>big"0", one(n)=>big"1")
    fₙ = fib_n(n, d)
    fₙ₋₁ = fib_n(n - one(n), d)
    fₘ = fib_n(m, d)
    fₘ₋₁ = fib_n(m - one(n), d)
    iterate(fr, (fₙ, fₙ₋₁, fₘ, fₘ₋₁))
end
function Base.iterate(fr::FibSequence{<:StepSequence}, (fₙ, fₙ₋₁, fₘ, fₘ₋₁)::Tuple{BigInt, BigInt, BigInt, BigInt})
    fₙ₊ₘ = fₙ * fₘ + fₙ₋₁ * fₘ + fₙ * fₘ₋₁
    fₙ₊ₘ₋₁ = fₙ * fₘ + fₙ₋₁ * fₘ₋₁
    (fₙ, (fₙ₊ₘ, fₙ₊ₘ₋₁, fₘ, fₘ₋₁))
end

fibseq_m1 = Fib[0:-1:end]

collect(Iterators.take(fibseq_m1, 21))