[seqfan] Re: From Ali Sada : Another permutation of the positive integers

[M. F. Hasler]

Ali,

Maybe a possible short but sufficiently precise definition could be:

Alternatingly for odd and even numbers, concatenate the smallest yet unused
numbers of that parity until their sum equals the sum of some of the yet
unused numbers of the opposite parity, and also concatenate (the
lexicographically smallest possible choice of) these numbers.

However, I think there's an inconsistency in the example you gave.
The first step is 1+3 = 4
but later you do not allow 5+11 = 16,
you say no even numbers add up to 16, but the number 16 itself is a
solution (sum with 1 term just like 4).
My program gives the following terms a(1..99):
A_upto(99) = [1, 3, 4, 2, 6, 8, 5, 11, 7, 9, 16, 10, 12, 14, 13, 23, 15,
17, 32, 18, 20, 22, 19, 41, 21, 25, 46, 24, 26, 28, 27, 51, 29, 31, 60, 30,
34, 36, 33, 67, 35, 37, 72, 38, 40, 42, 39, 81, 43, 45, 88, 44, 48, 50, 47,
95, 49, 53, 102, 52, 54, 56, 55, 107, 57, 59, 116, 58, 62, 64, 61, 123, 63,
65, 128, 66, 68, 70, 69, 135, 71, 73, 144, 74, 76, 78, 75, 153, 77, 79,
156, 80, 82, 84, 83, 163, 85, 87, 172]

When I wrote it I first produced a variant where "lexicographically" is
replaced by "reverse lexicographically",
i.e., instead of 5+11 as solution for 16, it would produce 7+9  (i.e., it
would choose the smallest possible largest term, recursively
-- that was easier to program, for me at least).

That variant goes:
B_upto(99)
= [1, 3, 4, 2, 6, 8, 7, 9, 5, 11, 16, 10, 12, 14, 17, 19, 13, 15, 28, 18,
20, 22, 29, 31, 21, 23, 44, 24, 26, 30, 39, 41, 25, 27, 52, 32, 34, 36, 49,
53, 33, 35, 68, 38, 40, 42, 59, 61, 37, 43, 80, 46, 48, 50, 71, 73, 45, 47,
92, 54, 56, 58, 83, 85, 51, 55, 106, 60, 62, 57, 65, 63, 67, 64, 66, 70,
72, 74, 107, 109, 69, 75, 144, 76, 78, 82, 117, 119, 77, 79, 156, 84, 86,
81, 89, 87, 91, 88, 90]

Below I give the two programs.

-Maximilian
(PARI)
{A_upto(N, a=1)=local(U=[0]/*used numbers*/, q=[]/*queue*/, ok(s,p, L=oo,
i=U[1])=forstep(k=i+1+(i%2==p),L,2,
setsearch(U,k) || if( k>s, return, k==s || ok(s-k, p, k, i),
return(1))/*if*/)/*for k*/)/*my*/; vector(N,i,
q || (s=0) || forstep( k=U[1]+1+(U[1]%2==a%2),oo,2, !setsearch(U,k) &&
ok(s+=k+!q=concat(q,k), 1-a%2) &&
forstep(m=U[1]+1+(k-U[1])%2,s,2, !setsearch(U,m) && (s==m || ok(s-m, m%2,
oo, m)) && (q=concat(q,m)) && !(s-=m) && break(2)));
a=q[1]; q=q[^1]; if(a > U[1]+1, U=setunion(U, [a]), U[1]=a; while( #U>1 &&
U[2]==U[1]+1, U=U[^1])); a)}

{B_upto(N, a=1)=local(U=[0]/*used numbers*/, q=[]/*queue*/, ok(s,p,L=oo)=
forstep(k=U[1]+1+(U[1]%2==p),L,2,
!setsearch(U,k) && if( k>s, return, k==s || ok(s-k, p, k-2), q=concat(q,k);
return(1))/*if*/)/*for k*/)/*my*/; vector(N,i,
q || (s=0) || forstep( k=U[1]+1+(U[1]%2==a%2),oo,2, !setsearch(U,k) &&
ok(s+=k+!q=concat(q,k), 1-a%2) && break);
a=q[1]; q=q[^1]; if(a > U[1]+1, U=setunion(U, [a]), U[1]=a; while( #U>1 &&
U[2]==U[1]+1, U=U[^1])); a)}

On Sun, Jul 24, 2022, Ali Sada wrote:

> Hi everyone,
>
> We start by putting odd numbers in an ordered list and even numbers in
> another. Terms in each list aim at taking out terms from the other list.
> We start with the smallest number, 1. Since it can’t eliminate even numbers
> on its own, we add the next smallest odd number, 3. Both of them take out
> 4. So, the first three terms of our sequence are 1,3,4.
>
> Now, the smallest number in both lists is 2. On its own, it can’t take out
> any number from the other list, so we add it to the next smallest number on
> the even list, 6, and we get 8. There is no combination of odd numbers at
> this point that adds up to 8, so we add the next smallest even number, 8,
> and we get 16. 16 takes out 5 and 11. We add these five numbers to the
> sequence (in order). The sequence now is 1,3,4,2,6,8,5,11.
>
> The smallest remaining number is 7. We add it to 9 and we get 16. There is
> no combination of the remaining even numbers that adds up to 16, so we
> continue by adding 13 and 15 to get 44, which takes out 10 and 34. The
> sequence now is 1,3,4,2,6,8,5,11,7,9,13,15,10,34.
> And so on.
> The first 45 terms of the sequence are
>
> 1,3,4,2,6,8,5,11,7,9,13,15,10,34,12,14,16,17,25,18,20,22,19,41,21,23,27,29,24,76,26,28,30,31,53,32,36,33,35,37,39,43,45,38,126
>
> If this sequence is fit for the OEIS, I would appreciate any help with the
> definition.
>
>