A003071 -id:A003071 - cp's OEIS frontend

A230720 Even sorting numbers, cf. A003071.

0, 14, 30, 38, 70, 78, 98, 124, 166, 174, 194, 220, 242, 268, 292, 304, 390, 398, 418, 444, 466, 492, 516, 528, 578, 604, 628, 640, 684, 696, 724, 762, 902, 910, 930, 956, 978, 1004, 1028, 1040, 1090, 1116, 1140, 1152, 1196, 1208, 1236, 1274, 1346, 1372

Offset: 1

Reinhard Zumkeller, Oct 28 2013

nonn

A003071(a(n)) mod 2 = 0.

a(n) = A003071(A092246(n)).

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Index entries for sequences related to sorting

a230720 = a003071 . a092246
a230720_list = filter even a003071_list

A230721 Odd sorting numbers, cf. A003071.

Original entry on oeis.org

1, 3, 5, 9, 11, 17, 25, 27, 33, 41, 45, 49, 65, 67, 73, 81, 85, 89, 101, 105, 109, 115, 119, 129, 161, 163, 169, 177, 181, 185, 197, 201, 205, 211, 215, 225, 245, 249, 253, 259, 263, 273, 283, 287, 297, 309, 315, 321, 385, 387, 393, 401, 405, 409, 421, 425

Offset: 1

Reinhard Zumkeller, Oct 28 2013

nonn

A003071(a(n)) mod 2 = 1;

a(n) = A003071(A230709(n+1)).

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Index entries for sequences related to sorting

a230721 = a003071 . a230709 . (+ 1)
a230721_list = filter odd a003071_list

A133457 Irregular triangle read by rows: row n gives exponents in expression for n as a sum of powers of 2.

Original entry on oeis.org

0, 1, 0, 1, 2, 0, 2, 1, 2, 0, 1, 2, 3, 0, 3, 1, 3, 0, 1, 3, 2, 3, 0, 2, 3, 1, 2, 3, 0, 1, 2, 3, 4, 0, 4, 1, 4, 0, 1, 4, 2, 4, 0, 2, 4, 1, 2, 4, 0, 1, 2, 4, 3, 4, 0, 3, 4, 1, 3, 4, 0, 1, 3, 4, 2, 3, 4, 0, 2, 3, 4, 1, 2, 3, 4, 0, 1, 2, 3, 4, 5, 0, 5, 1, 5, 0, 1, 5, 2, 5, 0, 2, 5, 1, 2, 5, 0, 1, 2, 5, 3, 5, 0, 3, 5

Offset: 1

Masahiko Shin, Nov 27 2007

This sequence contains every increasing finite sequence. For example, the finite sequence {0,2,3,5} arises from n = 45.
Essentially A030308(n,k)*k, then entries removed where A030308(n,k)=0. - R. J. Mathar, Nov 30 2007
In the corresponding irregular triangle {a(n)+1}, the m-th row gives all positive integer roots m_i of polynomial {m,k}. - see link [Shevelev]; see also A264613. - Vladimir Shevelev, Dec 13 2015

			1 = 2^0.
2 = 2^1.
3 = 2^0 + 2^1.
4 = 2^2.
5 = 2^0 + 2^2.
etc. and reading the exponents gives the rows of the triangle.

Reinhard Zumkeller, Rows n = 1..1024 of triangle, flattened
Vladimir Shevelev, The number of permutations with prescribed up-down structure as a function of two variables, INTEGERS, 12 (2012), #A1. (See Section 3, Theorem 21 and Section 8, Theorem 50)

Cf. A003071, A030308, A048793, A067255, A264613.

Cf. A073642 (row sums), A272011 (rows reversed).

a133457 n k = a133457_tabf !! (n-1) !! n
a133457_row n = a133457_tabf !! (n-1)
a133457_tabf = map (fst . unzip . filter ((> 0) . snd) . zip [0..]) $
                   tail a030308_tabf
-- Reinhard Zumkeller, Oct 28 2013, Feb 06 2013

A133457 := proc(n) local a,bdigs,i ; a := [] ; bdigs := convert(n,base,2) ; for i from 1 to nops(bdigs) do if op(i,bdigs) <> 0 then a := [op(a),i-1] ; fi ; od: a ; end: seq(op(A133457(n)),n=1..80) ; # R. J. Mathar, Nov 30 2007

