A122946 -id:A122946 - cp's OEIS frontend

A122941 Rectangular table, read by antidiagonals, where the g.f. of row n is Sum_{i>=0} F_i(x)^n / 2^(i+1), where F_0(x)=x, F_{n+1}(x) = F_n(x+x^2), for n>=1.

1, 1, 1, 1, 2, 2, 1, 3, 7, 7, 1, 4, 15, 34, 34, 1, 5, 26, 94, 214, 214, 1, 6, 40, 200, 726, 1652, 1652, 1, 7, 57, 365, 1831, 6645, 15121, 15121, 1, 8, 77, 602, 3865, 19388, 70361, 160110, 160110, 1, 9, 100, 924, 7239, 46481, 233154, 846144, 1925442, 1925442, 1

Offset: 1

Paul D. Hanna, Sep 25 2006

A122940(n)/n = Sum_{m=1..n} (-1)^(m-1)*T(m,n-m+1)/m ; where l.g.f. of A122940, L(x), satisfies: L(x+x^2) = 2*L(x) - log(1+x).

			Table begins:
1, 1, 2, 7, 34, 214, 1652, 15121, 160110, 1925442, 25924260, ...;
1, 2, 7, 34, 214, 1652, 15121, 160110, 1925442, 25924260, ...;
1, 3, 15, 94, 726, 6645, 70361, 846144, 11392530, 169785124, ...;
1, 4, 26, 200, 1831, 19388, 233154, 3139200, 46784118, ...;
1, 5, 40, 365, 3865, 46481, 625820, 9326720, 152426170, ...;
1, 6, 57, 602, 7239, 97470, 1452610, 23739936, 422171622, ...;
1, 7, 77, 924, 12439, 185388, 3029782, 53879148, 1035760670, ...;
1, 8, 100, 1344, 20026, 327296, 5820360, 111889248, 2312153223, ...;
1, 9, 126, 1875, 30636, 544824, 10473576, 216432783, 4784414985, ...;
1, 10, 155, 2530, 44980, 864712, 17868995, 395007850, 9301284465, ...;
Given that A122940 begins:
[1, 1, 4, 17, 106, 796, 7176, 75057, 894100, 11946906, ...],
demonstrate A122940(n)/n = Sum_{m=1..n} (-1)^(m-1)*T(m,n-m+1)/m
at n=4: A122940(4)/4 = 17/4 = 7/1 - 7/2 + 3/3 - 1/4;
at n=5: A122940(5)/5 = 106/5 = 34/1 - 34/2 + 15/3 - 4/4 + 1/5;
at n=6: A122940(6)/6 = 796/6 = 214/1 - 214/2 + 94/3 - 26/4 + 5/5 - 1/6.

Cf. A122940; rows: A122942, A122943, A122944, A122945; related tables: A122888, A122946, A122948, A122951.

/* Get T(n,k) from H(n,), the n-th self-composition of x+x^2: */
{H(n,p)=local(F=x+x^2, G=x+x*O(x^p));if(n==0,G=x,for(i=1,n,G=subst(F,x,G));G)}
{T(n,k)=round(polcoeff( sum(i=0,6*n+100,H(i,k+n-1)^n/2^(i+1)),k+n-1))}

T(n,k) = [x^k] Sum_{i>=0} F_i(x)^n / 2^(i+1) where F_0(x)=x, F_{n+1}(x) = F_n(x+x^2); a sum involving n-th powers of self-compositions of x+x^2 (cf. A122888).

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

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane, Jun 13 2002

nonn

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)

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.

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

{ 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<>2; }  \\ Kevin Ryde, Jan 09 2021

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

from itertools import count, islice
from functools import reduce
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)
def A071911_gen(startvalue=0): # generator of terms >= startvalue
    return filter(inA071911, count(max(startvalue,0)))
A071911_list = list(islice(A071911_gen(),20)) # Chai Wah Wu, May 18 2023

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

cp's OEIS Frontend

A122941 Rectangular table, read by antidiagonals, where the g.f. of row n is Sum_{i>=0} F_i(x)^n / 2^(i+1), where F_0(x)=x, F_{n+1}(x) = F_n(x+x^2), for n>=1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula