A227741 -id:A227741

Search: a227741 -id:a227741

Displaying 1-6 of 6 results found.

page 1

A227742

Fixed points of permutation A227741.

+20
3

1, 4, 8, 12, 16, 23, 28, 32, 36, 43, 51, 59, 64, 71, 76, 80, 84, 91, 99, 107, 115, 126, 135, 143, 148, 155, 163, 171, 176, 183, 188, 192, 196, 203, 211, 219, 227, 238, 247, 255, 263, 274, 286, 298, 307, 318, 327, 335, 340, 347, 355, 363, 371, 382, 391, 399, 404

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

LINKS

Antti Karttunen, Table of n, a(n) for n = 1..1000

FORMULA

a(n) = A173318(2*(n-1)) + (1/2)*(1 + A005811((2n)-1)).

PROG

(Scheme) (define (A227742 n) (+ (A173318 (* 2 (- n 1))) (/ (+ 1 (A005811 (- (* 2 n) 1))) 2)))

KEYWORD

nonn

AUTHOR

Antti Karttunen, Jul 25 2013

STATUS

approved

A101211

Triangle read by rows: n-th row is length of run of leftmost 1's, followed by length of run of 0's, followed by length of run of 1's, etc., in the binary representation of n.

+10
61

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,4

COMMENTS

Row n has A005811(n) elements. In rows 2^(k-1)..2^k-1 we have all the compositions (ordered partitions) of k. Other orderings of compositions: A066099, A108244, and A124734. - Jason Kimberley, Feb 09 2013

A043276(n) = largest term in n-th row. - Reinhard Zumkeller, Dec 16 2013

From the first comment it follows that we have a bijection between the positive integers and the set of all compositions. - Emeric Deutsch, Jul 11 2017

From Robert Israel, Jan 23 2018: (Start)

If n is even, row 2*n is row n with its last element incremented by 1, and row 2*n+1 is row n with 1 appended.

If n is odd, row 2*n+1 is row n with its last element incremented by 1, and row 2*n is row n with 1 appended. (End)

LINKS

Antti Karttunen, The rows 1..1023 of the table, flattened

FORMULA

a(n) = A227736(A227741(n)) = A227186(A056539(A227737(n)),A227740(n)) - Antti Karttunen, Jul 27 2013

EXAMPLE

Since 9 is 1001 in binary, the 9th row is 1,2,1.

Since 11 is 1011 in binary, the 11th row is 1,1,2.

Triangle begins:

1,1;

1,2;

1,1,1;

2,1;

1,3;

MAPLE

# Maple program due to W. Edwin Clark:

Runs := proc (L) local j, r, i, k; j := 1: r[j] := L[1]: for i from 2 to nops(L) do if L[i] = L[i-1] then r[j] := r[j], L[i] else j := j+1: r[j] := L[i] end if end do: [seq([r[k]], k = 1 .. j)] end proc: RunLengths := proc (L) map(nops, Runs(L)) end proc: c := proc (n) ListTools:-Reverse(convert(n, base, 2)): RunLengths(%) end proc: # Row n is obtained with the command c(n). - Emeric Deutsch, Jul 03 2017

# Maple program due to W. Edwin Clark, yielding the integer ind corresponding to a given composition (the index of the composition):

ind := proc (x) local X, j, i: X := NULL: for j to nops(x) do if type(j, odd) then X := X, seq(1, i = 1 .. x[j]) end if: if type(j, even) then X := X, seq(0, i = 1 .. x[j]) end if end do: X := [X]: add(X[i]*2^(nops(X)-i), i = 1 .. nops(X)) end proc; # Clearly, ind(c(n))= n. - Emeric Deutsch, Jan 23 2018

MATHEMATICA

Table[Length /@ Split@ IntegerDigits[n, 2], {n, 38}] // Flatten (* Michael De Vlieger, Jul 11 2017 *)

PROG

(Scheme, two variants)

(define (A101211 n) (A227736 (A227741 n)))

(define (A101211v2 n) (A227186bi (A056539 (A227737 n)) (A227740 n)))

