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-5 of 5 results.

A061562 Old, obsolete version of A003075.

Original entry on oeis.org

0, 1, 3, 5, 9, 12, 16, 19, 25, 29, 35, 39, 46, 51, 56, 60
Offset: 1

Views

Author

Keywords

A000372 Dedekind numbers or Dedekind's problem: number of monotone Boolean functions of n variables, number of antichains of subsets of an n-set, number of elements in a free distributive lattice on n generators, number of Sperner families.

Original entry on oeis.org

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, 286386577668298411128469151667598498812366
Offset: 0

Views

Author

Keywords

Comments

A monotone Boolean function is an increasing function from P(S), the set of subsets of S, to {0,1}.
The count of antichains includes the empty antichain which contains no subsets and the antichain consisting of only the empty set.
a(n) is also equal to the number of upsets of an n-set S. A set U of subsets of S is an upset if whenever A is in U and B is a superset of A then B is in U. - W. Edwin Clark, Nov 06 2003
Also the number of simple games with n players in minimal winning form. - Fabián Riquelme, May 29 2011
The unlabeled case is A003182. - Gus Wiseman, Feb 20 2019
From Amiram Eldar, May 28 2021 and Michel Marcus, Apr 07 2023: (Start)
The terms were first calculated by:
a(0)-a(4) - Dedekind (1897)
a(5) - Church (1940)
a(6) - Ward (1946)
a(7) - Church (1965, verified by Berman and Kohler, 1976)
a(8) - Wiedemann (1991)
a(9) - Jäkel (2023)
a(9) - independently computed by Lennart Van Hirtum, Patrick De Causmaecker, Jens Goemaere, Tobias Kenter, Heinrich Riebler, Michael Lass, and Christian Plessl (2023)
(End)

Examples

			a(2)=6 from the antichains {}, {{}}, {{1}}, {{2}}, {{1,2}}, {{1},{2}}.
From _Gus Wiseman_, Feb 20 2019: (Start)
The a(0) = 2 through a(3) = 20 antichains:
  {}    {}     {}        {}
  {{}}  {{}}   {{}}      {{}}
        {{1}}  {{1}}     {{1}}
               {{2}}     {{2}}
               {{12}}    {{3}}
               {{1}{2}}  {{12}}
                         {{13}}
                         {{23}}
                         {{123}}
                         {{1}{2}}
                         {{1}{3}}
                         {{2}{3}}
                         {{1}{23}}
                         {{2}{13}}
                         {{3}{12}}
                         {{12}{13}}
                         {{12}{23}}
                         {{13}{23}}
                         {{1}{2}{3}}
                         {{12}{13}{23}}
(End)
		

References

  • Ian Anderson, Combinatorics of Finite Sets. Oxford Univ. Press, 1987, p. 38.
  • Jorge Luis Arocha, Antichains in ordered sets [in Spanish], Anales del Instituto de Matematicas de la Universidad Nacional Autonoma de Mexico, Vol. 27 (1987), pp. 1-21.
  • Joel Berman and Peter Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, Vol. 121 (1976), pp. 103-124.
  • Garrett Birkhoff, Lattice Theory, American Mathematical Society, Colloquium Publications, Vol. 25, 3rd ed., Providence, RI, 1967, p. 63.
  • Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 273.
  • Michael A. Harrison, Introduction to Switching and Automata Theory, McGraw Hill, NY, 1965, p. 188.
  • Donald E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.1, p. 79.
  • A. D. Korshunov, The number of monotone Boolean functions, Problemy Kibernet, No. 38, (1981), 5-108, 272. MR0640855 (83h:06013)
  • W. F. Lunnon, The IU function: the size of a free distributive lattice, in D. J. A. Welsh, editor, Combinatorial Mathematics and Its Applications. Academic Press, NY, 1971, pp. 173-181.
  • Saburo Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, pp. 38 and 214.
  • R. A. Obando, On the number of nondegenerate monotone boolean functions of n variables in an n-variable boolean algebra. In preparation.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • Douglas B. West, Introduction to Graph Theory, 2nd ed., Prentice-Hall, NJ, 2001, p. 349.

Crossrefs

