cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

A268289 a(0)=0; thereafter a(n) = a(n-1) - A037861(n).

Original entry on oeis.org

0, 1, 1, 3, 2, 3, 4, 7, 5, 5, 5, 7, 7, 9, 11, 15, 12, 11, 10, 11, 10, 11, 12, 15, 14, 15, 16, 19, 20, 23, 26, 31, 27, 25, 23, 23, 21, 21, 21, 23, 21, 21, 21, 23, 23, 25, 27, 31, 29, 29, 29, 31, 31, 33, 35, 39, 39, 41, 43, 47, 49
Offset: 0

Views

Author

Mark Moore, Jan 30 2016

Keywords

Comments

The graph of this sequence is related to the Takagi (blancmange) curve: see Lagarias (2012), Section 9, especially Theorem 9.1. [Corrected by Laura Monroe, Oct 21 2020]
Theorem: a(n) is the cardinality of the set { 1<= m <= n, ((n-m) mod 2^floor(log_2(m)+1)) < 2^floor(log_2(m)) }. See links.
From Laura Monroe, Jun 11 2020: (Start)
Consider a full balanced binary tree with n unlabeled leaves such that for each internal node, the number of leaf descendants of the two children differs by at most 1. Call a tree with this even distribution of leaves "pairwise".
Apply labels to the internal nodes, where an internal node is labeled S if its two children have the same number of leaf descendants, and D if its two children have a different number of leaf descendants, and call this an SD-tree. (For a pairwise tree, this is equivalent to saying that a node is an S-node iff it has an even number of leaf descendants.)
a(n) is then the number of S-nodes on a pairwise SD-tree with n+1 leaves.
This is proved in Props. 17 and 18 of the Monroe et al. article in the links.
One example of such a tree is the summation tree generated by a pairwise summation on n+1 summands (see example below). Another example is the tree representing a neutral single-elimination tournament on n+1 teams, as in A096351.
(End)
From Laura Monroe, Oct 23 2020: (Start)
Subtracting a(n) from n gives a sequence of dilations of increasing length on the dyadic rational points of the Takagi function. The number of points in each dilation is 2^k and the scale of each dilation in both the x and y directions is 2^k, where k = floor(log_2(n+1)).
2^(a(n)) is the number of tree automorphisms on the pairwise (i.e., divide-and-conquer) tree with n+1 leaves.
(End)

Examples

			From _Laura Monroe_, Jun 11 2020: (Start)
For n=2, the pairwise summation on 2+1=3 summands takes the form ((a+b)+c). The corresponding summation tree and SD-tree look like:
       +            D
      / \          / \
     +   c        S   c
    / \          / \
   a   b        a   b
and exactly 1 internal node has an even number of leaf descendants, hence is an S-node.
For n=3, the pairwise summation on 3+1=4 summands takes the form ((a+b)+(c+d)). The corresponding summation tree and SD-tree look like:
       +            S
      / \          / \
     +   +        S   S
    /|   |\      /|   |\
   a b   c d    a b   c d
and exactly 3 internal nodes have an even number of leaf descendants, hence are S-nodes.
(End)

Links

Crossrefs

Partial sums of A145037.
Cf. A000120, A000788, A023416, A037861, A096351, A181132, A269735, A233271, A296062.

