A071911 - OEIS

A071911

Numbers m such that Stern's diatomic A002487(m) is divisible by 3.

%I #23 May 22 2023 12:39:47

%S 0,5,7,10,14,20,28,33,35,40,45,47,49,51,56,61,63,66,70,73,75,80,85,87,

%T 90,94,98,102,105,107,112,117,119,122,126,132,140,146,150,153,155,160,

%U 165,167,170,174,180,188,196,204,210,214,217,219,224,229,231,234,238,244,252

%N Numbers m such that Stern's diatomic A002487(m) is divisible by 3.

%C From _Kevin Ryde_, Jan 09 2021: (Start)

%C Dijkstra gives bit pattern {0}1{?0{1}0|?1{0}1}?1{0} for the terms of this sequence, where | is alternative, {x} is zero or more of x, and ? is a single 0 or 1. Dijkstra formed this from a finite state automaton (states as pairs of Stern diatomic values mod 3 = A071412). The minimized automaton is as follows. State A is the start and the sole accepting state.

%C +---+

%C 1 +----> | B | <-----+ 0

%C | +---+ |

%C 0 +-- +===+ | +---+ --+ 1

%C +-> | A | |0,1 | D | <-+

%C start +===+ v +---+

%C ^ +---+ ^

%C 1 +----- | C | ------+ 0

%C +---+

%C a(n) can be calculated from n by a usual unranking in this automaton, using the number of strings of a given length k accepted from each state. Reznick's A122946(k) is the number of strings accepted starting from B. A089977(k-1) is the number accepted starting from C.

%C Dijkstra shows that for any m, a bit reversal (A030101) or an internal bit complement (A122155) of m are no change to the resulting Diatomic(m) value. So here if m is a term then so are A030101(m) and A122155(m). In the bit pattern, a reversal or complement between (but not including) the outermost 1's is no change.

%C (End)

%H Edsger W. Dijkstra, <a href="http://www.cs.utexas.edu/users/EWD/ewd05xx/EWD570.PDF">An exercise for Dr. R. M. Burstall</a>, 1976. Reprinted in Edsger W. Dijkstra, <a href="https://doi.org/10.1007/978-1-4612-5695-3_36">Selected Writings on Computing</a>, Springer-Verlag, 1982, pages 215-216.

%H Edsger W. Dijkstra, <a href="http://www.cs.utexas.edu/users/EWD/ewd05xx/EWD578.PDF">More about the function ``fusc''</a>, 1976. Reprinted in Edsger W. Dijkstra, <a href="https://doi.org/10.1007/978-1-4612-5695-3_41">Selected Writings on Computing</a>, Springer-Verlag, 1982, pages 230-232.

%H Bruce Reznick, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL11/Reznick/reznick4.html">Regularity Properties of the Stern Enumeration of the Rationals</a>, Journal of Integer Sequences, volume 11, 2008, article 08.4.1. Also <a href="https://arxiv.org/abs/math/0610601">arXiv:math/0610601</a> [math.NT] 2006, and <a href="https://faculty.math.illinois.edu/~reznick/reznick4.pdf">author's copy</a>. Section 5 theorem 18 onward.

%F If m is in the sequence, then 2*m, 8*m +- 5, and 8*m +- 7 (when nonnegative) are in the sequence. Starting from m=0, this rule generates the sequence. [Reznick section 5 theorem 18] - _Kevin Ryde_, Jan 09 2021

%o (PARI) { my(M=Mod('x, 'x^2+'x+2),

%o f=[2,1, 0,-'x-1, -2,1, 0,'x-1],

%o table=[1,3, 5,5, 7,1, 3,7]);

%o a(n) = n<<=2; my(k=if(n,logint(n,2)+1), p=M^k, s=1);

%o while(k>=0,

%o my(t = n + (3<<k) - f[s] - polcoeff(lift(f[s+1]*p),0));

%o if(bittest(t,k+2), n=t;s++); s=table[s]; p/='x; k--);

%o n>>2; } \\ _Kevin Ryde_, Jan 09 2021

%o (Python)

%o def aupto(nn):

%o ok = [1] + [0 for i in range(nn)]

%o for m in range(nn+1):

%o if ok[m]: # from formula

%o for i in [2*m, 8*m-5, 8*m+5, 8*m-7, 8*m+7]:

%o if 0 <= i <= nn: ok[i] = 1

%o return [m for m in range(nn+1) if ok[m]]

%o print(aupto(252)) # _Michael S. Branicky_, Jan 09 2021

%o (Python)

%o from itertools import count, islice

%o from functools import reduce

%o def inA071911(n): return not (n and sum(reduce(lambda x,y:(x[0],(x[0]+x[1])%3) if int(y) else ((x[0]+x[1])%3,x[1]),bin(n)[-1:2:-1],(1,0)))%3)

%o def A071911_gen(startvalue=0): # generator of terms >= startvalue

%o return filter(inA071911, count(max(startvalue,0)))

%o A071911_list = list(islice(A071911_gen(),20)) # _Chai Wah Wu_, May 18 2023

%Y Cf. A071412 (diatomic mod 3), A122946 (count by bit length), A089977 (half that).

%K nonn

%O 0,2

%A _N. J. A. Sloane_, Jun 13 2002