A382109 a(n) is the index of the first Issai Schur additive sequence that will accept n.

1, 1, 2, 1, 2, 2, 1, 3, 3, 1, 3, 2, 1, 2, 3, 1, 4, 3, 1, 4, 2, 1, 2, 4, 1, 4, 4, 1, 4, 2, 1, 2, 4, 1, 3, 3, 1, 3, 2, 1, 2, 3, 1, 5, 4, 1, 5, 2, 1, 2, 5, 1, 5, 4, 1, 5, 2, 1, 2, 5, 1, 3, 3, 1, 3, 2, 1, 2, 3, 1, 5, 5, 1, 5, 2, 1, 2, 5, 1, 5, 5, 1, 5, 2, 1, 2, 5, 1, 3, 3

Offset: 1

Author

Gordon Hamilton, Mar 24 2025

Keywords

• nonn

Comments

The Issai Schur additive sequences are greedily constructed so that no term in a sequence is the sum of two earlier terms in that sequence. Each positive integer is placed into exactly one additive sequence with priority given to the first sequence that will accept it.

This sequence can be explored by grade 2 students.

Junior high students can be asked what fraction of all numbers have a(n) = 1 (answer 1/3), a(n)=2 (answer 2/9)...

How does this greedy algorithm compare to the best possible results where we are trying to push the first occurrence of a(n) = k to happen for the largest possible n?

Examples

			Let's consider where the number 15 goes after the first 14 numbers have been placed:
Issai Schur additive sequence #1 {1,2,4,7,10,13}.
Issai Schur additive sequence #2 {3,5,6,12,14}.
Issai Schur additive sequence #3 {8,9,11}.
We always try to greedily add the next number in the lowest indexed sequence possible. "15" cannot go in #1 because 2+13 = 15. It cannot go in #2 because 3+12 = 15. It goes into #3 because no two distinct numbers in that additive sequence add to 15. So a(15) = 3
Where does 16 go? It can be added to #1, so a(16) = 1
Where does 17 go? It requires that we start a new additive sequence, #4, so a(17) = 4.
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A033627 is Issai Schur additive sequence #1.

Programs

PARI

lista(n)={ my(a=vector(n), B=List(), L=List());
  for(n=1, n, my(k=1);
    while(k<=#L && bittest(L[k],n), k++);
    if(k>#L, listput(B,0); listput(L,0));
    a[n] = k; L[k] = bitor(L[k], B[k]<Andrew Howroyd, Mar 25 2025

Extensions

a(45) onwards from Andrew Howroyd, Mar 25 2025