A036987 -id:A036987 - cp's OEIS frontend

A154402 Inverse Moebius transform of Fredholm-Rueppel sequence, cf. A036987.

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

Offset: 1

Vladeta Jovovic, Jan 08 2009

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.

Number of divisors of n of the form 2^k - 1 (A000225) for k >= 1. - Jeffrey Shallit, Jan 23 2017

Antti Karttunen, Table of n, a(n) for n = 1..65537 (first 10000 terms from Robert Israel)

Cf. A000225, A000929, A001511, A036987, A065442, A147645, A161790 (positions of 1's), A305426, A353786.

Cf. also A305436.

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:
convert(A,list); # Robert Israel, Jan 23 2017

Table[DivisorSum[n, 1 &, IntegerQ@ Log2[# + 1] &], {n, 105}] (* Michael De Vlieger, Jun 11 2018 *)

A209229(n) = (n && !bitand(n,n-1));
A036987(n) = A209229(1+n);
A154402(n) = sumdiv(n,d,A036987(d)); \\ Antti Karttunen, Jun 11 2018

A154402(n) = { my(m=1,s=0); while(m<=n, s += !(n%m); m += (m+1)); (s); }; \\ Antti Karttunen, May 12 2022

G.f.: Sum_{k>0} x^(2^k-1)/(1-x^(2^k-1)).
From Antti Karttunen, Jun 11 2018: (Start)
a(n) = Sum_{d|n} A036987(d).
a(n) = A305426(n) + A036987(n). (End)
a(n) = A147645(n) + A353786(n). - Antti Karttunen, May 12 2022
Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = A065442 = 1.606695... . - Amiram Eldar, Dec 31 2023

A135416 a(n) = A036987(n)*(n+1)/2.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane, based on a message from Guy Steele and Don Knuth, Mar 01 2008

nonn

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,1) = A000007
GS(1,2) = A000035
GS(1,3) = A036987
GS(1,4) = A007814
GS(1,5) = A135416 (the present sequence)
GS(1,6) = A135481
GS(2,1) = A135528
GS(2,2) = A000012
GS(2,3) = A000012
GS(2,4) = A091090
GS(2,5) = A135517
GS(2,6) = A135521
GS(3,1) = A036987
GS(3,2) = A000012
GS(3,3) = A000012
GS(3,4) = A000120
GS(3,5) = A048896
GS(3,6) = A038573
GS(4,1) = A135523
GS(4,2) = A001511
GS(4,3) = A008687
GS(4,4) = A070939
GS(4,5) = A135529
GS(4,6) = A135533
GS(5,1) = A048298
GS(5,2) = A006519
GS(5,3) = A080100
GS(5,4) = A087808
GS(5,5) = A053644
GS(5,6) = A000027
GS(6,1) = A135534
GS(6,2) = A038712
GS(6,3) = A135540
GS(6,4) = A135542
GS(6,5) = A054429
GS(6,6) = A003817
(with a(0)=1): Moebius transform of A038712.

Antti Karttunen, Table of n, a(n) for n = 1..65537
Index entries for sequences related to binary expansion of n

Equals A048298(n+1)/2. Cf. A036987, A182660.

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):

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 *)

A048298(n) = if(!n,0,if(!bitand(n,n-1),n,0));
A135416(n) = (A048298(n+1)/2); \\ Antti Karttunen, Jul 22 2018

def A135416(n): return int(not(n&(n+1)))*(n+1)>>1 # Chai Wah Wu, Jul 06 2022

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.

Formulae and comments by Ralf Stephan, Jun 20 2014

A135560 a(n) = A007814(n) + A036987(n-1) + 1.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane, Mar 01 2008

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A007814, A036987, A091090, A135534, A135561.

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 *)

a(n)=my(t=valuation(n, 2)); t + (n==2^t) + 1 \\ Charles R Greathouse IV, Oct 17 2016

def A135560(n): return (m:=(~n & n-1)).bit_length()+int(m==n-1)+1 # Chai Wah Wu, Jul 06 2022

a(2^k) = k+2; a(2^k + 2^(k-1)) = k. - Reinhard Zumkeller, Mar 02 2008

More terms from Reinhard Zumkeller, Mar 02 2008

A265754 Reduced frequency counts for A004001: a(n) = A265332(n+1) - A036987(n).

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Jan 10 2016

