A384870 The largest k such that the set {1^n, 2^n, ..., k^n} has uniquely distinct subset sums.

1, 2, 4, 5, 8, 11, 15, 19, 21, 28, 30, 37, 42, 45, 45

Offset: 0

Author

Yuto Tsujino, Jun 11 2025

Keywords

• nonn
• hard
• more

Comments

a(15) >= 49. - David A. Corneth, Jun 16 2025

Examples

			For n=2, the set {1^2, 2^2, 3^2, 4^2} = {1, 4, 9, 16} has uniquely distinct subset sums.
However, adding 5^2 = 25 introduces a duplicate sum: 9 + 16 = 25.
Thus, the largest k that satisfies the subset sum uniqueness condition is 4, meaning a(2)=4.
		

Links

• David A. Corneth, PARI program

Crossrefs

Cf. A000124, A208531, A332101.

Programs

Maple

A := proc(n)
    local k, S, T, subsetsum;
    k := 1;
    while true do
        S := {seq(i^n, i=1..k)};
        T := combinat[powerset](S);
        subsetsum := map(x -> add(x), T);
        if numelems(subsetsum) = numelems(T) then
            k := k + 1;
        else
            return k - 1;
        end if;
    end do;
end proc;

Mathematica

A[n_] := Module[{k = 1, S, subsetSums},
  While[True,
    S = Table[i^n, {i, 1, k}];
    subsetSums = Total /@ Subsets[S];
    If[Length[subsetSums] == Length[DeleteDuplicates[subsetSums]], k++, Return[k - 1]];
  ]
]

PARI

isok(k,n) = my(list=List()); forsubset(k, s, listput(list, sum(i=1, #s, s[i]^n));); if (#Set(list) != #list, return(0)); 1;
a(n) = for (k=1, oo, if (!isok(k,n), return(k-1));); \\ Michel Marcus, Jun 14 2025

PARI

\\ See Corneth link

Python

def a(n):
    k = 1
    while True:
        powers = [(i + 1) ** n for i in range(k)]
        subset_sums = set()
        all_unique = True
        for mask in range(1 << k):
            total = sum(powers[i] for i in range(k) if mask & (1 << i))
            if total in subset_sums:
                all_unique = False
                break
            subset_sums.add(total)
        if not all_unique:
            return k - 1
        k += 1
print([a(n) for n in range(9)])

Python

from itertools import chain, combinations, count
def powerset(s):
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
def a(n):
    s, sums = {1}, {1}
    for k in count(2):
        t = k**n
        newsums = set(sum(ss)+t for ss in powerset(s))
        if newsums & sums:
            return k-1
        s, sums = s|{t}, s|newsums
print([a(n) for n in range(9)]) # Michael S. Branicky, Jun 14 2025

Formula

1/(2^(1/n)-1) + 1 <= a(n) <= e^(-LambertW(-1, -log(2)/(n+1))). - Yifan Xie, Jun 16 2025

Extensions

a(9)-a(10) from Michael S. Branicky, Jun 13 2025

a(11) from Jinyuan Wang, Jun 14 2025

a(12)-a(14) from David A. Corneth, Jun 16 2025