Programs

  • Mathematica
    nn=5;
    stableSets[u_,Q_]:=If[Length[u]===0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r===w||Q[r,w]||Q[w,r]],Q]]]];
    Table[Length[stableSets[Subsets[Range[n]],SubsetQ]],{n,0,nn}] (* Gus Wiseman, Feb 20 2019 *)
    Table[Total[Boole[Table[UnateQ[BooleanFunction[k, n]], {k, 0, 2^(2^n) - 1}]]], {n, 0, 4}] (* Eric W. Weisstein, Jun 27 2023 *)

Formula

The asymptotics can be found in the Korshunov paper. - Boris Bukh, Nov 07 2003
a(n) = Sum_{k=1..n} binomial(n,k)*A006126(k) + 2, i.e., this sequence is the inverse binomial transform of A006126, plus 2. E.g., a(3) = 3*1 + 3*2 + 1*9 + 2 = 20. - Rodrigo A. Obando (R.Obando(AT)computer.org), Jul 26 2004
From J. M. Aranda, Jun 12 2021: (Start)
a(n) = A132581(2^n) = A132581(2^n-2^m) + A132581(2^n-2^(n-m)) for n >= m >= 0.
a(n) = A132582(3*2^n -1) for n >= 0.
(End)

Extensions

a(8) from D. H. Wiedemann, personal communication, Nov 03 1990
Additional comments from Michael Somos, Jun 10 2002
a(9) from C. Jäkel added by Michel Marcus, Apr 04 2023

A000788 Total number of 1's in binary expansions of 0, ..., n.

Original entry on oeis.org

0, 1, 2, 4, 5, 7, 9, 12, 13, 15, 17, 20, 22, 25, 28, 32, 33, 35, 37, 40, 42, 45, 48, 52, 54, 57, 60, 64, 67, 71, 75, 80, 81, 83, 85, 88, 90, 93, 96, 100, 102, 105, 108, 112, 115, 119, 123, 128, 130, 133, 136, 140, 143, 147, 151, 156, 159, 163, 167, 172, 176, 181, 186
Offset: 0

Views

Author

Keywords

Comments

Partial sums of A000120.
The graph of this sequence is a version of the Takagi curve: see Lagarias (2012), Section 9, especially Theorem 9.1. - N. J. A. Sloane, Mar 12 2016
a(n-1) is the largest possible number of ordered pairs (a,b) such that a/b is a prime in a subset of the positive integers with n elements. - Yifan Xie, Feb 21 2025

References

  • J.-P. Allouche & J. Shallit, Automatic sequences, Cambridge University Press, 2003, p. 94
  • R. Bellman and H. N. Shapiro, On a problem in additive number theory, Annals Math., 49 (1948), 333-340. See Eq. 1.9. [From N. J. A. Sloane, Mar 12 2009]
  • L. E. Bush, An asymptotic formula for the average sums of the digits of integers, Amer. Math. Monthly, 47 (1940), pp. 154-156. [From the bibliography of Stolarsky, 1977]
  • P. Cheo and S. Yien, A problem on the k-adic representation of positive integers (Chinese; English summary), Acta Math. Sinica, 5 (1955), pp. 433-438. [From the bibliography of Stolarsky, 1977]
  • M. P. Drazin and J. S. Griffith, On the decimal representation of integers, Proc. Cambridge Philos. Soc., (4), 48 (1952), pp. 555-565. [From the bibliography of Stolarsky, 1977]
  • E. N. Gilbert, Games of identification or convergence, SIAM Review, 4 (1962), 16-24.
  • Grabner, P. J.; Kirschenhofer, P.; Prodinger, H.; Tichy, R. F.; On the moments of the sum-of-digits function. Applications of Fibonacci numbers, Vol. 5 (St. Andrews, 1992), 263-271, Kluwer Acad. Publ., Dordrecht, 1993.
  • R. L. Graham, On primitive graphs and optimal vertex assignments, pp. 170-186 of Internat. Conf. Combin. Math. (New York, 1970), Annals of the NY Academy of Sciences, Vol. 175, 1970.
  • E. Grosswald, Properties of some arithmetic functions, J. Math. Anal. Appl., 28 (1969), pp.405-430.
  • Donald E. Knuth, The Art of Computer Programming, volume 3 Sorting and Searching, section 5.3.4, subsection Bitonic sorting, with C'(p) = a(p-1).
  • Hiu-Fai Law, Spanning tree congestion of the hypercube, Discrete Math., 309 (2009), 6644-6648 (see p(m) on page 6647).
  • Z. Li and E. M. Reingold, Solution of a divide-and-conquer maximin recurrence, SIAM J. Comput., 18 (1989), 1188-1200.
  • B. Lindström, On a combinatorial problem in number theory, Canad. Math. Bull., 8 (1965), 477-490.
  • Mauclaire, J.-L.; Murata, Leo; On q-additive functions. I. Proc. Japan Acad. Ser. A Math. Sci. 59 (1983), no. 6, 274-276.
  • Mauclaire, J.-L.; Murata, Leo; On q-additive functions. II. Proc. Japan Acad. Ser. A Math. Sci. 59 (1983), no. 9, 441-444.
  • M. D. McIlroy, The number of 1's in binary integers: bounds and extremal properties, SIAM J. Comput., 3 (1974), 255-261.
  • L. Mirsky, A theorem on representations of integers in the scale of r, Scripta Math., 15 (1949), pp. 11-12.
  • I. Shiokawa, On a problem in additive number theory, Math. J. Okayama Univ., 16 (1974), pp.167-176. [From the bibliography of Stolarsky, 1977]
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • K. B. Stolarsky, Power and exponential sums of digital sums related to binomial coefficient parity, SIAM J. Appl. Math., 32 (1977), 717-730.
  • Trollope, J. R. An explicit expression for binary digital sums. Math. Mag. 41 1968 21-25.