Array[Join @@ Position[#, 1] - 1 &@ Reverse@ IntegerDigits[#, 2] &, 41] // Flatten (* Michael De Vlieger, Oct 08 2017 *)

a(n) = A048793(n) - 1.

More terms from R. J. Mathar, Nov 30 2007

A001855 Sorting numbers: maximal number of comparisons for sorting n elements by binary insertion.

Original entry on oeis.org

0, 1, 3, 5, 8, 11, 14, 17, 21, 25, 29, 33, 37, 41, 45, 49, 54, 59, 64, 69, 74, 79, 84, 89, 94, 99, 104, 109, 114, 119, 124, 129, 135, 141, 147, 153, 159, 165, 171, 177, 183, 189, 195, 201, 207, 213, 219, 225, 231, 237, 243, 249, 255, 261, 267, 273, 279, 285

Offset: 1

N. J. A. Sloane

Equals n-1 times the expected number of probes for a successful binary search in a size n-1 list.
Piecewise linear: breakpoints at powers of 2 with values given by A000337.
a(n) is the number of digits in the binary representation of all the numbers 1 to n-1. - Hieronymus Fischer, Dec 05 2006
It is also coincidentally the maximum number of comparisons for merge sort. - Li-yao Xia, Nov 18 2015

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, Sect 5.3.1, Eq. (3); Sect. 6.2.1 (4).
J. W. Moon, Topics on Tournaments. Holt, NY, 1968, p. 48.
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).
Tianxing Tao, On optimal arrangement of 12 points, pp. 229-234 in Combinatorics, Computing and Complexity, ed. D. Du and G. Hu, Kluwer, 1989.

Paolo Xausa, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
Michael Albert, Michael Engen, Jay Pantone, and Vincent Vatter, Universal layered permutations, arXiv:1710.04240 [math.CO], (2017).
Michael Albert, Michael Engen, Jay Pantone, and Vincent Vatter, Universal Layered Permutations, Electronic Journal of Combinatorics. Volume 25(3), 2018, #P3.23.
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
Sung-Hyuk Cha, On Integer Sequences Derived from Balanced k-ary Trees, Applied Mathematics in Electrical and Computer Engineering, 2012.
Sung-Hyuk Cha, On Complete and Size Balanced k-ary Tree Integer Sequences, International Journal of Applied Mathematics and Informatics, Issue 2, Volume 6, 2012, pp. 67-75. - From _N. J. A. Sloane_, Dec 24 2012
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 36.
Tanya Khovanova, There are no coincidences, arXiv preprint 1410.2193 [math.CO], 2014.
D. Knuth, Letter to N. J. A. Sloane, date unknown
N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 5.
R. Stephan, Some divide-and-conquer sequences ...
R. Stephan, Table of generating functions
Eric Weisstein's World of Mathematics, Sorting.
Index entries for sequences related to sorting

Partial sums of A029837.

Cf. A003071, A000337, A030190, A030308, A061168, A123753, A373709.

import Data.List (transpose)
a001855 n = a001855_list !! n
a001855_list = 0 : zipWith (+) [1..] (zipWith (+) hs $ tail hs) where
   hs = concat $ transpose [a001855_list, a001855_list]
-- Reinhard Zumkeller, Jun 03 2013

a := proc(n) local k; k := ilog2(n) + 1; 1 + n*k - 2^k end; # N. J. A. Sloane, Dec 01 2007 [edited by Peter Luschny, Nov 30 2017]

a[n_?EvenQ] := a[n] = n + 2a[n/2] - 1; a[n_?OddQ] := a[n] = n + a[(n+1)/2] + a[(n-1)/2] - 1; a[1] = 0; a[2] = 1; Table[a[n], {n, 1, 58}] (* Jean-François Alcover, Nov 23 2011, after Pari *)
a[n_] := n IntegerLength[n, 2] - 2^IntegerLength[n, 2] + 1;
Table[a[n], {n, 1, 58}] (* Peter Luschny, Dec 02 2017 *)
Accumulate[BitLength[Range[0, 100]]] (* Paolo Xausa, Sep 30 2024 *)

PARI
```
a(n)=if(n<2,0,n-1+a(n\2)+a((n+1)\2))
```

a(n)=local(m);if(n<2,0,m=length(binary(n-1));n*m-2^m+1)

def A001855(n):
    s, i, z = 0, n-1, 1
    while 0 <= i: s += i; i -= z; z += z
    return s
print([A001855(n) for n in range(1, 59)]) # Peter Luschny, Nov 30 2017

def A001855(n): return n*(m:=(n-1).bit_length())-(1<Chai Wah Wu, Mar 29 2023

Let n = 2^(k-1) + g, 0 <= g <= 2^(k-1); then a(n) = 1 + n*k - 2^k. - N. J. A. Sloane, Dec 01 2007
a(n) = Sum_{k=1..n}ceiling(log_2 k) = n*ceiling(log_2 n) - 2^ceiling(log_2(n)) + 1.
a(n) = a(floor(n/2)) + a(ceiling(n/2)) + n - 1.
G.f.: x/(1-x)^2 * Sum_{k>=0} x^2^k. - Ralf Stephan, Apr 13 2002
a(1)=0, for n>1, a(n) = ceiling(n*a(n-1)/(n-1)+1). - Benoit Cloitre, Apr 26 2003
a(n) = n-1 + min { a(k)+a(n-k) : 1 <= k <= n-1 }, cf. A003314. - Vladeta Jovovic, Aug 15 2004
a(n) = A061168(n-1) + n - 1 for n>1. - Hieronymus Fischer, Dec 05 2006
a(n) = A123753(n-1) - n. - Peter Luschny, Nov 30 2017

Additional comments from M. D. McIlroy (mcilroy(AT)dartmouth.edu)

A092246 Odd "odious" numbers (A000069).

Original entry on oeis.org

1, 7, 11, 13, 19, 21, 25, 31, 35, 37, 41, 47, 49, 55, 59, 61, 67, 69, 73, 79, 81, 87, 91, 93, 97, 103, 107, 109, 115, 117, 121, 127, 131, 133, 137, 143, 145, 151, 155, 157, 161, 167, 171, 173, 179, 181, 185, 191, 193, 199, 203, 205, 211, 213, 217, 223, 227, 229, 233

Offset: 1

Benoit Cloitre, Feb 23 2004

In other words, numbers having a binary representation ending in 1, and an odd number of 1's overall. It follows that by decrementing an odd odious number, one gets an even evil number (A125592). - Ralf Stephan, Aug 27 2013
The members of the sequence may be called primitive odious numbers because every odious number is a power of 2 times one of these numbers. Note that the difference between consecutive terms is either 2, 4, or 6. - T. D. Noe, Jun 06 2007
From Gary W. Adamson, Apr 06 2010: (Start)
a(n) = A026147(n)-th odd number, where A026147 = (1, 4, 6, 7, 10, 11, ...); e.g.,
         n: 1   2   3   4   5   6   7   8   9  10  11
  n-th odd: 1   3   5   7   9  11  13  15  17  19  21
      a(n): 1           7      11  13          19  21
etc. (End)
Numbers m, such that when merge-sorting lists of length m, the maximal number of comparisons is even: A003071(a(n)) = A230720(n). - Reinhard Zumkeller, Oct 28 2013
Fixed points of permutation pair A268717/A268718. - Antti Karttunen, Feb 29 2016

Cf. A129771, A026147.
Cf. A230709 (complement).
Cf. A268717, A268718, A268673.

a092246 n = a092246_list !! (n - 1)
a092246_list = filter odd a000069_list
-- Reinhard Zumkeller, Oct 28 2013

Table[If[n < 1, 0, 2 n - 1 - Mod[First@ DigitCount[n - 1, 2], 2]], {n, 120}] /. n_ /; EvenQ@ n -> Nothing (* Michael De Vlieger, Feb 29 2016 *)
Select[Range[1, 1001, 2], OddQ[Total[IntegerDigits[#, 2]]]&] (* Jean-François Alcover, Mar 15 2016 *)

is(n)=n%2&&hammingweight(n)%2 \\ Charles R Greathouse IV, Mar 21 2013

a(n)=4*n-if(hammingweight(n-1)%2,1,3) \\ Charles R Greathouse IV, Mar 22 2013

def A092246(n): return (n<<2)-(1 if (n-1).bit_count()&1 else 3) # Chai Wah Wu, Mar 03 2023

a(n) = 4*n + 2*A010060(n-1) - 3;

a(n) = 2*A001969(n-1) + 1.

A104258 Replace 2^i with n^i in binary representation of n.

Original entry on oeis.org

1, 2, 4, 16, 26, 42, 57, 512, 730, 1010, 1343, 1872, 2367, 2954, 3616, 65536, 83522, 104994, 130341, 160400, 194923, 234762, 280394, 345600, 406251, 474578, 551152, 637392, 732512, 837930, 954305, 33554432, 39135394, 45435458

Offset: 1

Ralf Stephan, Mar 05 2005

The following sequences all appear to have the same parity: A003071, A029886, A061297, A092524, A093431, A102393, A104258, A122248, A128975. - Jeremy Gardiner, Dec 28 2008

Michael S. Branicky, Table of n, a(n) for n = 1..10000

Cf. A104257.

a(n) = my(b=binary(n)); sum(k=1, #b, b[k]*n^(#b-k)); \\ Michel Marcus, Mar 19 2015

def a(n): return sum(n**i*int(bi) for i, bi in enumerate(bin(n)[2:][::-1]))
print([a(n) for n in range(1, 35)]) # Michael S. Branicky, Aug 02 2022

a(n) = A104257(n, n).

a(n) = [x^n] (1/(1 - x)) * Sum_{k>=0} n^k*x^(2^k)/(1 + x^(2^k)). - Ilya Gutkovskiy, Aug 17 2019

A093431 a(n) = Sum_{k=1..n} (lcm(n,n-1,...,n-k+2,n-k+1)/lcm(1,2,...,k)).

Original entry on oeis.org

1, 3, 7, 13, 31, 38, 113, 165, 265, 420, 1607, 1004, 3979, 6893, 4205, 8665, 40903, 49558, 315477, 162320, 79179, 269877, 1647123, 937552, 1810091, 8445653, 7791355, 3978237, 33071543, 19578860, 283536169, 327438713, 117635955, 742042966, 154748983, 88779588

Offset: 1

Amarnath Murthy, Mar 31 2004

nonn

The following sequences all appear to have the same parity: A003071, A029886, A061297, A092524, A093431, A102393, A104258, A122248, A128975. - Jeremy Gardiner, Dec 28 2008

Alois P. Heinz, Table of n, a(n) for n = 1..4546

Cf. A093430, A093432, A093433.

Row sums of A093430.

a:= n-> add(ilcm(seq(i,i=n-k+1..n))/ilcm(seq(j,j=1..k)),k=1..n): seq(a(n),n=1..40); # Emeric Deutsch, Jan 30 2006
# second Maple program:
b:= proc(n) option remember; `if`(n=1, 1, ilcm(b(n-1), n)) end:
a:= proc(n) option remember; local k, r, s; r, s:= 0, 1;
      for k to n do s:= ilcm(s,n-k+1); r:= r+s/b(k) od; r
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Mar 17 2018

Table[Sum[(LCM@@(n-Range[0,k-1])/LCM@@Range[k]),{k,n}],{n,33}] (* Jayanta Basu, May 22 2013 *)

Corrected and extended by Emeric Deutsch, Jan 30 2006

A061297 a(n) = Sum_{ r = 0 to n} L(n,r), where L(n,r) (A067049) = lcm(n, n-1, n-2, ..., n-r+1)/lcm(1, 2, 3, ..., r).

Original entry on oeis.org

1, 2, 4, 8, 14, 32, 39, 114, 166, 266, 421, 1608, 1005, 3980, 6894, 4206, 8666, 40904, 49559, 315478, 162321, 79180, 269878, 1647124, 937553, 1810092, 8445654, 7791356, 3978238, 33071544, 19578861, 283536170, 327438714, 117635956, 742042967, 154748984, 88779589, 1532487536, 10514107742, 3761632498

Offset: 0

Amarnath Murthy, Apr 26 2001

The following sequences all appear to have the same parity: A003071, A029886, A061297, A092524, A093431, A102393, A104258, A122248, A128975. - Jeremy Gardiner, Dec 28 2008

			a(0) = 1, a(4) = 14: we have L(4,0) = 1, L(4,1) = 4, L(4,2) = 6, L(4,3) = 2, L(4,4) = 1. For r = 0 to 4, sigma {L(4,r)}= 1 + 4 + 6 + 2 + 1 = 14.

Amarnath Murthy, Some Notions On Least Common Multiples, Smarandache Notions Journal, Vol. 12, No. 1-2-3, Spring 2001.

Tanya Khovanova, There are no coincidences, arXiv preprint 1410.2193 [math.CO], 2014.

Row sums of A067049.

tlcm(n, r) = {nt = 1; for (k = n-r+1, n, nt = lcm(nt, k);); dt = 1; for (k = 1, r, dt = lcm(dt, k);); return (nt/dt);}
a(n) = sum(r = 0, n , tlcm(n, r)); \\ Michel Marcus, Sep 14 2013

A102393 A wicked evil sequence.

Original entry on oeis.org

1, 0, 0, 4, 0, 6, 7, 0, 0, 10, 11, 0, 13, 0, 0, 16, 0, 18, 19, 0, 21, 0, 0, 24, 25, 0, 0, 28, 0, 30, 31, 0, 0, 34, 35, 0, 37, 0, 0, 40, 41, 0, 0, 44, 0, 46, 47, 0, 49, 0, 0, 52, 0, 54, 55, 0, 0, 58, 59, 0, 61, 0, 0, 64, 0, 66, 67, 0, 69, 0, 0, 72, 73, 0, 0, 76, 0, 78, 79, 0, 81, 0, 0, 84, 0, 86

Offset: 0

Paul Barry, Jan 06 2005

Elements of A026147 (evil numbers plus one) appear at positions indexed by the evil numbers A001969, 0 otherwise. A000027(n) = A102393(n) + A102394(n).

The following sequences all appear to have the same parity: A003071, A029886, A061297, A092524, A093431, A102393, A104258, A122248, A128975. - Jeremy Gardiner, Dec 28 2008

Tanya Khovanova, There are no coincidences, arXiv preprint 1410.2193 [math.CO], 2014.

Cf. A000027, A000120, A001969, A010060, A026147, A102391, A102393, A102394.

Cf. A003071, A029886, A061297, A092524, A093431, A104258, A122248, A128975.

a[n_] := If[EvenQ @ DigitCount[n, 2, 1], n + 1, 0]; Array[a, 100, 0] (* Amiram Eldar, Aug 02 2020 *)

a(n) = (n+1)(1+(-1)^A000120(n))/2.

a(n) = (n+1)(1+(-1)^A010060(n))/2.

A122248 a(n) - a(n-1) = A113474(n).

Original entry on oeis.org

0, 1, 3, 5, 9, 13, 18, 23, 31, 39, 48, 57, 68, 79, 91, 103, 119, 135, 152, 169, 188, 207, 227, 247, 270, 293, 317, 341, 367, 393, 420, 447, 479, 511, 544, 577, 612, 647, 683, 719, 758, 797, 837, 877, 919, 961, 1004, 1047, 1094, 1141, 1189

Offset: 0

Paul Barry, Aug 27 2006

First differences are A113474.

The following sequences all appear to have the same parity: A003071, A029886, A061297, A092524, A093431, A102393, A104258, A122248, A128975. - Jeremy Gardiner, Dec 28 2008

Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, preprint, 2016.
Hsien-Kuei Hwang, Svante Janson, Tsung-Hsi Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms 13:4 (2017), #47.
Tanya Khovanova, There are no coincidences, arXiv preprint 1410.2193 [math.CO], 2014.

Cf. A113474, A122247.

a(n) = sum(k=1, n, sum(j=0, n, k\2^j)) - binomial(n, 2); \\ Michel Marcus, Mar 09 2023

G.f.: (1/(1-x))*Sum{k=0..infinity, x^(2^k)/((1-x)*(1-x^(2^k)))}-x^2/(1-x)^3.
a(n) = Sum_{k=1..n} Sum_{j=0..n} floor(k/2^j) - binomial(n,2).
a(n) = A122247(n)-binomial(n,2).

cp's OEIS Frontend

A230720 Even sorting numbers, cf. A003071.

Views

Author

Keywords

Comments

Links

Programs

Haskell

A230721 Odd sorting numbers, cf. A003071.

Views

Author

Keywords

Comments

Links

Programs

Haskell

A133457 Irregular triangle read by rows: row n gives exponents in expression for n as a sum of powers of 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

Extensions

A001855 Sorting numbers: maximal number of comparisons for sorting n elements by binary insertion.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Python

Formula

Extensions

A092246 Odd "odious" numbers (A000069).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Python

Formula

A104258 Replace 2^i with n^i in binary representation of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Python

Formula

A093431 a(n) = Sum_{k=1..n} (lcm(n,n-1,...,n-k+2,n-k+1)/lcm(1,2,...,k)).

Views

Author

Keywords

Comments

Links