Programs

  • C
    int a(int n)   {
    int m=n+1;
    int result=0;
    int i=0;
    while (n) {
        int ith_bit_set = m&(1<>= 1;
    }
   return result;
}
/* Laura Monroe, Jun 17 2020 */
  • Julia
    function A268289List(len)
    A = zeros(Int, len)
    for n in 1:len-1
        a, b, c = n, n & 1, 1
        while (a >>= 1) != 0
            b += a & 1
            c += 1
        end
        A[n+1] = A[n] + <<(b, 1) - c
    end
    A
end; println(A268289List(61)) # Peter Luschny, Jun 22 2020
  • Maple
    a000120 := proc(n) add(i, i=convert(n, base, 2)) end:
a023416 := proc(n) if n = 0 then 1; else add(1-e, e=convert(n, base, 2)) ; end if; end proc:
a268289:=proc(n) option remember; global a000120, a023416;
if n=0 then 0 else a268289(n-1)+a000120(n)-a023416(n); fi; end;
[seq(a268289(n),n=0..132)];
# N. J. A. Sloane, Mar 07 2016
# second Maple program:
a:= proc(n) option remember; `if`(n<0, 0,
      a(n-1)+add(2*i-1, i=Bits[Split](n)))
    end:
seq(a(n), n=0..60);  # Alois P. Heinz, Jan 18 2022
  • Mathematica
    Join[{0}, Table[DigitCount[n, 2, 1] - DigitCount[n, 2, 0], {n, 1, 100}] // Accumulate] (* Jean-François Alcover, Oct 24 2016 *)
  • PARI
    a(n) = if (n==0, 0, if (n%2, 2*a((n-1)/2)+1, a(n/2) + a(n/2-1))); \\ Michel Marcus, Jun 16 2020
  • PARI
    a(n) = my(v=binary(n+1),s=-1); for(i=1,#v, v[i]=if(v[i],s++,s--;1)); fromdigits(v,2); \\ Kevin Ryde, Jun 16 2020
  • Python
    def A268289(n): return (sum(i.bit_count() for i in range(1,n+1))<<1)-1-(n+1)*(m:=(n+1).bit_length())+(1<Chai Wah Wu, Mar 01 2023
  • Python
    def A268289(n): return sum((n+1)%m if (n+1)&(m:=1<Chai Wah Wu, Nov 11 2024

Formula

From N. J. A. Sloane, Mar 11 2016: (Start)
a(0)=0; for n > 0, a(n) = a(n-1) + A000120(n) - A023416(n) = A000788(n) - A181132(n).
a(0)=0; thereafter a(2*n) = a(n) + a(n-1), a(2*n+1) = 2*a(n) + 1.
G.f.: (1/(1-x)^2) * Sum_{k >= 0} x^(2^k)*(1-x^(2^k))/(1+x^(2^k)).
a(2^k-1) = 2^k-1, a(3*2^k-1) = 2^(k+1)-1, a(5*2^k-1) = 3*2^k-1, etc.
(End)
From Laura Monroe, Jun 11 2020: (Start)
a(n-1) = Sum_{i=0..floor(log_2(n))} (((floor(n/(2^i))+1) mod 2)*(2^i)+(-1)^((floor(n/(2^i))+1) mod 2)*(n mod (2^i))), for n>=1.
This is an explicit formula for this sequence, and is O(log(n)). This formula is proven in Prop. 18, in the Monroe et al. reference in the links. (End)
From Laura Monroe, Oct 23 2020: (Start)
a(n) = n - A296062(n).
a(n+1) = (n+1) - (2^k)*tau(x/(2^k)), where tau is the Takagi function and n+1 = (2^k)+x with x < 2^k. (End)

Extensions

Simplified definition following a suggestion from Michel Marcus. Corrected start, added more terms. - N. J. A. Sloane, Mar 07 2016

A356254 Given n balls, all of which are initially in the first of n numbered boxes, a(n) is the number of steps required to get one ball in each box when a step consists of moving to the next box every second ball from the highest-numbered box that has more than one ball.

Original entry on oeis.org

0, 1, 3, 5, 9, 13, 18, 23, 31, 39, 47, 56, 67, 78, 91, 103, 119, 135, 150, 167, 185, 203, 223, 243, 266, 289, 313, 337, 364, 391, 420, 447, 479, 511, 541, 574, 607, 640, 675, 711, 749, 787, 826, 865, 907, 949, 993, 1036, 1083, 1130, 1177, 1225, 1275, 1325, 1377
Offset: 1

Views

Author

Mikhail Kurkov, Oct 15 2022

Keywords

Comments

The sum of the number of balls being shifted at each step is A000217(n-1).
If the definition were changed to use "lowest-numbered box" instead of "highest-numbered box", then the number of steps would be A001855.

Examples

			For n = 5, the number of balls in each box at each step is as follows:
.
       |      Boxes
  Step | #1 #2 #3 #4 #5
  -----+-------------------
     0 |  5
     1 |  3  2
     2 |  3  1  1
     3 |  2  2  1
     4 |  2  1  2
     5 |  2  1  1  1
     6 |  1  2  1  1
     7 |  1  1  2  1
     8 |  1  1  1  2
     9 |  1  1  1  1  1
.
Thus, a(5) = 9.

Links

Crossrefs

Cf. A000217, A001855, A181132.

Programs

  • PARI
    a(n)=my(A, B, v); v=vector(n, i, 0); v[1]=n; A=0; while(v[n]==0, B=n; while(v[B]<2, B--); v[B+1]+=v[B]\2; v[B]-=v[B]\2; A++); A

Formula

If n = 2^k, then a(n) = (n/2)*(n + 1 - k) - 1. - Jon E. Schoenfield, Oct 17 2022
Define s(n) = floor(n/2) - 1 + s(floor(n/2)) + A181132(ceiling(n/2) - 2) for n > 3, 0 otherwise. Then a(n) = n*(n-1)/2 - s(n). - Jon E. Schoenfield, Oct 18 2022

A369332 a(n) is the sum of numbers whose binary forms can be constructed using some or all of the binary digits of 1..n.

Original entry on oeis.org

1, 17, 186, 12234, 605714, 30143621, 865062888, 374978871766, 92420578210888, 22764626902276757, 4227156427366610576, 1076625258046594762034, 196829039855755478065982, 34737980525681450161565604, 3519580168264415862502129296, 8186117385516870986118141242073
Offset: 1

Views

Author

Tamas Sandor Nagy, Jan 20 2024

Keywords

Examples

			For a(3) = 186, the binary forms of n = 1, 2 and 3 are 1, 10 and 11. These together contain four 1's and one 0. The possible combinations to construct binary numbers of these are below with their equivalent decimal values:
       1     1
      10     2
      11     3
     101     5
     110     6
     111     7
    1011    11
    1101    13
    1110    14
    1111    15
   10111    23
   11011    27
   11101    29
   11110    30
           ---
   Total:  186

Crossrefs

Cf. A181132, A000788.

Programs

  • PARI
    a(n)={my(w=0,b=0); for(i=1, n, w+=hammingweight(i); b+=logint(i,2)+1); sum(j=0, w-1, sum(k=0, b-w, my(t=j+k);if(t, binomial(t,j)*(2^t + j*(2^t-1)/t), 1) ))} \\ Andrew Howroyd, Jan 20 2024

Extensions

More terms from Andrew Howroyd, Jan 20 2024
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.