cp's OEIS Frontend

A343017 a(1)=1. For n > 1, a(n) is the n-th positive integer after a(n-1) which cannot be written as a sum of distinct preceding terms in the sequence.

%I A343017 #45 Apr 26 2021 02:44:17
%S A343017 1,3,7,14,26,39,67,122,180,347,524,884,1700,2564,4893,8826,15593,
%T A343017 28348,50527,73536,136858,251537,388362,662078,1038501,1952109,
%U A343017 2983020,5533878,8515097,16211471,29346362,45472332,74818528,134329628,251629409,385580882
%N A343017 a(1)=1. For n > 1, a(n) is the n-th positive integer after a(n-1) which cannot be written as a sum of distinct preceding terms in the sequence.
%C A343017 Theorem: for n >= 6, a(n) < (Sum_{i=1..n-1} a(i)) - a(n-3). Corollary: a(n) = O(x^n) where x is the positive real solution to x^4 - 2x^3 + x - 1 = 0, exact value (1 + sqrt(3 + 2*sqrt(5)))/2 = 1.86676.... I conjecture that this bound can be tightened further. - _Matthew R. Maas_, Apr 21 2021
%H A343017 Rémy Sigrist, <a href="/A343017/b343017.txt">Table of n, a(n) for n = 1..41</a>
%H A343017 Rémy Sigrist, <a href="/A343017/a343017.txt">C++ program for A343017</a>
%H A343017 Matthew R. Maas, <a href="/A343017/a343017_3.txt">Proof of upper bound on growth rate of a</a>
%e A343017 For a(7):
%e A343017 The first six terms of the sequence are 1, 3, 7, 14, 26, and 39, and the set of all distinct sums of subsets of this set of six numbers is {0 (the empty sum), 1, 3, 4, 7, 8, 10, 11, 14, 15, 17, 18, 21, 22, 24, 25, 26, 27, 29, 30, 33, 34, 36, 37, 39, 40, 41, 42, 43, 44, 46, 47, 48, 49, 50, 51, 53, 54, 56, 57, 60, 61, 63, 64, 65, 66, 68, 69, 72, 73, 75, 76, 79, 80, 82, 83, 86, 87, 89, 90}. The numbers after 39 which are NOT in this set are {45, 52, 55, 58, 59, 62, 67, ...}. The 7th such number is 67, so a(7)=67.
%p A343017 b:= proc(n, i) option remember; n=0 or i>1 and
%p A343017       b(n, i-1) or i>0 and a(i)<=n and b(n-a(i), i-1)
%p A343017     end:
%p A343017 a:= proc(n) option remember; local i, j, k; if n=1 then k:= 1
%p A343017       else k:= a(n-1); for i to n do for j from k+1 while
%p A343017         b(j, n-1) do od; k:= j od fi; k
%p A343017     end:
%p A343017 seq(a(n), n=1..20);  # _Alois P. Heinz_, Apr 02 2021
%t A343017 a[1]=1;a[n_]:=a[n]=Select[Complement[Range[n+Max[l=Union[Total/@Subsets[s=Array[a,n-1]]]]],l],#>Last@s&][[n]];Array[a,20] (* _Giorgos Kalogeropoulos_, Apr 21 2021 *)
%o A343017 (Java)
%o A343017 // Running set of all possible numbers
%o A343017 // that can be written as a sum of distinct
%o A343017 // terms in the sequence so far. The set
%o A343017 // starts with one element, 0, for the empty
%o A343017 // sum.
%o A343017 HashSet<Integer> set = new HashSet<>();
%o A343017 set.add(0);
%o A343017 int last = 0;
%o A343017 int nextCount = 1;
%o A343017 while (true) {
%o A343017     int j = nextCount;
%o A343017     int position = last;
%o A343017     while(true) {
%o A343017         ++position;
%o A343017         if (set.contains(position)) {
%o A343017             continue;
%o A343017         }
%o A343017         --j;
%o A343017         if (j == 0) {
%o A343017             // Output the next term of the sequence.
%o A343017             System.out.println(position);
%o A343017             last = position;
%o A343017             // Add to the running set of possible sums
%o A343017             // any new sums now possible because of the
%o A343017             // term just added.
%o A343017             HashSet<Integer> setCopy = new HashSet<>(set);
%o A343017             for (Integer val : setCopy) {
%o A343017                 set.add(Math.addExact(position, val));
%o A343017             }
%o A343017             break;
%o A343017         }
%o A343017     }
%o A343017     ++nextCount;
%o A343017 }
%o A343017 (C++) See Links section.
%Y A343017 Cf. A049864. Formula for A049864 was used in calculation of growth rate upper bound. - _Matthew R. Maas_, Apr 21 2021
%K A343017 nonn
%O A343017 1,2
%A A343017 _Matthew R. Maas_, Apr 02 2021
%E A343017 a(25)-a(27) from _Alois P. Heinz_, Apr 02 2021
%E A343017 a(28)-a(30) from _Jinyuan Wang_, Apr 02 2021
%E A343017 More terms from _Rémy Sigrist_, Apr 04 2021