A025282 - OEIS

%I #25 Aug 23 2019 17:33:10

%S 1,4,12,51,373,7724,370555,27284157,2075178956

%N Smallest number requiring n Fibonacci numbers to build using + and *.

%C The n Fibonacci numbers need not be distinct.  - _Robert Israel_, Jan 25 2015

%C a(10) > 4427000000. - _Sean A. Irvine_, Aug 23 2019

%H Sean A. Irvine, <a href="https://github.com/archmageirvine/joeis/blob/master/src/irvine/oeis/a025/A025282.java">Java program</a> (github)

%e a(12) = 1 + 3 + 8 but can't be represented using fewer than 3 Fibonacci numbers, and is the least number with this property. - _Robert Israel_, Jan 25 2015

%p N:= 50000: # to get a(n) where a(n) <= N

%p P:= Vector(N):

%p for i from 1 do

%p   f:= combinat:-fibonacci(i);

%p if f > N then break fi;

%p P[f]:= 1

%p od:

%p A[1]:= 1:

%p rmax:= 1:

%p for n from 1 to N do

%p   if P[n] = 0 then

%p      m:= floor(n/2);

%p      r:= min(P[1..m] + P[[seq(n-i, i=1..m)]]);

%p      for a in select(`<=`, numtheory:-divisors(n) minus {1}, floor(sqrt(n))) do

%p         r:= min(r, P[a] + P[n/a])

%p      od:

%p      P[n]:= r;

%p      if r > rmax then

%p        A[r]:= n;

%p        rmax:= r;

%p      fi

%p   fi

%p od:

%p seq(A[i], i=1..rmax); # _Robert Israel_, Jan 25 2015

%Y Cf. A000045, A254122, A254123.

%K nonn,more

%O 1,2

%A _David W. Wilson_

%E a(7)-a(9) from _Sean A. Irvine_, Aug 23 2019