login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 2
1, 3, 7, 14, 26, 39, 67, 122, 180, 347, 524, 884, 1700, 2564, 4893, 8826, 15593, 28348, 50527, 73536, 136858, 251537, 388362, 662078, 1038501, 1952109, 2983020, 5533878, 8515097, 16211471, 29346362, 45472332, 74818528, 134329628, 251629409, 385580882 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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

LINKS

Rémy Sigrist, Table of n, a(n) for n = 1..41

Rémy Sigrist, C++ program for A343017

Matthew R. Maas, Proof of upper bound on growth rate of a

EXAMPLE

For a(7):

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.

MAPLE

b:= proc(n, i) option remember; n=0 or i>1 and

      b(n, i-1) or i>0 and a(i)<=n and b(n-a(i), i-1)

    end:

a:= proc(n) option remember; local i, j, k; if n=1 then k:= 1

      else k:= a(n-1); for i to n do for j from k+1 while

        b(j, n-1) do od; k:= j od fi; k

    end:

seq(a(n), n=1..20);  # Alois P. Heinz, Apr 02 2021

MATHEMATICA

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

PROG

(Java)

// Running set of all possible numbers

// that can be written as a sum of distinct

// terms in the sequence so far. The set

// starts with one element, 0, for the empty

// sum.

HashSet<Integer> set = new HashSet<>();

set.add(0);

int last = 0;

int nextCount = 1;

while (true) {

    int j = nextCount;

    int position = last;

    while(true) {

        ++position;

        if (set.contains(position)) {

            continue;

        }

        --j;

        if (j == 0) {

            // Output the next term of the sequence.

            System.out.println(position);

            last = position;

            // Add to the running set of possible sums

            // any new sums now possible because of the

            // term just added.

            HashSet<Integer> setCopy = new HashSet<>(set);

            for (Integer val : setCopy) {

                set.add(Math.addExact(position, val));

            }

            break;

        }

    }

    ++nextCount;

}

(C++) See Links section.

CROSSREFS

Cf. A049864. Formula for A049864 was used in calculation of growth rate upper bound. - Matthew R. Maas, Apr 21 2021

Sequence in context: A193911 A206417 A207381 * A008646 A036830 A014153

Adjacent sequences:  A343014 A343015 A343016 * A343018 A343019 A343020

KEYWORD

nonn

AUTHOR

Matthew R. Maas, Apr 02 2021

EXTENSIONS

a(25)-a(27) from Alois P. Heinz, Apr 02 2021

a(28)-a(30) from Jinyuan Wang, Apr 02 2021

More terms from Rémy Sigrist, Apr 04 2021

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 2 09:22 EDT 2021. Contains 346422 sequences. (Running on oeis4.)