;; Scheme-implementation for A227186bi can be found under A227186. - Antti Karttunen, Jul 27 2013

(Haskell)

import Data.List (group)

a101211 n k = a101211_tabf !! (n-1) !! (k-1)

a101211_row n = a101211_tabf !! (n-1)

a101211_tabf = map (reverse . map length . group) $ tail a030308_tabf

-- Reinhard Zumkeller, Dec 16 2013

(Python)

from itertools import groupby

def arow(n): return [len(list(g)) for k, g in groupby(bin(n)[2:])]

def auptorow(rows):

alst = []

for i in range(1, rows+1): alst.extend(arow(i))

return alst

print(auptorow(38)) # Michael S. Branicky, Oct 02 2021

CROSSREFS

A070939(n) gives the sum of terms in row n, while A167489(n) gives the product of its terms. A090996 gives the first column. A227736 lists the terms of each row in reverse order.

Cf. also A227186.

Cf. A030308, A175911.

KEYWORD

nonn,base,tabf

AUTHOR

Leroy Quet, Dec 13 2004

EXTENSIONS

More terms from Emeric Deutsch, Apr 12 2005

STATUS

approved

A227736

Irregular table read by rows: the first entry of n-th row is length of run of rightmost identical bits (either 0 or 1, equal to n mod 2), followed by length of the next run of bits, etc., in the binary representation of n, when scanned from the least significant to the most significant end.

+10
22

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,4

COMMENTS

Row n has A005811(n) terms. In rows 2^(k-1)..2^k-1 we have all the compositions (ordered partitions) of k. Other orderings of compositions: A101211, A066099, A108244 and A124734.

Each row n (n>=1) contains the initial A005811(n) nonzero terms from the beginning of row n of A227186. A070939(n) gives the sum of terms on row n, while A167489(n) gives the product of its terms. A136480 gives the first column. A101211 lists the terms of each row in reverse order.

LINKS

Antti Karttunen, The rows 1..1023 of the table, flattened

Mikhail Kurkov, Comments on A227736 [verification needed]

Claude Lenormand, Deux transformations sur les mots, Preprint, 5 pages, Nov 17 2003. Apparently unpublished. This is a scanned copy of the version that the author sent to me in 2003. - N. J. A. Sloane, Sep 09 2018. See Procedure 1.

FORMULA

a(n) = A227186(A227737(n), A227740(n)).

a(n) = A101211(A227741(n)).

EXAMPLE

Table begins as:

Row n in Terms on

n binary that row

1 1 1;

2 10 1,1;

3 11 2;

4 100 2,1;

5 101 1,1,1;

6 110 1,2;

7 111 3;

8 1000 3,1;

9 1001 1,2,1;

10 1010 1,1,1,1;

11 1011 2,1,1;

12 1100 2,2;

13 1101 1,1,2;

14 1110 1,3;

15 1111 4;

16 10000 4,1;

etc. with the terms of row n appearing in reverse order compared how the runs of the same length appear in the binary expansion of n (Cf. A101211).

From Omar E. Pol, Sep 08 2013: (Start)

Illustration of initial terms:

---------------------------------------

k m Diagram Composition

---------------------------------------

. _

1 1 |_|_ 1;

2 1 |_| | 1, 1,

2 2 |_ _|_ 2;

3 1 |_ | | 2, 1,

3 2 |_|_| | 1, 1, 1,

3 3 |_| | 1, 2,

3 4 |_ _ _|_ 3;

4 1 |_ | | 3, 1,

4 2 |_|_ | | 1, 2, 1,

4 3 |_| | | | 1, 1, 1, 1,

4 4 |_ _|_| | 2, 1, 1,

4 5 |_ | | 2, 2,

4 6 |_|_| | 1, 1, 2,

4 7 |_| | 1, 3,

4 8 |_ _ _ _|_ 4;

5 1 |_ | | 4, 1,

5 2 |_|_ | | 1, 3, 1,

5 3 |_| | | | 1, 1, 2, 1,

5 4 |_ _|_ | | 2, 2, 1,

