A061297 -id:A061297 - cp's OEIS frontend

A003071 Sorting numbers: maximal number of comparisons for sorting n elements by list merging.

0, 1, 3, 5, 9, 11, 14, 17, 25, 27, 30, 33, 38, 41, 45, 49, 65, 67, 70, 73, 78, 81, 85, 89, 98, 101, 105, 109, 115, 119, 124, 129, 161, 163, 166, 169, 174, 177, 181, 185, 194, 197, 201, 205, 211, 215, 220, 225, 242, 245, 249, 253, 259, 263, 268, 273, 283, 287, 292, 297, 304

Offset: 1

N. J. A. Sloane

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(A092246(n)) = A230720(n); a(A230709(n)) = A230721(n+1). - Reinhard Zumkeller, Oct 28 2013

D. E. Knuth, Art of Computer Programming, Vol. 3, Sections 5.2.4 and 5.3.1.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Zak Seidov, Table of n, a(n) for n = 1..10000
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
An Vinh Nguyen Dinh, Nhien Pham Hoang Bao, Terrillon Jean-Christophe, Hiroyuki Iida, Reaper Tournament System, 2018.
An Vinh Nguyen Dinh, Nhien Pham Hoang Bao, Mohd Nor Akmal Khalid, Hiroyuki Iida, Simulating competitiveness and precision in a tournament structure: a reaper tournament system, Int'l J. of Information Technology (2020) Vol. 12, 1-18.
Tanya Khovanova, There are no coincidences, arXiv preprint 1410.2193 [math.CO], 2014.
Index entries for sequences related to sorting

Cf. A001855, A133457.

a003071 n = 1 - 2 ^ last es +
   sum (zipWith (*) (zipWith (+) es [0..]) (map (2 ^) es))
   where es = reverse $ a133457_row n
-- Reinhard Zumkeller, Oct 28 2013

a[1] = 0; a[n_] := a[n] = a[n-1] + 2^IntegerExponent[n-1, 2] + DigitCount[n-1, 2, 1] - 1; Table[a[n], {n, 1, 61}] (* Jean-François Alcover, Feb 10 2012, after Henry Bottomley *)

Let n = 2^e_1 + 2^e_2 + ... + 2^e_t, e_1 > e_2 > ... > e_t >= 0, t >= 1. Then a(n) = 1 - 2^e_t + Sum_{k=1..t} (e_k + k - 1)*2^e_k [Knuth, Problem 14, Section 5.2.4].
a(n) = a(n-1) + A061338(n) = a(n-1) + A006519(n) + A000120(n) - 1 = n + A000337(A000523(n)) + a(n - 2^A000523(n)). a(2^k) = k*2^k + 1 = A002064(k). - Henry Bottomley, Apr 27 2001
G.f.: x/(1-x)^3 + 1/(1-x)^2*Sum(k>=1, (-1+(1-x)*2^(k-1))*x^2^k/(1-x^2^k)). - Ralf Stephan, Apr 17 2003

More terms from David W. Wilson

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

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

A029886 Convolution of Thue-Morse sequence A001285 with itself.

Original entry on oeis.org

1, 4, 8, 10, 12, 14, 15, 16, 22, 24, 23, 26, 29, 30, 34, 40, 38, 40, 43, 42, 47, 50, 52, 56, 55, 56, 62, 66, 64, 70, 71, 64, 78, 80, 75, 82, 83, 82, 88, 96, 89, 92, 100, 98, 102, 106, 105, 104, 111, 112, 114, 122, 118, 122, 125, 120, 130, 136, 131, 130, 141, 134, 138, 160

Offset: 0

N. J. A. Sloane

nonn

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

Seiichi Manyama, Table of n, a(n) for n = 0..10000
Tanya Khovanova, There are no coincidences, arXiv preprint 1410.2193 [math.CO], 2014.

Cf. A001285.

P[n_, x_] := (bb = IntegerDigits[n, 2]) . x^Range[Length[bb]-1, 0, -1];
TM[n_] := 1 + Mod[P[n, 1], 2];
a[n_] := Sum[TM[k] TM[n-k], {k, 0, n}];
Table[a[n], {n, 0, 63}] (* Jean-François Alcover, Aug 31 2018 *)

a(n)=sum(k=0,n,(1+subst(Pol(binary(k)),x,1)%2)*(1+subst(Pol(binary(n-k)),x,1)%2)) \\ Ralf Stephan, Aug 23 2013

G.f.: (1/4)*(3/(1 - x) - Product_{k>=0} (1 - x^(2^k)))^2. - Ilya Gutkovskiy, Apr 03 2019

A092524 Binary representation of n interpreted in base p, where p is the smallest prime factor of n: p = A020639(n).

Original entry on oeis.org

1, 2, 4, 4, 26, 6, 57, 8, 28, 10, 1343, 12, 2367, 14, 40, 16, 83522, 18, 130341, 20, 91, 22, 280394, 24, 751, 26, 112, 28, 732512, 30, 954305, 32, 244, 34, 3131, 36, 69345327, 38, 256, 40, 115925123, 42, 147087994, 44, 280, 46, 229451087, 48

Offset: 1

Reinhard Zumkeller, Apr 07 2004

