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

A001768 Sorting numbers: number of comparisons for merge insertion sort of n elements.

Original entry on oeis.org

0, 1, 3, 5, 7, 10, 13, 16, 19, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58, 62, 66, 71, 76, 81, 86, 91, 96, 101, 106, 111, 116, 121, 126, 131, 136, 141, 146, 151, 156, 161, 166, 171, 177, 183, 189, 195, 201, 207, 213, 219, 225, 231, 237, 243, 249, 255
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

References

  • D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 5.3.1.
  • T. A. J. Nicholson, A method for optimizing permutation problems and its industrial applications, pp. 201-217 of D. J. A. Welsh, editor, Combinatorial Mathematics and Its Applications. Academic Press, NY, 1971.
  • 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).

Links

Crossrefs

Cf. A085423, A000523.

Programs

  • Haskell
    a001768 n = n * (z - 1) - (2 ^ (z + 2) - 3 * z) `div` 6
   where z = a085423 $ n + 1
-- Reinhard Zumkeller, Mar 16 2013  after David W. Wilson's formula.
  • Maple
    Digits := 60: A001768 := proc(n) local k; add( ceil( log(3*k/4)/log(2) ), k=1..n); end;
# second Maple program:
b:= proc(n) option remember; ceil(log[2](3*n/4)) end:
a:= proc(n) option remember; `if`(n<1, 0, a(n-1)+b(n)) end:
seq(a(n), n=1..61);  # Alois P. Heinz, Dec 03 2019
  • Mathematica
    Accumulate[Ceiling[Log[2,(3*Range[60])/4]]] (* Harvey P. Dale, Oct 30 2013 *)
  • PARI
    a(n)=ceil(log(3/4*n)/log(2)) \\ Charles R Greathouse IV, Nov 04 2011

Formula

a(n) = Sum_{k=1..n} ceiling(log_2 (3k/4)). See also Problem 5.3.1-14 of Knuth.
a(n) = n(z-1)-[(2^(z+2)-3z)/6] where z = [log_2(3n+3)]. - David W. Wilson, Feb 26 2006

Extensions

Name clarified by Li-yao Xia, Nov 18 2015

A003160 a(1) = a(2) = 1, a(n) = n - a(a(n-1)) - a(a(n-2)).

Original entry on oeis.org

1, 1, 1, 2, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 8, 9, 9, 9, 10, 11, 12, 12, 12, 13, 14, 15, 15, 15, 16, 16, 16, 17, 17, 17, 18, 19, 20, 20, 20, 21, 21, 21, 22, 22, 22, 23, 24, 25, 25, 25, 26, 26, 26, 27, 27, 27, 28, 29, 30, 30, 30, 31, 32, 33, 33, 33, 34, 35, 36, 36, 36, 37, 37, 37, 38
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

Sequence of indices n where a(n-1) < a(n) appears to be given by A003156. - Joerg Arndt, May 11 2010
The number n appears A080426(n+1) times. - John Keith, Dec 31 2020

References

  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A003156, A005206, A080426, A095774, A095775.

Programs

  • Haskell
    a003160 n = a003160_list !! (n-1)
a003160_list = 1 : 1 : zipWith (-) [3..] (zipWith (+) xs $ tail xs)
   where xs = map a003160 a003160_list
-- Reinhard Zumkeller, Aug 02 2013
  • Mathematica
    Block[{a = {1, 1}}, Do[AppendTo[a, i - a[[ a[[-1]] ]] - a[[ a[[-2]] ]] ], {i, 3, 76}]; a] (* Michael De Vlieger, Dec 31 2020 *)
  • PARI
    a(n)=if(n<3,1,n-a(a(n-1))-a(a(n-2)))
  • SageMath
    @CachedFunction
def a(n): return 1 if (n<3) else n - a(a(n-1)) - a(a(n-2))
[a(n) for n in range(1, 81)] # G. C. Greubel, Nov 06 2022

Formula

a(n) is asymptotic to n/2.
Conjecture: a(n) = E/2 where we start with A := n + 1, B := 0, L := A085423(A), C := A000975(L-1), D := 0, E := C and until A = B consecutively apply B := A, A := 2*C - A - (L mod 2) + 2, L := A085423(A), C := A000975(L-1), D := D + 1, E := (1 + [A = B])*E + (-1)^D*C. - Mikhail Kurkov, May 12 2025

Extensions

Edited by Benoit Cloitre, Jan 01 2003

A085424 Number of ones in the symmetric signed digit expansion of n with q=2 (i.e., the representation of n in the (-1,0,1)_2 number system).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 2, 2, 2, 2, 3, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 2, 2, 2, 2, 3, 2, 2, 2, 3, 3, 1, 1, 2, 1, 1, 1, 2, 2, 2, 2, 3, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 2, 2, 2, 2, 3, 2, 2, 2, 3, 3, 2, 2, 3, 2, 2, 2, 3, 3, 3, 3, 4, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1
Offset: 1

Views

Author

Ralf Stephan, Jun 30 2003

Keywords

Links

Crossrefs

Cf. A005578, A085423, A007302 (nonzeros), A057526 (0's), A085425 (-1's).

Programs

  • PARI
    ep(r, n)=local(t=n/2^(r+2)); floor(t+5/6)-floor(t+4/6)-floor(t+2/6)+floor(t+1/6);
a(n)=sum(r=0, log(3*n)\log(2)-1, (ep(r, n) == 1)) ;

A085425 Number of minus ones in the symmetric signed digit expansion of n with q=2 (i.e., the representation of n in the (-1,0,1)_2 number system).

Original entry on oeis.org

0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 2, 2, 1, 1, 1, 2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 3, 2, 2, 2, 2, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 3, 3, 2, 2, 2, 3, 2, 2, 2, 2, 1
Offset: 1

Views

Author

Ralf Stephan, Jun 30 2003

Keywords

Links

Crossrefs

Cf. A005578, A085423, A007302 (nonzeros), A057526 (0's), A085424 (1's).

Programs

  • PARI
    ep(r, n)=local(t=n/2^(r+2)); floor(t+5/6)-floor(t+4/6)-floor(t+2/6)+floor(t+1/6);
a(n)=sum(r=0, log(3*n)\log(2)-1, (ep(r, n) == 1)) ;
Showing 1-4 of 4 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.