A354773 - OEIS

%I #37 Nov 29 2023 13:08:09

%S 0,2,0,1,2,3,8,0,1,5,12,2,3,7,16,8,9,0,10,1,4,11,24,12,13,2,14,3,6,15,

%T 32,16,17,8,18,9,19,0,20,10,21,1,22,4,5,11,48,24,25,12,26,13,27,2,28,

%U 14,29,3,30,6,7,15,64,32,33,16,34,17,35,8,36,18,37,9,38,19,39,0,40,20,41,10,42,21,43,1,44,22,45,4,46

%N For terms of A354169 that are the sum of two distinct powers of 2, the exponent of the smaller power of 2.

%H Rémy Sigrist, <a href="/A354773/b354773.txt">Table of n, a(n) for n = 1..10000</a>

%H Michael De Vlieger, Thomas Scheuerle, Rémy Sigrist, N. J. A. Sloane, and Walter Trump, <a href="http://arxiv.org/abs/2209.04108">The Binary Two-Up Sequence</a>, arXiv:2209.04108 [math.CO], Sep 11 2022.

%H Rémy Sigrist, <a href="/A354773/a354773.txt">C++ program</a>

%F Conjecture from _N. J. A. Sloane_, Jun 29 2022: (Start)

%F The following is a conjectured recurrence for a(n). Basically a(n) = a(n/2-1) if n is even, and a(n) = (n+1)/2 if n is odd, except that there are four types of n which have a different formula, and there are 19 exceptional values for small n. Note that a(n) does not depend on earlier values when n is odd.

%F Here is the formula, which agrees with the first 10000 terms.

%F There are exceptional values as far out as n=61, so we take care of them first.

%F Initial conditons:

%F If n is on the list

%F [1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 15, 21, 22, 29, 30, 45, 61]

%F then a(n) is given by the n-th term of the following list:

%F   [0, 2, 0, 1, 2, 3, 8, 0, 1, 5, 12, 2, 3, 7, 16, 8, 9, 0, 10,

%F    1, 4, 11, 24, 12, 13, 2, 14, 3, 6, 15, 32, 16, 17, 8, 18, 9,

%F   19, 0, 20, 10, 21, 1, 22, 4, 5, 11, 48, 24, 25, 12, 26, 13,

%F   27, 2, 28, 14, 29, 3, 30, 6, 7].

%F Otherwise, if n is even, a(n) = a(n/2-1).

%F Otherwise n is odd and is not one of the exceptions.

%F   (I) If n = 3*2^k-3, k >= 5, then a(n) = (n-1)/4.

%F   (II) If n = 2^k-3, k >= 4 then a(n) = (n-1)/4.

%F   (III) If n = 3*2^k-1, k >= 2 then a(n) = n+1.

%F   (IV) If n = 2^k-1, k >= 3 then a(n) = n+1.

%F   (V) Otherwise a(n) = (n+1)/2.

%F (End)

%F The conjecture is now known to be true. See De Vlieger et al. (2022). - _N. J. A. Sloane_, Aug 29 2022

%o (Python)

%o from itertools import count, islice

%o from collections import deque

%o from functools import reduce

%o from operator import or_

%o def A354773_gen(): # generator of terms

%o     aset, aqueue, b, f = {0,1,2}, deque([2]), 2, False

%o     while True:

%o         for k in count(1):

%o             m, j, j2, r, s = 0, 0, 1, b, k

%o             while r > 0:

%o                 r, q = divmod(r,2)

%o                 if not q:

%o                     s, y = divmod(s,2)

%o                     m += y*j2

%o                 j += 1

%o                 j2 *= 2

%o             if s > 0:

%o                 m += s*2**b.bit_length()

%o             if m not in aset:

%o                 if (s := bin(m)[:1:-1]).count('1') == 2:

%o                     yield s.index('1')

%o                 aset.add(m)

%o                 aqueue.append(m)

%o                 if f: aqueue.popleft()

%o                 b = reduce(or_,aqueue)

%o                 f = not f

%o                 break

%o A354773_list = list(islice(A354773_gen(),20)) # _Chai Wah Wu_, Jun 26 2022

%o (C++) See Links section.

%Y Cf. A354169, A354680, A354767, A354798, A354774, A354775.

%K base,nonn

%O 1,2

%A _N. J. A. Sloane_, Jun 26 2022