n>1: a(n) = n iff n is even.
a(n) = A005836(n) iff n=6k-3, k>0 (see A016945).
The following sequences all appear to have the same parity: A003071, A029886, A061297, A092524, A093431, A102393, A104258, A122248, A128975. - Jeremy Gardiner, Dec 28 2008

			n = 35 = 7*5 = '100011': 2^5 + 2^1 + 2^0 -> a(35) = 5^5 + 5^1 + 5^0 = 3125+5+1 = 3131.

Cf. A005836, A007088, A020639.

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

a[n_] := If[EvenQ[n], n, FromDigits[IntegerDigits[n, 2], FactorInteger[n][[1, 1]]]]; Array[a, 50] (* Amiram Eldar, Aug 02 2020 *)

A128975 a(n) = the number of unordered triples of integers (a,b,c) with a+b+c=n, whose bitwise XOR is zero. Equivalently, the number of three-heap nim games with n stones which are in a losing position for the first player.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 4, 0, 0, 0, 1, 0, 1, 0, 4, 0, 1, 0, 4, 0, 4, 0, 13, 0, 0, 0, 1, 0, 1, 0, 4, 0, 1, 0, 4, 0, 4, 0, 13, 0, 1, 0, 4, 0, 4, 0, 13, 0, 4, 0, 13, 0, 13, 0, 40, 0, 0, 0, 1, 0, 1, 0, 4, 0, 1, 0, 4, 0, 4, 0, 13, 0, 1, 0, 4, 0, 4, 0, 13, 0, 4, 0, 13, 0, 13, 0, 40, 0, 1, 0, 4, 0, 4, 0

Offset: 1

Jacob A. Siehler, Apr 29 2007

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

			For example, a(14)=4; the four 3-tuples are (1,6,7), (2,5,7), (3,4,7) and (3,5,6).

Antti Karttunen, Table of n, a(n) for n = 1..65537
Tanya Khovanova, There are no coincidences, arXiv preprint 1410.2193 [math.CO], 2014.

Cf. A000120, A003987.

A128975(n) = if(n%2,0,(1/2)*((3^(hammingweight(n)-1))-1)); \\ Antti Karttunen, Sep 25 2018

a(n)=0 if n is odd; otherwise, a(n) = ( 3^(r-1) - 1)/2, where r is the number of 1's in the binary expansion of n.

A228495 Characteristic function of the odd odious numbers (A092246).

Original entry on oeis.org

0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0

Offset: 0

Ralf Stephan, Aug 23 2013

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(n+1) is the characteristic function of the even evil numbers (A125592). - Jeremy Gardiner, Feb 06 2015

Antti Karttunen, Table of n, a(n) for n = 0..65537
Tanya Khovanova, There are no coincidences, arXiv preprint 1410.2193 [math.CO], 2014.
Index entries for characteristic functions.
Index entries for sequences related to binary expansion of n.

Cf. A000035, A010060, A092246, A092436, A125592, A254379.

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

a[n_] := If[OddQ[n] && OddQ[DigitCount[n, 2, 1]], 1, 0]; Array[a, 100, 0] (* Amiram Eldar, Aug 06 2023 *)

a(n)=if(n%2==0,0,subst(Pol(binary((n-1)/2)),x,1)%2==0)

A228495(n) = ((n%2)&&(hammingweight(n)%2)); \\ Antti Karttunen, Jan 12 2019

def A228495(n): return n.bit_count()&1&n # Chai Wah Wu, Mar 03 2023

a(2n) = 0, a(2n+1) = A092436(n).

a(n) = A000035(n) * A010060(n). - Antti Karttunen, Jan 12 2019

A067049 Triangle T(n,r) = lcm(n,n-1,n-2,...,n-r+1)/lcm(1,2,3,...,r-1,r), 0 <= r < n.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 2, 1, 1, 5, 10, 10, 5, 1, 1, 6, 15, 10, 5, 1, 1, 1, 7, 21, 35, 35, 7, 7, 1, 1, 8, 28, 28, 70, 14, 14, 2, 1, 1, 9, 36, 84, 42, 42, 42, 6, 3, 1, 1, 10, 45, 60, 210, 42, 42, 6, 3, 1, 1, 1, 11, 55, 165, 330, 462, 462, 66, 33, 11, 11, 1, 1, 12, 66, 110

Offset: 0

Amarnath Murthy, Dec 30 2001

			Triangle begins:
  1;
  1, 1;
  1, 2, 1;
  1, 3, 3, 1;
  1, 4, 6, 2, 1; ...

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

Diagonals give A067046, A067047, A067048. Row sums give A061297.

t[n_, r_] :=  LCM @@ Table[n-k+1, {k, 1, r}] / LCM @@ Table[k, {k, 1, r}]; t[, 0] = 1; Table[t[n, r], {n, 0, 12}, {r, 0, n}] // Flatten (* _Jean-François Alcover, Apr 22 2014 *)

t(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);} \\ Michel Marcus, Sep 14 2013

More terms from Vladeta Jovovic, Dec 31 2001

cp's OEIS Frontend

A003071 Sorting numbers: maximal number of comparisons for sorting n elements by list merging.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

Extensions

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

Crossrefs

Programs

Maple

Mathematica

Extensions

A102393 A wicked evil sequence.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A029886 Convolution of Thue-Morse sequence A001285 with itself.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A092524 Binary representation of n interpreted in base p, where p is the smallest prime factor of n: p = A020639(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A128975 a(n) = the number of unordered triples of integers (a,b,c) with a+b+c=n, whose bitwise XOR is zero. Equivalently, the number of three-heap nim games with n stones which are in a losing position for the first player.

Views

Author

Keywords