Search: a036987 -id:a036987
|
|
A154402
|
|
Inverse Moebius transform of Fredholm-Rueppel sequence, cf. A036987.
|
|
+20
43
|
|
|
1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 1, 3, 1, 1, 2, 1, 1, 2, 2, 1, 3, 2, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 3, 1, 1, 3, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 3, 1, 2, 4, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 3, 1, 2, 2, 1, 1, 2, 1, 1, 3, 1, 1, 2, 1, 1, 3, 2, 1, 3, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 4
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
Number of ways to write n as a sum a_1 + ... + a_k where the a_i are positive integers and a_i = 2 * a_{i-1}, cf. A000929.
|
|
LINKS
|
|
|
FORMULA
|
G.f.: Sum_{k>0} x^(2^k-1)/(1-x^(2^k-1)).
Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = A065442 = 1.606695... . - Amiram Eldar, Dec 31 2023
|
|
MAPLE
|
N:= 200: # to get a(1)..a(N)
A:= Vector(N):
for k from 1 do
t:= 2^k-1;
if t > N then break fi;
R:= [seq(i, i=t..N, t)];
A[R]:= map(`+`, A[R], 1)
od:
|
|
MATHEMATICA
|
Table[DivisorSum[n, 1 &, IntegerQ@ Log2[# + 1] &], {n, 105}] (* Michael De Vlieger, Jun 11 2018 *)
|
|
PROG
|
(PARI)
A209229(n) = (n && !bitand(n, n-1));
(PARI) A154402(n) = { my(m=1, s=0); while(m<=n, s += !(n%m); m += (m+1)); (s); }; \\ Antti Karttunen, May 12 2022
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
|
|
1, 0, 2, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
Guy Steele defines a family of 36 integer sequences, denoted here by GS(i,j) for 1 <= i, j <= 6, as follows. a[1]=1; a[2n] = i-th term of {0,1,a[n],a[n]+1,2a[n],2a[n]+1}; a[2n+1] = j-th term of {0,1,a[n],a[n]+1,2a[n],2a[n]+1}. The present sequence is GS(1,5).
The full list of 36 sequences:
GS(1,5) = A135416 (the present sequence)
(with a(0)=1): Moebius transform of A038712.
|
|
LINKS
|
|
|
FORMULA
|
G.f.: sum{k>=1, 2^(k-1)*x^(2^k-1) }.
Recurrence: a(2n+1) = 2a(n), a(2n) = 0, starting a(1) = 1.
|
|
MAPLE
|
GS:=proc(i, j, M) local a, n; a:=array(1..2*M+1); a[1]:=1;
for n from 1 to M do
a[2*n] :=[0, 1, a[n], a[n]+1, 2*a[n], 2*a[n]+1][i];
a[2*n+1]:=[0, 1, a[n], a[n]+1, 2*a[n], 2*a[n]+1][j];
od: a:=convert(a, list); RETURN(a); end;
GS(1, 5, 200):
|
|
MATHEMATICA
|
i = 1; j = 5; Clear[a]; a[1] = 1; a[n_?EvenQ] := a[n] = {0, 1, a[n/2], a[n/2]+1, 2*a[n/2], 2*a[n/2]+1}[[i]]; a[n_?OddQ] := a[n] = {0, 1, a[(n-1)/2], a[(n-1)/2]+1, 2*a[(n-1)/2], 2*a[(n-1)/2]+1}[[j]]; Array[a, 105] (* Jean-François Alcover, Sep 12 2013 *)
|
|
PROG
|
(PARI)
A048298(n) = if(!n, 0, if(!bitand(n, n-1), n, 0));
(Python)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
|
|
2, 3, 1, 4, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 8, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
LINKS
|
|
|
FORMULA
|
|
|
MATHEMATICA
|
a[n_] := 1 + IntegerExponent[n, 2] + Sum[(-1)^(n - k - 1)*Binomial[n - 1, k]* Sum[Binomial[k, 2^j - 1], {j, 0, k}], {k, 0, n - 1}]; Table[a[n], {n, 1, 25}] (* G. C. Greubel, Oct 17 2016 *)
|
|
PROG
|
(Python)
def A135560(n): return (m:=(~n & n-1)).bit_length()+int(m==n-1)+1 # Chai Wah Wu, Jul 06 2022
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
|
|
1, 1, 2, 1, 1, 2, 3, 1, 1, 1, 2, 1, 2, 3, 4, 1, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 5, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 6, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
Can be generated recursively by first setting R_1 = (1), after which each R_n is obtained by replacing in R_{n-1} each term k with terms 1 .. k, followed by final n. This sequence is then obtained by concatenating all levels R_1, R_2, ..., R_inf together. See page 230 in Kubo-Vakil paper (page 6 in PDF).
Deleting all 1's and decrementing the remaining terms by one gives the sequence back.
The following simple Pascal-like triangle produces the same sequence. Construct a triangle T(n,k) of strings (with 0 <= k <= n), where T(0,0) = {1}, T(n,n) = {n+1}, and otherwise T(n,k) is the concatenation of T(n-1,k-1) and T(n-1,k). The first few rows of the triangle (where the strings T(n,k) are shown without spaces for legibility) are:
1
1,2
1,12,3
1,112,123,4
1,1112,112123,1234,5
1,11112,1112112123,1121231234,12345,6
...
Now read the strings across the rows to get the sequence. T(n,k) has length binomial(n,k). (End)
|
|
LINKS
|
|
|
FORMULA
|
As a recurrence: If A036987(n) = 1 [when n is of the form 2^k -1], a(n) = A070939(n), else if a(n+1) = 1, a(n) = a(2^A000523(n) - A266349(n)), otherwise a(n) = a(n+1)-1.
Other identities. For all n >= 1:
|
|
EXAMPLE
|
Illustration of the sequence as a tree:
1
/ \
1 2
/ /|\
1 1 2 3_________
/ / /| | \ \ \
1 1 1 2 1 2 3__ 4________
/ / / /| | / \ |\ \ \ \ \ \ \
1 1 1 1 2 1 1 2 1 2 3 1 2 3 4 5
etc.
Compare with the illustration in A265332.
|
|
PROG
|
(Scheme, two variants)
|
|
CROSSREFS
|
Cf. A000225 (positions of records, where n appears first time).
Cf. A266640 (obtained from the mirror image of the same tree).
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
|
|
1, 3, 0, 3, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Row sums of number triangle A127801.
|
|
LINKS
|
|
|
PROG
|
(Python)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
|
|
1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
Right border = A036987, the Fredholm-Rueppel sequence, (1, 1, 0, 1, 0, 0, 0, 1, 0, ...). Row sums = the ruler function, A001511: (1, 2, 1, 3, 1, 2, 1, 4, ...).
|
|
LINKS
|
|
|
FORMULA
|
Inverse Moebius transform of a lower triangular matrix with A036987 (the Fredholm-Rueppel sequence) on the main diagonal and the rest zeros.
|
|
EXAMPLE
|
First few rows of the triangle are:
1;
1, 1;
1, 0, 0;
1, 1, 0, 1;
1, 0, 0, 0, 0;
1, 1, 0, 0, 0, 0;
1, 0, 0, 0, 0, 0, 0;
1, 1, 0, 1, 0, 0, 0, 1;
...
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
|
|
0, 0, 1, 1, 2, 3, 3, 3, 4, 5, 6, 7, 6, 7, 7, 7, 8, 9, 10, 11, 12, 13, 14, 15, 12, 13, 14, 15, 14, 15, 15, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 24, 25, 26, 27, 28, 29, 30, 31, 28, 29, 30, 31, 30, 31, 31, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
Informally: In binary representation of n, move the most significant 1-bit to the position of the most significant 0-bit ("the leftmost free hole"), and remove it altogether if there are no such holes, i.e., if n is one of the terms of A000225. When the subsets of nonnegative integers are associated with the binary expansion of n in the usual way (bit-k is 1 if number k is present in the set, and 0 stands for an empty set) then a(n) corresponds to the set obtained by "squashing" the set which corresponds to n. See Kubo & Vakil paper, page 240, 8.1 Compression revisited.
|
|
LINKS
|
|
|
FORMULA
|
a(0) = 0; after which, for n = 2^k - 1 (when k >= 1) a(n) = 2^(k-1) - 1, otherwise a(n) = n - A053644(n) + 2^(A063250(n)-1).
Other identities. For all n >= 0:
a(n) = A209862(-1+A004001(1+A209861(n))). [Not yet proved that the required permutations are just A209861 & A209862, although this has been checked empirically up to n=32769. See also Kubo & Vakil paper.]
|
|
EXAMPLE
|
For n=13, "1101" in binary, we remove the most significant bit to get "101", where the most significant nonleading 0 is then filled with that 1, to get "111", which is 7's binary representation, thus a(13) = 7.
For n=15, "1111" in binary, we remove the most significant bit to get "111" (= 7), and as there is no most significant nonleading 0 present, the result is just that, and a(15) = 7.
For n=21, "10101" in binary, removing the most significant bit and moving it to the position of next zero results "1101", thus a(21) = 13.
|
|
PROG
|
(Python)
from sympy import catalan
def a063250(n):
if n<2: return 0
b=bin(n)[2:]
s=0
while b.count("0")!=0:
N=int(b[-1] + b[:-1], 2)
s+=1
b=bin(N)[2:]
return s
def a053644(n): return 0 if n==0 else 2**(len(bin(n)[2:]) - 1)
def a036987(n): return catalan(n)%2
def a(n): return n - a053644(n) if a036987(n)==1 else n - a053644(n) + 2**(a063250(n) - 1) # Indranil Ghosh, May 25 2017
(PARI) a(n) = my(s=bitnegimply(n>>1, n)); n - if(n, 1<<logint(n, 2)) + if(s, 1<<logint(s, 2)); \\ Kevin Ryde, Jun 15 2023
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A115367
|
|
Row sums of correlation triangle for Fredholm-Rueppel sequence A036987.
|
|
+20
1
|
|
|
1, 2, 2, 4, 4, 4, 5, 6, 7, 6, 9, 6, 9, 6, 10, 8, 12, 8, 14, 8, 14, 8, 16, 8, 16, 8, 16, 8, 16, 8, 17, 10, 19, 10, 21, 10, 21, 10, 23
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
If a sequence has g.f. A(x), its correlation triangle has g.f. A(x)A(x*y)/(1-x^2*y). (Observation due to Christian G. Bower).
|
|
LINKS
|
|
|
FORMULA
|
G.f. : (sum{k>=0, x^(2k-1)})^2/(1-x^2); a(n)=sum{k=0..n, sum{j=0..k, A036987(j)}*sum{j=0..n-k, A036987(j)*(-1)^(n-k-j)}}.
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A115381
|
|
Correlation triangle for Fredholm-Rueppel sequence A036987.
|
|
+20
0
|
|
|
1, 1, 1, 0, 2, 0, 1, 1, 1, 1, 0, 1, 2, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 3, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 3, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 3, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 3, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
Row sums are A115367. T(2n,n) is partial sums of squares of A036987(n).
|
|
LINKS
|
|
|
FORMULA
|
G.f.: A(x)A(x*y)/(1-x^2*y) where A(x)=sum{k>=0, x^(2^k-1)}. Number triangle T(n, k)=sum{j=0..n, if(j<=k, A036987(k-j), 0)*if(j<=(n-k), A036987(n-k-j), 0)}
|
|
EXAMPLE
|
Triangle begins
1,
1, 1,
0, 2, 0,
1, 1, 1, 1,
0, 1, 2, 1, 0,
0, 1, 1, 1, 1, 0,
0, 0, 1, 3, 1, 0, 0,
1, 0, 1, 1, 1, 1, 0, 1,
0, 1, 0, 1, 3, 1, 0, 1, 0,
0, 1, 0, 1, 1, 1, 1, 0, 1, 0,
0, 0, 1, 1, 1, 3, 1, 1, 1, 0, 0,
0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0,
0, 0, 0, 1, 1, 1, 3, 1, 1, 1, 0, 0, 0,
0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0,
0, 0, 0, 0, 1, 1, 1, 4, 1, 1, 1, 0, 0, 0, 0,
1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1,
0, 1, 0, 0, 0, 1, 1, 1, 4, 1, 1, 1, 0, 0, 0, 1, 0
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A127822
|
|
Triangle whose row sums modulo 2 give the Fredholm-Rueppel sequence A036987.
|
|
+20
0
|
|
|
1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,1
|
|
COMMENTS
|
|
|
LINKS
|
|
|
FORMULA
|
G.f. of k-th column is x^k*if(k=0,1,x*sum{j=0..\infty, x^(-2^(j/2)*(((k+2)/(2*sqrt(2))-(k+1))(-1)^j-(k+2)/(2*sqrt(2))-(k+1))-(k+2))+1+x}
|
|
EXAMPLE
|
Triangle begins
1,
0, 1,
0, 1, 1,
0, 1, 1, 1,
0, 0, 0, 1, 1,
0, 1, 1, 0, 1, 1,
0, 0, 0, 0, 0, 1, 1,
0, 1, 1, 1, 0, 0, 1, 1,
0, 0, 0, 0, 0, 0, 0, 1, 1,
0, 0, 0, 1, 1, 0, 0, 0, 1, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1,
0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
Search completed in 0.077 seconds
|