5 5 |_ | | | | 2, 1, 1, 1,

5 6 |_|_| | | | 1, 1, 1, 1, 1,

5 7 |_| | | | 1, 2, 1, 1,

5 8 |_ _ _|_| | 3, 1, 1,

5 9 |_ | | 3, 2,

5 10 |_|_ | | 1, 2, 2,

5 11 |_| | | | 1, 1, 1, 2,

5 12 |_ _|_| | 2, 1, 2,

5 13 |_ | | 2, 3,

5 14 |_|_| | 1, 1, 3,

5 15 |_| | 1, 4,

5 16 |_ _ _ _ _| 5;

Also irregular triangle read by rows in which row k lists the compositions of k, k >= 1.

Triangle begins:

[1];

[1,1], [2];

[2,1], [1,1,1], [1,2],[3];

[3,1], [1,2,1], [1,1,1,1], [2,1,1], [2,2], [1,1,2], [1,3], [4];

[4,1], [1,3,1], [1,1,2,1], [2,2,1], [2,1,1,1], [1,1,1,1,1], [1,2,1,1], [3,1,1], [3,2], [1,2,2], [1,1,1,2], [2,1,2], [2,3], [1,1,3], [1,4], [5];

Row k has length A001792(k-1).

Row sums give A001787(k), k >= 1.

(End)

MATHEMATICA

