login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 56th year, we are closing in on 350,000 sequences, and we’ve crossed 9,700 citations (which often say “discovered thanks to the OEIS”).

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A071911 Numbers m such that Stern's diatomic A002487(m) is divisible by 3. 0
0, 5, 7, 10, 14, 20, 28, 33, 35, 40, 45, 47, 49, 51, 56, 61, 63, 66, 70, 73, 75, 80, 85, 87, 90, 94, 98, 102, 105, 107, 112, 117, 119, 122, 126, 132, 140, 146, 150, 153, 155, 160, 165, 167, 170, 174, 180, 188, 196, 204, 210, 214, 217, 219, 224, 229, 231, 234, 238, 244, 252 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

From Kevin Ryde, Jan 09 2021: (Start)

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.

                 +---+

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

          |      +---+       |

  0 +-- +===+      |       +---+ --+ 1

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

  start +===+      v       +---+

          ^      +---+       ^

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

                 +---+

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.

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.

(End)

LINKS

Table of n, a(n) for n=0..60.

Edsger W. Dijkstra, An exercise for Dr. R. M. Burstall, 1976.  Reprinted in Edsger W. Dijkstra, Selected Writings on Computing, Springer-Verlag, 1982, pages 215-216.

Edsger W. Dijkstra, More about the function ``fusc'', 1976.  Reprinted in Edsger W. Dijkstra, Selected Writings on Computing, Springer-Verlag, 1982, pages 230-232.

Bruce Reznick, Regularity Properties of the Stern Enumeration of the Rationals, Journal of Integer Sequences, volume 11, 2008, article 08.4.1.  Also arXiv:math/0610601 [math.NT] 2006, and author's copy.  Section 5 theorem 18 onward.

FORMULA

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

PROG

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

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

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

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

  while(k>=0,

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

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

  n>>2; }  \\ Kevin Ryde, Jan 09 2021

(Python)

def aupto(nn):

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

  for m in range(nn+1):

    if ok[m]:  # from formula

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

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

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

print(aupto(252)) # Michael S. Branicky, Jan 09 2021

CROSSREFS

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

Sequence in context: A156243 A020942 A190035 * A070875 A091522 A020711

Adjacent sequences:  A071908 A071909 A071910 * A071912 A071913 A071914

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, Jun 13 2002

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 7 20:40 EST 2021. Contains 349589 sequences. (Running on oeis4.)