experimental-projects/oeis-research/Ilya Gutkovskiy/Smallest positive integer which can be represented as the sum of distinct positive Fibonacci n-step numbers (with a single type of 1) in exactly n ways, or -1 if no such integer exists/prog.sf

#!/usr/bin/ruby

# a(n) is the smallest positive integer which can be represented as the sum of distinct positive Fibonacci n-step numbers (with a single type of 1) in exactly n ways, or -1 if no such integer exists.
# https://oeis.org/A359631

# Known terms:
#   1, 3, 44, 416, 26815, 464031

func isok(n, k) {

    var arr = []

    Inf.times {|j|
        var t = j.fib(k)
        if (t <= n) {
            arr << t
        }
        else {
            break
        }
    }

    arr.uniq!
    arr.grep!{_>0}

    #~ var s = Set(arr...)

    var sol = []

    for k in (0..arr.len) {
        arr.combinations(k, {|*a|

            if (a.sum == n) {
                sol << a
            }

            #~ with (n - a.sum) {|d|
                #~ if (s.has(d) && !a.has(d)) {
                    #~ sol << a
                #~ }
            #~ }
        })
    }

    #~ arr.combinations(k-1, {|*a|
        #~ with (n - a.sum) {|d|
            #~ if (s.has(d) && !a.has(d)) {
                #~ sol << a
            #~ }
        #~ }
    #~ })

    sol.map {|a| [a..., n - a.sum].sort }.uniq
}

func a(n) {
    for k in (1..Inf) {
        var sol = isok(k, n)
        if (sol.len == n) {
            return [n, k]
        }
        elsif (sol.len > n) {
            say "[#{n}] Found #{sol.len} solutions for k = #{k}..."
        }
    }
}

for k in (2..100) {
    say a(k)
}

__END__
[2, 3]
[3, 44]
[4, 416]