project-euler/Yet to solve/755 Not Zeckendorf.sf

#!/usr/bin/ruby

# Not Zeckendorf
# https://projecteuler.net/problem=755

# The sum hits powers of two at indices given by g(n).

func f(x,y,z) is cached {
    if (x < y) {
        return 0**x
    }
    f(x-y, y+z, y) + f(x, y+z, y)
}

func a(n) {
    f(n, 1, 1)
}

var sum = 0

func g(n) is cached {
    return 1 if (n == 1)
    return 1 if (n == 2)
    return 2 if (n == 3)
    return 3 if (n == 4)
    return 4 if (n == 5)
    return 5 if (n == 6)
    return 8 if (n == 7)
    g(n-2) + g(n-3) + g(n-4) - g(n-5) - g(n-7)
}

#a(1)=1, a(2)=1, a(3)=2, a(4)=3, a(5)=4, a(6)=5, a(7)=8, a(n)=a(n-2)+ a(n-3)+a(n-4)-a(n-5)-a(n-7)


#say g(30)
say bsearch_le(1..1e4, {|k|
    g(k) <=> 1e4
})

say bsearch_ge(1..1e4, {|k|
    g(k) <=> 1e4
})

say g(122)
say g(123)

#__END__
for k in (0..1e4) {

    sum += a(k)

    if (sum.is_power_of(2)) {
        say [k, sum]
    }
}

say sum

#say a(10000)
#say sum(0..12, a)
#say sum(0..128, a)

__END__
f(x, y, z)=if(x<y, 0^x, )

a(n)=f(n, 1, 1)