Crossrefs

For number of 0's in binary expansion of 0, ..., n see A059015.
The basic sequences concerning the binary expansion of n are A000120, A000788, A000069, A001969, A023416, A059015, A070939, A083652.

Programs

  • Haskell
    a000788_list = scanl1 (+) A000120_list
    -- Walt Rorie-Baety, Jun 30 2012
    
  • Haskell
    {a000788 0 = 0; a00788 n = a000788 n2 + a000788 (n-n2-1) + (n-n2) where n2 = n `div` 2}
    -- Walt Rorie-Baety, Jul 15 2012
    
  • Maple
    a:= proc(n) option remember; `if`(n=0, 0, a(n-1)+add(i, i=Bits[Split](n))) end:
    seq(a(n), n=0..62);  # Alois P. Heinz, Nov 11 2024
  • Mathematica
    a[n_] := Count[ Table[ IntegerDigits[k, 2], {k, 0, n}], 1, 2]; Table[a[n], {n, 0, 62}] (* Jean-François Alcover, Dec 16 2011 *)
    Table[Plus@@Flatten[IntegerDigits[Range[n], 2]], {n, 0, 62}] (* Alonso del Arte, Dec 16 2011 *)
    Accumulate[DigitCount[Range[0,70],2,1]] (* Harvey P. Dale, Jun 08 2013 *)
  • PARI
    A000788(n)={ n<3 && return(n); if( bittest(n,0) \\
    , n+1 == 1<A000788(n>>1)*2+n>>1+1 \\
    , n == 1<A000788(n>>=1)+A000788(n-1)+n )} \\ M. F. Hasler, Nov 22 2009
    
  • PARI
    a(n)=sum(k=1,n,hammingweight(k)) \\ Charles R Greathouse IV, Oct 04 2013
    
  • PARI
    a(n) = if (n==0, 0, m = logint(n, 2); r = n % 2^m; m*2^(m-1) + r + 1 + a(r)); \\ Michel Marcus, Mar 27 2018
    
  • PARI
    a(n)={n++; my(t, i, s); c=n; while(c!=0, i++; c\=2); for(j=1, i, d=(n\2^(i-j))%2; t+=(2^(i-j)*(s*d+d*(i-j)/2)); s+=d); t} \\ David A. Corneth, Nov 26 2024
    (C++) /* See David W. Wilson link. */
    
  • Python
    def A000788(n): return sum(i.bit_count() for i in range(1,n+1)) # Chai Wah Wu, Mar 01 2023
    
  • Python
    def A000788(n): return (n+1)*n.bit_count()+(sum((m:=1<>j)-(r if n<<1>=m*(r:=k<<1|1) else 0)) for j in range(1,n.bit_length()+1))>>1) # Chai Wah Wu, Nov 11 2024

Formula

