cp's OEIS Frontend

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

%I A025282 #25 Aug 23 2019 17:33:10
%S A025282 1,4,12,51,373,7724,370555,27284157,2075178956
%N A025282 Smallest number requiring n Fibonacci numbers to build using + and *.
%C A025282 The n Fibonacci numbers need not be distinct.  - _Robert Israel_, Jan 25 2015
%C A025282 a(10) > 4427000000. - _Sean A. Irvine_, Aug 23 2019
%H A025282 Sean A. Irvine, <a href="https://github.com/archmageirvine/joeis/blob/master/src/irvine/oeis/a025/A025282.java">Java program</a> (github)
%e A025282 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 A025282 N:= 50000: # to get a(n) where a(n) <= N
%p A025282 P:= Vector(N):
%p A025282 for i from 1 do
%p A025282   f:= combinat:-fibonacci(i);
%p A025282 if f > N then break fi;
%p A025282 P[f]:= 1
%p A025282 od:
%p A025282 A[1]:= 1:
%p A025282 rmax:= 1:
%p A025282 for n from 1 to N do
%p A025282   if P[n] = 0 then
%p A025282      m:= floor(n/2);
%p A025282      r:= min(P[1..m] + P[[seq(n-i, i=1..m)]]);
%p A025282      for a in select(`<=`, numtheory:-divisors(n) minus {1}, floor(sqrt(n))) do
%p A025282         r:= min(r, P[a] + P[n/a])
%p A025282      od:
%p A025282      P[n]:= r;
%p A025282      if r > rmax then
%p A025282        A[r]:= n;
%p A025282        rmax:= r;
%p A025282      fi
%p A025282   fi
%p A025282 od:
%p A025282 seq(A[i], i=1..rmax); # _Robert Israel_, Jan 25 2015
%Y A025282 Cf. A000045, A254122, A254123.
%K A025282 nonn,more
%O A025282 1,2
%A A025282 _David W. Wilson_
%E A025282 a(7)-a(9) from _Sean A. Irvine_, Aug 23 2019