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

1, 4, 9, 16, 36, 81, 144, 324, 625, 1156, 2401, 4900, 9801, 19600, 39204, 78400, 156816, 313600, 627264, 1254400, 2509056, 5022081, 10042561, 20088324, 40182921, 80371225, 160731684, 321484900, 642977449, 1285939600, 2571909796, 5143901841, 10287842041, 20575607364, 41151368164, 82303003225, 164606284089, 329212012900, 658425136356, 1316850346681, 2633700545424, 5267401386724

Offset: 1

Author

M. F. Hasler, Apr 09 2008

Keywords

• nonn

Comments

Asking for 2^n different values implies that a(n) differs from all a(k), k a(n-1) for n>1.

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.

From Martin Fuller, Apr 07 2025: (Start)

a(n) is also the least square which is not in {sum(A)-sum(B) : A,B subsets of {a(1)..a(n-1)}}.

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.

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).

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)

Examples

			Up to a(4)=16, we have a(n)=n^2.
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.
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.
But in contrast to A064934, such a simple formula (with equality) cannot be used here:
a(7)=12^2=144 < 147=sum(a(k),k<7) and also a(10)=sum(a(k),k<10)-84.
		

Links

• Martin Fuller, Table of n, a(n) for n = 1..1000
• Martin Fuller, PARI program

Crossrefs

Cf. A138857 (=sqrt(a(n))), A138000-138001, A064934.

Programs

PARI

{s=1;p=0; for( n=1,20, until( !bitand( s, s>>(p^2) ), p++); s+=s<<(p^2); print1( p^2,","))}

Extensions

a(24)-a(30) from Donovan Johnson, Oct 03 2009

a(31) onwards from Martin Fuller, Apr 07 2025