cp's OEIS Frontend

A138858 a(n) = least square such that the subsets of {a(1),...,a(n)} sum to 2^n different values.

%I A138858 #15 Apr 07 2025 14:04:42
%S A138858 1,4,9,16,36,81,144,324,625,1156,2401,4900,9801,19600,39204,78400,
%T A138858 156816,313600,627264,1254400,2509056,5022081,10042561,20088324,
%U A138858 40182921,80371225,160731684,321484900,642977449,1285939600,2571909796,5143901841,10287842041,20575607364,41151368164,82303003225,164606284089,329212012900,658425136356,1316850346681,2633700545424,5267401386724
%N A138858 a(n) = least square such that the subsets of {a(1),...,a(n)} sum to 2^n different values.
%C A138858 Asking for 2^n different values implies that a(n) differs from all a(k), k<n and in view of the minimality condition, also that a(n) > a(n-1) for n>1.
%C A138858 Note that a(n) is close to, but not always larger than sum(a(k),k=1..n-1), as opposed to the case in A064934.
%C A138858 From _Martin Fuller_, Apr 07 2025: (Start)
%C A138858 a(n) is also the least square which is not in {sum(A)-sum(B) : A,B subsets of {a(1)..a(n-1)}}.
%C A138858 It is much more efficient to work with the complement s(n-1) = {0..sum(a(k),k=1..n-1)} \ {sum(A)-sum(B) : A,B subsets of {a(1)..a(n-1)}}. s(n) can be calculated iteratively and has no more than 7 elements below n=10^6.
%C A138858 Then a(n) is the least square in s(n-1), if any, or else the least square greater than sum(a(k),k=1..n-1).
%C A138858 a(7) and a(10) are the only cases where a(n) < sum(a(k),k=1..n-1) up to n=10^6. (End)
%H A138858 Martin Fuller, <a href="/A138858/b138858.txt">Table of n, a(n) for n = 1..1000</a>
%H A138858 Martin Fuller, <a href="/A138858/a138858.gp.txt">PARI program</a>
%e A138858 Up to a(4)=16, we have a(n)=n^2.
%e A138858 But since 5^2=25=9+16 is already represented as sum of earlier terms, this is excluded, while a(5)=6^2=36 has the required property.
%e A138858 Obviously, any square larger to the sum of all preceding terms leads to enough new terms, thus a(n) <= floor( sqrt( sum(a(k),k=1..n-1))+1)^2.
%e A138858 But in contrast to A064934, such a simple formula (with equality) cannot be used here:
%e A138858 a(7)=12^2=144 < 147=sum(a(k),k<7) and also a(10)=sum(a(k),k<10)-84.
%o A138858 (PARI) {s=1;p=0; for( n=1,20, until( !bitand( s, s>>(p^2) ), p++); s+=s<<(p^2); print1( p^2,","))}
%Y A138858 Cf. A138857 (=sqrt(a(n))), A138000-138001, A064934.
%K A138858 nonn
%O A138858 1,2
%A A138858 _M. F. Hasler_, Apr 09 2008
%E A138858 a(24)-a(30) from _Donovan Johnson_, Oct 03 2009
%E A138858 a(31) onwards from _Martin Fuller_, Apr 07 2025