McIlroy (1974) gives bounds and recurrences. - N. J. A. Sloane, Mar 24 2014
Stolarsky (1977) studies the asymptotics, and gives at least nine references to earlier work on the problem. I have added all the references that were not here already. - N. J. A. Sloane, Apr 06 2014
a(n) = Sum_{k=1..n} A000120(k). - Benoit Cloitre, Dec 19 2002
a(0) = 0, a(2n) = a(n)+a(n-1)+n, a(2n+1) = 2a(n)+n+1. - Ralf Stephan, Sep 13 2003
a(n) = n*log_2(n)/2 + O(n); a(2^n)=n*2^(n-1)+1. - Benoit Cloitre, Sep 25 2003 (The first result is due to Bellman and Shapiro, - N. J. A. Sloane, Mar 24 2014)
a(n) = n*log_2(n)/2+n*F(log_2(n)) where F is a nowhere differentiable continuous function of period 1 (see Allouche & Shallit). - Benoit Cloitre, Jun 08 2004
G.f.: (1/(1-x)^2) * Sum_{k>=0} x^2^k/(1+x^2^k). - Ralf Stephan, Apr 19 2003
a(2^n-1) = A001787(n) = n*2^(n-1). - M. F. Hasler, Nov 22 2009
a(4^n-2) = n(4^n-2).
For real n, let f(n) = [n]/2 if [n] even, n-[n+1]/2 otherwise. Then a(n) = Sum_{k>=0} 2^k*f((n+1)/2^k).
a(A000225(n)) = A173921(A000225(n)) = A001787(n); a(A000079(n)) = A005183(n). - Reinhard Zumkeller, Mar 04 2010
From Hieronymus Fischer, Jun 10 2012: (Start)
a(n) = (1/2)*Sum_{j=1..m+1} (floor(n/2^j + 1/2)*(2n + 2 - floor(n/2^j + 1/2))*2^j - floor(n/2^j)*(2n + 2 - (1 + floor(n/2^j)) * 2^j)), where m=floor(log_2(n)).
a(n) = (n+1)*A000120(n) - 2^(m-1) + 1/4 + (1/2)*Sum_{j=1..m+1} ((floor(n/2^j) + 1/2)^2 - floor(n/2^j + 1/2)^2)*2^j, where m=floor(log_2(n)).
a(2^m-1) = m*2^(m-1).
(This is the total number of '1' digits occurring in all the numbers with <= m bits.)
Generic formulas for the number of digits >= d in the base p representations of all integers from 0 to n, where 1<= d < p.
a(n) = (1/2)*Sum_{j=1..m+1} (floor(n/p^j + (p-d)/p)*(2n + 2 + ((p-2*d)/p - floor(n/p^j + (p-d)/p))*p^j) - floor(n/p^j)*(2n + 2 - (1+floor(n/p^j)) * p^j)), where m=floor(log_p(n)).
a(n) = (n+1)*F(n,p,d) + (1/2)*Sum_{j=1..m+1} ((((p-2*d)/p)*floor(n/p^j+(p-d)/p) + floor(n/p^j))*p^j - (floor(n/p^j+(p-d)/p)^2 - floor(n/p^j)^2)*p^j), where m=floor(log_p(n)) and F(n,p,d) = number of digits >= d in the base p representation of n.
a(p^m-1) = (p-d)*m*p^(m-1).
(This is the total number of digits >= d occurring in all the numbers with <= m digits in base p representation.)
G.f.: g(x) = (1/(1-x)^2)*Sum_{j>=0} (x^(d*p^j) - x^(p*p^j))/(1-x^(p*p^j)). (End)
a(n) = Sum_{k=1..n} A000120(A240857(n,k)). - Reinhard Zumkeller, Apr 14 2014
For n > 0, if n is written as 2^m + r with 0 <= r < 2^m, then a(n) = m*2^(m-1) + r + 1 + a(r). - Shreevatsa R, Mar 20 2018
a(n) = n*(n+1)/2 + Sum_{k=1..floor(n/2)} ((2k-1)((g(n,k)-1)*2^(g(n,k) + 1) + 2) - (n+1)*(g(n,k)+1)*g(n,k)/2), where g(n,k) = floor(log_2(n/(2k-1))). - Fabio Visonà, Mar 17 2020
From Jeffrey Shallit, Aug 07 2021: (Start)
A 2-regular sequence, satisfying the identities
a(4n+1) = -a(2n) + a(2n+1) + a(4n)
a(4n+2) = -2a(2n) + 2a(2n+1) + a(4n)
a(4n+3) = -4a(n) + 4a(2n+1)
a(8n) = 4a(n) - 8a(2n) + 5a(4n)
a(8n+4) = -9a(2n) + 5a(2n+1) + 4a(4n)
for n>=0. (End)
a(n) = Sum_{k=0..floor(log_2(n+1))} k * A360189(n,k). - Alois P. Heinz, Mar 06 2023

