cp's OEIS Frontend

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

%I A071911 #23 May 22 2023 12:39:47
%S A071911 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 A071911 90,94,98,102,105,107,112,117,119,122,126,132,140,146,150,153,155,160,
%U A071911 165,167,170,174,180,188,196,204,210,214,217,219,224,229,231,234,238,244,252
%N A071911 Numbers m such that Stern's diatomic A002487(m) is divisible by 3.
%C A071911 From _Kevin Ryde_, Jan 09 2021: (Start)
%C A071911 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 A071911                  +---+
%C A071911         1 +----> | B | <-----+ 0
%C A071911           |      +---+       |
%C A071911   0 +-- +===+      |       +---+ --+ 1
%C A071911     +-> | A |      |0,1    | D | <-+
%C A071911   start +===+      v       +---+
%C A071911           ^      +---+       ^
%C A071911         1 +----- | C | ------+ 0
%C A071911                  +---+
%C A071911 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 A071911 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 A071911 (End)
%H A071911 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 A071911 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 A071911 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 A071911 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 A071911 (PARI) { my(M=Mod('x, 'x^2+'x+2),
%o A071911             f=[2,1, 0,-'x-1, -2,1, 0,'x-1],
%o A071911             table=[1,3, 5,5, 7,1, 3,7]);
%o A071911 a(n) = n<<=2; my(k=if(n,logint(n,2)+1), p=M^k, s=1);
%o A071911   while(k>=0,
%o A071911     my(t = n + (3<<k) - f[s] - polcoeff(lift(f[s+1]*p),0));
%o A071911     if(bittest(t,k+2), n=t;s++); s=table[s]; p/='x; k--);
%o A071911   n>>2; }  \\ _Kevin Ryde_, Jan 09 2021
%o A071911 (Python)
%o A071911 def aupto(nn):
%o A071911   ok = [1] + [0 for i in range(nn)]
%o A071911   for m in range(nn+1):
%o A071911     if ok[m]:  # from formula
%o A071911       for i in [2*m, 8*m-5, 8*m+5, 8*m-7, 8*m+7]:
%o A071911         if 0 <= i <= nn: ok[i] = 1
%o A071911   return [m for m in range(nn+1) if ok[m]]
%o A071911 print(aupto(252)) # _Michael S. Branicky_, Jan 09 2021
%o A071911 (Python)
%o A071911 from itertools import count, islice
%o A071911 from functools import reduce
%o A071911 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 A071911 def A071911_gen(startvalue=0): # generator of terms >= startvalue
%o A071911     return filter(inA071911, count(max(startvalue,0)))
%o A071911 A071911_list = list(islice(A071911_gen(),20)) # _Chai Wah Wu_, May 18 2023
%Y A071911 Cf. A071412 (diatomic mod 3), A122946 (count by bit length), A089977 (half that).
%K A071911 nonn
%O A071911 0,2
%A A071911 _N. J. A. Sloane_, Jun 13 2002