|
|
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
|
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
|
|
|
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--);
(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]]
(Python)
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)))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|