nonn

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.
Comment from N. J. A. Sloane, Nov 05 2017: (Start)
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)

			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.

Antti Karttunen, Table of n, a(n) for n = 1..8191
T. Kubo and R. Vakil, On Conway's recursive sequence, Discr. Math. 152 (1996), 225-252.

Cf. A004001, A036987, A054429, A070939, A265332, A266348, A266349.
Cf. A000225 (positions of records, where n appears first time).
Cf. A266640 (obtained from the mirror image of the same tree).
See A293959 for another version.

a(n) = A265332(n+1) - A036987(n).
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:
a(n) = A266640(A054429(n)).
a(A000225(n)) = n.

A127802 a(0) = 1, a(n) = 3*A036987(n), n>1.

Original entry on oeis.org

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

Offset: 0

Paul Barry, Jan 29 2007

nonn

Row sums of number triangle A127801.

Antti Karttunen, Table of n, a(n) for n = 0..16384

Cf. A036987, A043529.

Join[{1},3*Rest[Table[PadRight[{1}, 2^k, 0], {k, 0, 6}]//Flatten]] (* James C. McMahon, Jan 04 2025 *)

def A127802(n): return 3*int(not(n&(n+1))) if n else 1 # Chai Wah Wu, Jul 06 2022

A130093 A051731 * a lower triangular matrix with A036987 on the main diagonal and the rest zeros.

Original entry on oeis.org

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

Offset: 1

Gary W. Adamson, May 06 2007

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, ...).
A130093 also = A047999 (Sierpinski's gasket) * A036987 diagonalized, as infinite lower triangular matrices. - Gary W. Adamson, Oct 21 2009
Eigensequence of A130093 = A001511, (same sequence as row sums). - Gary W. Adamson, Oct 21 2009
Equals Sierpinski's gasket, A047999 * A036987 (diagonalized); as infinite lower triangular matrices. - Gary W. Adamson, Oct 26 2009

			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;
  ...

Cf. A001511, A051731, A036987.

Cf. A047999. - Gary W. Adamson, Oct 21 2009, Oct 26 2009

Inverse Moebius transform of a lower triangular matrix with A036987 (the Fredholm-Rueppel sequence) on the main diagonal and the rest zeros.

A266341 If A036987(n) = 1, a(n) = n - A053644(n), otherwise a(n) = n - A053644(n) + 2^(A063250(n)-1).

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jan 13 2016

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.

			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.

Antti Karttunen, Table of n, a(n) for n = 0..8191
T. Kubo and R. Vakil, On Conway's recursive sequence, Discr. Math. 152 (1996), 225-252.

Cf. A000079, A000225, A036987, A053644, A063250.

Cf. also A004001, A209861, A209862.

a(n) = my(s=bitnegimply(n>>1,n)); n - if(n,1<Kevin Ryde, Jun 15 2023

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

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).
Equally: if A063250(n) = 0, a(n) = n - A053644(n), 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.]

A115367 Row sums of correlation triangle for Fredholm-Rueppel sequence A036987.

Original entry on oeis.org

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

Offset: 0

Paul Barry, Jan 21 2006

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).

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)}}.

A115381 Correlation triangle for Fredholm-Rueppel sequence A036987.

Original entry on oeis.org

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

Offset: 0

Paul Barry, Jan 21 2006

Row sums are A115367. T(2n,n) is partial sums of squares of A036987(n).

			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

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)}

A127822 Triangle whose row sums modulo 2 give the Fredholm-Rueppel sequence A036987.

Original entry on oeis.org

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

Offset: 0

Paul Barry, Jan 30 2007

Row sums are A111982. Unsigned version of A111967.

			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

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}

cp's OEIS Frontend

A154402 Inverse Moebius transform of Fredholm-Rueppel sequence, cf. A036987.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A135416 a(n) = A036987(n)*(n+1)/2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A135560 a(n) = A007814(n) + A036987(n-1) + 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A265754 Reduced frequency counts for A004001: a(n) = A265332(n+1) - A036987(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A127802 a(0) = 1, a(n) = 3*A036987(n), n>1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

A130093 A051731 * a lower triangular matrix with A036987 on the main diagonal and the rest zeros.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A266341 If A036987(n) = 1, a(n) = n - A053644(n), otherwise a(n) = n - A053644(n) + 2^(A063250(n)-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Formula

A115367 Row sums of correlation triangle for Fredholm-Rueppel sequence A036987.