cp's OEIS Frontend

A376635 a(n+1) = size of the largest subset S of 1...n such that i+j <= n implies a(i+j) = a(i)+a(j) for i and j in S. Start with a(1) = 1.

%I A376635 #26 Nov 01 2024 03:24:23
%S A376635 1,1,1,2,3,3,4,5,4,5,5,6,7,8,9,9,8,9,10,11,12,13,12,12,13,14,15,16,17,
%T A376635 17,16,17,17,17,17,18,19,20,21,22,23,23,22,23,24,24,24,25,25,25,25,26,
%U A376635 26,27,27,28,28,29,29,30,30,31,31,32,32,33,33,34,35,35,36,37,37,37,37,38,38,39,39
%N A376635 a(n+1) = size of the largest subset S of 1...n such that i+j <= n implies a(i+j) = a(i)+a(j) for i and j in S. Start with a(1) = 1.
%H A376635 Robert Israel, <a href="/A376635/b376635.txt">Table of n, a(n) for n = 1..600</a>
%p A376635 f:= proc(n) local V,E,G,i,j; uses GraphTheory;
%p A376635       V:= select(t -> 2*t > n or 2*A[t] = A[2*t], [$1..n]);
%p A376635       E:= select(t -> t[1]+t[2] <= n and A[t[1]]+A[t[2]] <> A[t[1]+t[2]],{seq(seq({V[i],V[j]},i=1..j-1),j=1..nops(V))});
%p A376635       G:= Graph(V,E);
%p A376635       IndependenceNumber(G)
%p A376635 end proc:
%p A376635 A[1]:= 1:
%p A376635 for n from 1 to 99 do A[n+1]:= f(n) od:
%p A376635 seq(A[i],i=1..100); # _Robert Israel_, Oct 31 2024
%o A376635 (Python)
%o A376635 from itertools import combinations, count, islice
%o A376635 def c(n, s, a): # test the condition for subset s
%o A376635     for ii, i in enumerate(s):
%o A376635         for j in s[ii:]:
%o A376635             if i+j <= n:
%o A376635                 if a[i] + a[j] != a[i+j]:
%o A376635                     return False
%o A376635             else:
%o A376635                 break
%o A376635     return True
%o A376635 def agen(): # generator of terms
%o A376635     a, valid = [None, 1], [tuple()]
%o A376635     yield 1
%o A376635     for n in count(1):
%o A376635         new_valid, r = [], 0
%o A376635         for s in valid:
%o A376635             if c(n, s, a):
%o A376635                 new_valid.extend([s, s+(n,)])
%o A376635                 r = max(r, len(s)+1)
%o A376635         valid = new_valid
%o A376635         yield r
%o A376635         a.append(r)
%o A376635 print(list(islice(agen(), 30))) # _Michael S. Branicky_, Oct 01 2024
%K A376635 nonn
%O A376635 1,4
%A A376635 _Bryle Morga_, Sep 30 2024
%E A376635 a(23)-a(58) from _Michael S. Branicky_, Oct 01 2024
%E A376635 More terms from _Robert Israel_, Oct 31 2024