cp's OEIS Frontend

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

%I A382109 #48 Mar 31 2025 01:59:41
%S A382109 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,
%T A382109 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,
%U A382109 3,1,5,5,1,5,2,1,2,5,1,5,5,1,5,2,1,2,5,1,3,3
%N A382109 a(n) is the index of the first Issai Schur additive sequence that will accept n.
%C A382109 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.
%C A382109 This sequence can be explored by grade 2 students.
%C A382109 Junior high students can be asked what fraction of all numbers have a(n) = 1 (answer 1/3), a(n)=2 (answer 2/9)...
%C A382109 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?
%H A382109 Andrew Howroyd, <a href="/A382109/b382109.txt">Table of n, a(n) for n = 1..10000</a>
%e A382109 Let's consider where the number 15 goes after the first 14 numbers have been placed:
%e A382109 Issai Schur additive sequence #1 {1,2,4,7,10,13}.
%e A382109 Issai Schur additive sequence #2 {3,5,6,12,14}.
%e A382109 Issai Schur additive sequence #3 {8,9,11}.
%e A382109 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
%e A382109 Where does 16 go? It can be added to #1, so a(16) = 1
%e A382109 Where does 17 go? It requires that we start a new additive sequence, #4, so a(17) = 4.
%o A382109 (PARI)
%o A382109 lista(n)={ my(a=vector(n), B=List(), L=List());
%o A382109   for(n=1, n, my(k=1);
%o A382109     while(k<=#L && bittest(L[k],n), k++);
%o A382109     if(k>#L, listput(B,0); listput(L,0));
%o A382109     a[n] = k; L[k] = bitor(L[k], B[k]<<n); B[k] += 1<<n
%o A382109   );
%o A382109   a
%o A382109 } \\ _Andrew Howroyd_, Mar 25 2025
%Y A382109 Cf. A033627 is Issai Schur additive sequence #1.
%K A382109 nonn
%O A382109 1,3
%A A382109 _Gordon Hamilton_, Mar 24 2025
%E A382109 a(45) onwards from _Andrew Howroyd_, Mar 25 2025