Array[Length /@ Reverse@ Split@ IntegerDigits[#, 2] &, 34] // Flatten (* Michael De Vlieger, Dec 11 2020 *)

PROG

(Scheme) (define (A227736 n) (A227186bi (A227737 n) (A227740 n))) ;; The Scheme-function for A227186bi has been given in A227186.

(Haskell)

import Data.List (group)

a227736 n k = a227736_tabf !! (n-1) !! (k-1)

a227736_row n = a227736_tabf !! (n-1)

a227736_tabf = map (map length . group) $ tail a030308_tabf

-- Reinhard Zumkeller, Aug 11 2014

CROSSREFS

Cf. A227738 and also A227739 for similar table for unordered partitions.

Cf. A030308, A245562, A245563.

KEYWORD

nonn,base,tabf

AUTHOR

Antti Karttunen, Jul 25 2013

STATUS

approved

A173318

Partial sums of A005811.

+10
11

0, 1, 3, 4, 6, 9, 11, 12, 14, 17, 21, 24, 26, 29, 31, 32, 34, 37, 41, 44, 48, 53, 57, 60, 62, 65, 69, 72, 74, 77, 79, 80, 82, 85, 89, 92, 96, 101, 105, 108, 112, 117, 123, 128, 132, 137, 141, 144, 146, 149, 153, 156, 160, 165, 169, 172, 174, 177, 181, 184, 186, 189

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

Partial sums of number of runs in binary expansion of n (n>0). Partial sums of number of 1's in Gray code for n. The subsequence of squares in this partial sum begins 0, 1, 4, 9, 144, 169, 256, 289, 324 (since we also have 32 and 128 I wonder about why so many powers). The subsequence of primes in this partial sum begins: 3, 11, 17, 29, 31, 37, 41, 53, 79, 89, 101, 137, 149, 181, 191, 197, 229, 271.

Note: A227744 now gives the squares, which occur at positions given by A227743. - Antti Karttunen, Jul 27 2013

LINKS

Antti Karttunen, Table of n, a(n) for n = 0..8191

Richard Blecksmith and Purushottam W. Laud, Some Exact Number Theory Computations via Probability Mechanisms, American Mathematical Monthly, volume 102, number 10, December 1995, pages 893-903, with a(n) = Sum_{j=0..n} b_j as calculated in section 2.

Hsien-Kuei Hwang, Svante Janson and Tsung-Hsi Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, volume 13, number 4, December 2017, article number 47, pages 1-43. Also first authors' copy, 2016. See example 5.5.

Kevin Ryde, Iterations of the Dragon Curve, see index "DirCumul".

FORMULA

a(n) = sum(i=0..n) A005811(i) = sum(i=0..n) (A037834(i)+1) = sum(i=0..n) (A069010(i) + A033264(i)).

a(A000225(n)) = A001787(n) = A000788(A000225(n)). - Antti Karttunen, Jul 27 2013 & Aug 09 2013

a(2n) = 2*a(n) + n - 2*(ceiling(A005811(n)/2) - (n mod 2)), a(2n+1) = 2*a(n) + n + 1. - Ralf Stephan, Aug 11 2013

EXAMPLE

1 has 1 run in its binary representation "1".

2 has 2 runs in its binary representation "10".

3 has 1 run in its binary representation "11".

4 has 2 runs in its binary representation "100".

5 has 3 runs in its binary representation "101".

Thus a(1) = 1, a(2) = 1+2 = 3, a(3) = 1+2+1 = 4, a(4) = 1+2+1+2 = 6, a(5) = 1+2+1+2+3 = 9.

MATHEMATICA

Accumulate[Join[{0}, Table[Length[Split[IntegerDigits[n, 2]]], {n, 110}]]] (* Harvey P. Dale, Jul 29 2013 *)

PROG

(PARI) a(n) = my(v=binary(n+1), d=0, e=4); for(i=1, #v, if(v[i], v[i]=#v-i+d; d+=e; e=0, e=4)); fromdigits(v, 2)>>1; \\ Kevin Ryde, Aug 27 2021

CROSSREFS

Cf. A005811, A000788, A056539, A014707, A014577, A082410, A000975, A034947.

Cf. also A227737, A227741, A227742.

Cf. A227744 (squares occurring), A227743 (indices of squares).

KEYWORD

easy,nonn

AUTHOR

Jonathan Vos Post, Feb 16 2010

STATUS

approved

A227737

n occurs as many times as there are runs in binary representation of n.

+10
9

1, 2, 2, 3, 4, 4, 5, 5, 5, 6, 6, 7, 8, 8, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 12, 12, 13, 13, 13, 14, 14, 15, 16, 16, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 24, 24, 25, 25, 25, 26, 26, 26, 26

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

a(n) = the least integer k such that A173318(k) >= n, which implies that each n occurs A005811(n) times.

Although as such quite uninteresting, this sequence is useful for computing irregular tables like A101211, A227736, A227738 and A227739.

LINKS

Antti Karttunen, Table of n, a(n) for n = 1..5120

EXAMPLE

1 has one run in its binary representation "1", thus 1 occurs once.

2 has two runs in its binary representation "10", thus 2 occurs twice.

3 has one run in its binary representation "11", thus 3 occurs only once.

4 has two runs in its binary representation "100", thus 4 occurs twice.

5 has three runs in its binary representation "101", thus 5 occurs three times.

The sequence thus begins as 1, 2,2, 3, 4,4, 5,5,5, ...

MATHEMATICA

Table[ConstantArray[n, Length@ Split@ IntegerDigits[n, 2]], {n, 26}] // Flatten (* Michael De Vlieger, May 09 2017 *)

Table[PadRight[{}, Length[Split[IntegerDigits[n, 2]]], n], {n, 40}]//Flatten (* Harvey P. Dale, Jul 23 2021 *)

PROG

(Scheme with Antti Karttunen's IntSeq-library) (define A227737 (LEAST-GTE-I 1 1 A173318))

CROSSREFS

Cf. A227740, A227741, A005811, A173318.

KEYWORD

nonn,base

AUTHOR

Antti Karttunen, Jul 25 2013

STATUS

approved

A227740

Integers from 0 to A037834(n) followed by integers from 0 to A037834(n+1) and so on.

+10
8

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,9

COMMENTS

Equivalently, integers from 0 to A005811(n)-1 followed by integers from 0 to A005811(n+1)-1 and so on.

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 1..2272

FORMULA

a(n) = n - (1 + A173318(A227737(n)-1)).

MATHEMATICA

Table[Range[0, #] &@ Total@ Flatten@ Map[Abs@ Differences@ # &,

Partition[IntegerDigits[n, 2], 2, 1]], {n, 34}] // Flatten (* Michael De Vlieger, May 09 2017 *)