Extensions

More terms from Larry Reeves (larryr(AT)acm.org), Jan 15 2001

A006282 Sorting numbers: number of comparisons in Batcher's parallel sort.

Original entry on oeis.org

0, 1, 3, 5, 9, 12, 16, 19, 26, 31, 37, 41, 48, 53, 59, 63, 74, 82, 91, 97, 107, 114, 122, 127, 138, 146, 155, 161, 171, 178, 186, 191, 207, 219, 232, 241, 255, 265, 276, 283, 298, 309, 321, 329, 342, 351, 361, 367, 383, 395, 408, 417, 431, 441, 452, 459, 474
Offset: 1

Views

Author

Keywords

Examples

			G.f. = x^2 + 3*x^3 + 5*x^4 + 9*x^5 + 12*x^6 + 16*x^7 + 19*x^8 + 26*x^9 + 31*x^10 + ...
		

References

  • R. W. Floyd and D. E. Knuth, The Bose-Nelson sorting problem, pp. 163-172 of J. N. Srivastava, ed., A Survey of Combinatorial Theory, North-Holland, 1973.
  • D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 5.3.4, Eq. (10).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Crossrefs

Cf. A003075.
First differences are in A083742.

Programs

  • Mathematica
    c[m_, n_] /; m*n <= 1 = m*n; c[m_, n_] := c[m, n] = c[ Ceiling[m/2], Ceiling[n/2] ] + c[ Floor[m/2], Floor[n/2] ] + Floor[(m + n - 1)/2]; a[1] = 0; a[n_] := a[n] = a[ Ceiling[n/2] ] + a[ Floor[n/2] ] + c[ Ceiling[n/2], Floor[n/2] ]; Table[ a[n], {n, 1, 57}] (* Jean-François Alcover, Jan 19 2012, from formula *)
  • PARI
    (c(m, n) = local(i, j); i=ceil(m/2); j=ceil(n/2); if( m*n<2, m*n, c(i, j) + c(m\2, n\2) + (m+n-1)\2)); {a(n) = local(i, j); i=ceil(n/2); j=floor(n/2); if( n<2, 0, a(i) + a(j) + c(i, j))}; /* Michael Somos, Feb 07 2004 */

Formula

a(1)=0, a(n) = a(ceiling(n/2)) + a(floor(n/2)) + C(ceiling(n/2), floor(n/2)), n > 1, where the C function is defined in Knuth by C(m,n) = m*n if m*n <= 1 and C(m,n) = C(ceiling(m/2),ceiling(n/2)) + C(floor(m/2),floor(n/2)) + floor((m+n-1)/2) otherwise.

A067782 Minimal delay time for an n-element sorting network.

Original entry on oeis.org

0, 1, 3, 3, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 9, 9, 10
Offset: 1

Views

Author

Ron Zeno (rzeno(AT)hotmail.com), Feb 06 2002

Keywords

Comments

Or, minimal depth of a sorting network on n channels.

References

  • S. W. A.-H. Baddar, K. E. Batcher, Designing Sorting Networks: A New Paradigm, Springer (2011)
  • D. Bundala, J. Závodný, Optimal sorting networks, LATA 2014, LNCS, vol. 8370, Springer (2014), pp. 236-247
  • Thorsten Ehlers, Merging almost sorted sequences yields a 24-sorter, Information Processing Letters, Volume 118, February 2017, Pages 17-20
  • D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 5.3.4.

Crossrefs

Cf. A003075.

Extensions

a(17) = 10 is mentioned in Ehlers (2017). - N. J. A. Sloane, Aug 21 2017
Showing 1-5 of 5 results.