A227368 -id:A227368 - cp's OEIS frontend

A227370 Permutation which maps between A227368 and A227369.

0, 1, 2, 4, 3, 6, 5, 8, 7, 9, 10, 11, 12, 13, 14, 16, 15, 18, 17, 20, 19, 22, 21, 24, 23, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 36, 35, 38, 37, 40, 39, 42, 41, 44, 43, 46, 45, 48, 47, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 64, 63, 66, 65, 68, 67

Offset: 0

Antti Karttunen, Jul 08 2013

nonn

Conjecture 1: This is an involution (self-inverse permutation) of nonnegative integers. (Which would imply that both formulas given in A227368 and A227369 involving A227370 are valid).
Conjecture 2: (which would automatically imply the conjecture 1): the only transpositions (used to compose the permutation) are of adjacent terms 2k-1 and 2k, where A061887 gives the values of k. This is true at least for the first 35 transpositions (up to k=60).
See the example section of A227368 to get a grasp of the problem.

Antti Karttunen, Table of n, a(n) for n = 0..132
Index entries for sequences that are permutations of the natural numbers

Cf. A227368, A227369, A061887.

(define (A227370 n) (A227183 (A227369 n)))

a(n) = A227183(A227369(n)).

A227761 a(n) is the maximal difference between successive parts in the minimally runlength-encoded unordered partition of n (A227368(n)).

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 2, 0, 0, 0, 1, 0, 2, 1, 0, 0, 1, 1, 1, 0, 1, 1, 2, 0, 0, 1, 1, 0, 1, 0, 1, 1, 2, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 2, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 2, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 2, 0, 0, 1, 1, 1, 1, 1

Offset: 0

Antti Karttunen, Jul 26 2013

nonn

After n=3, only composites may obtain value 0. (But not all of them do; see A227762.) The first nine n for which a(n)=2 are 7, 13, 23, 33, 47, 61, 79, 97, 119, of which all are primes except 33 and 119. Conjecture: these values are given by A227786.

Are there any terms larger than 2?

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

A227762 gives the positions of zeros, in other words, such n that their minimally runlength-encoded partition consists of identical parts.

Cf. also A227368 (for the concept of minimally runlength-encoded unordered partition).

(define (A227761 n) (if (< n 2) 0 (- (A043276 (A163575 (A227368 n))) 1)))
;; Alternative version which uses auxiliary functions DIFF and binexp_to_ascpart which can be found in the Program section of A129594:
(define (A227761v2 n) (if (< n 2) 0 (apply max (DIFF (binexp_to_ascpart (A227368 n))))))

a(0) = a(1) = 0, and for n>1, a(n) = A043276(A163575(A227368(n))) - 1.

A000267 Integer part of square root of 4n+1.

Original entry on oeis.org

1, 2, 3, 3, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17

Offset: 0

N. J. A. Sloane

1^1, 2^1, 3^2, 4^2, 5^3, 6^3, 7^4, 8^4, 9^5, 10^5, ...
Start with n, repeatedly subtract the square root of the previous term; a(n) gives number of steps to reach 0. - Robert G. Wilson v, Jul 22 2002
Triangle A094727 read by diagonals. - Philippe Deléham, Mar 21 2014
Partial sums of A240025; a(n) = number of quarter squares <= n. - Reinhard Zumkeller, Jul 05 2014
Every number k is present consecutively (floor((2*k+3)/4)) times. - Bernard Schott, Jun 08 2019

			From _Philippe Deléham_, Mar 21 2014: (Start)
Triangle A094727 begins:
  1;
  2,  3;
  3,  4,  5;
  4,  5,  6,  7;
  5,  6,  7,  8,  9;
  6,  7,  8,  9, 10, 11; ...
Read by diagonals:
   1;
   2;
   3,  3;
   4,  4;
   5,  5,  5;
   6,  6,  6;
   7,  7,  7,  7;
   8,  8,  8,  8;
   9,  9,  9,  9,  9;
  10, 10, 10, 10, 10; (End)
G.f. = 1 + 2*x + 3*x^2 + 3*x^3 + 4*x^4 + 4*x^5 + 5*x^6 + 5*x^7 + 5*x^8 + 6*x^9 + ...

Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 73, problem 20.
Bruce C. Berndt, Ramanujan's Notebooks Part IV, Springer-Verlag, 1994, see p. 77, Entry 23.

T. D. Noe, Table of n, a(n) for n = 0..10000
Gal Cohensius, Urban Larsson, Reshef Meir, and David Wahlstedt, Cumulative subtraction games, arXiv:1805.09368 [math.CO], 2018-2020.
S. Ramanujan, Question 723, J. Ind. Math. Soc., Vol. 7 (1915), p. 240, Vol. 10 (1918), pp. 357-358.

Cf. A055086, A080037, A227368.

Cf. A000196, A002620, A016813, A070939, A094727, A240025.

a000267 = a000196 . a016813  -- Reinhard Zumkeller, Dec 13 2012

[Floor(Sqrt(4*n+1)): n in [0..100]]; // Vincenzo Librandi, Jun 08 2019

A000267:=seq(floor(sqrt(4*n+1)), n=0..100); // Bernard Schott, Jun 08 2019

Table[Floor[Sqrt[4*n + 1]], {n, 0, 100}] (* T. D. Noe, Jun 19 2012 *)

{a(n) = if( n<0, 0, sqrtint(4*n + 1))};

from math import isqrt
def A000267(n): return isqrt((n<<2)|1) # Chai Wah Wu, Nov 23 2024

floor(a(n)/2) = A000196(n).
a(n) = 1 + a(n - floor(n^(1/2))), if n>0. - Michael Somos, Jul 22 2002
a(n) = floor( 1 / ( sqrt(n + 1) - sqrt(n) ) ). - Robert A. Stump (bob_ess107(AT)yahoo.com), Apr 07 2003
a(n) = |{floor(n/k): k in Z+}|. - David W. Wilson, May 26 2005
a(n) = ceiling(2*sqrt(n+1) - 1). - Mircea Merca, Feb 03 2012
a(n) = A000196(A016813(n)). - Reinhard Zumkeller, Dec 13 2012
a(n) = A070939(A227368(n+1)), conjectured. - Antti Karttunen, Dec 28 2013
a(n) = floor( sqrt(n) + sqrt(n+2) ). [Bruno Berselli, Jan 08 2015]
a(n) = floor( sqrt(4*n + k) ) where k = 1, 2, or 3. - Michael Somos, Mar 11 2015
G.f.: (Sum_{k>0} x^floor(k^2 / 4)) / (1 - x). - Michael Somos, Mar 11 2015
a(n) = 1 + A055086(n). - Michael Somos, Sep 02 2017
a(n) = floor(sqrt(n+1)+1/2) + floor(sqrt(n)). - Ridouane Oudra, Jun 07 2019
Sum_{k>=0} (-1)^k/a(k) = Pi/8 + log(2)/4. - Amiram Eldar, Jan 26 2024

More terms from Michael Somos, Jun 13 2000

A227183 a(n) is the sum of parts of the unique unordered partition encoded in the run lengths of the binary expansion of n; row sums of A227739 for n >= 1.

Original entry on oeis.org

0, 1, 2, 2, 4, 3, 3, 3, 6, 5, 4, 6, 5, 4, 4, 4, 8, 7, 6, 8, 8, 5, 7, 9, 7, 6, 5, 7, 6, 5, 5, 5, 10, 9, 8, 10, 10, 7, 9, 11, 12, 9, 6, 10, 11, 8, 10, 12, 9, 8, 7, 9, 9, 6, 8, 10, 8, 7, 6, 8, 7, 6, 6, 6, 12, 11, 10, 12, 12, 9, 11, 13, 14, 11, 8, 12, 13, 10, 12, 14

Offset: 0

Antti Karttunen, Jul 05 2013

Like A129594 this sequence utilizes the fact that compositions (i.e., ordered partitions) can be bijectively mapped to (unordered) partitions by taking the partial sums of the list of composants after one has been subtracted from each except the first one. Compositions in turn are mapped to nonnegative integers via the runlength encoding, where the lengths of maximum runs of 0's or 1's in binary representation of n give the composants. See the OEIS Wiki page and the example below.

Each n occurs A000041(n) times in total and occurs for the first time at A227368(n) and for the last time at position A000225(n). See further comments and conjectures at A227368 and A227370.

			19 has binary expansion "10011", thus the maximal runs of identical bits (scanned from right to left) are [2,2,1]. We subtract one from each after the first one, to get [2,1,0] and then form their partial sums as [2,2+1,2+1+0], which thus maps to unordered partition {2+3+3} which adds to 8. Thus a(19)=8.

Antti Karttunen, Table of n, a(n) for n = 0..8192
A. Karttunen et al., Run-length encoding, OEIS Wiki.
Index entries for sequences related to partitions

Row sums of A227189 and A227739. Cf. A227184 (corresponding products), A227185, A227189, A227192, A129594, A226062, A227368.

Analogous sum sequences computed for other encoding schemes of unordered partitions: A036042, A056239, A161511, A243503. Cf. also A229119, A003188, A075157, A243353 (associated permutations mapping between these schemes).

Table[Function[b, Total@ Accumulate@ Prepend[If[Length@ b > 1, Rest[b] - 1, {}], First@ b] - Boole[n == 0]]@ Map[Length, Split@ Reverse@ IntegerDigits[n, 2]], {n, 0, 79}] // Flatten (* Michael De Vlieger, May 09 2017 *)

def A227183(n):
  '''Sum of parts of the unique unordered partition encoded in the run lengths of the binary expansion of n.'''
  s = 0
  b = n%2
  i = 1
  while (n != 0):
    n >>= 1
    if ((n%2) == b): # Staying in the same run of bits?
      i += 1
    else: # The run changes.
      b = n%2
      s += i
  return(s)

a(n) = Sum_{i=0..A005811(n)-1} A227189(n,i). [The defining formula]
Equivalently, for n>=1, a(n) = Sum_{i=(A173318(n-1)+1)..A173318(n)} A227739(i).
a(n) = A227192(n) - A000217(A005811(n)-1).
Other identities:
a(A129594(n)) = a(n). [This follows from the fact that conjugating a partition doesn't change its total sum]
a(A226062(n)) = a(n). [Which is also true for the "Bulgarian operation"]
From Antti Karttunen, Mar 08 2015: (Start)
Can be also obtained by mapping with an appropriate permutation from the sequences giving sizes of each partition (i.e., sum of their parts) computed for other enumerations similar to A227739:
a(n) = A036042(A229119(n)).
a(n) = A161511(A003188(n)).
a(n) = A056239(A243353(n)).
a(n) = A243503(1+A075157(n)).
(End)

A227739 Irregular table where row n lists in nondecreasing order the parts of unordered partition encoded in the runlengths of binary expansion of n; nonzero terms of A227189.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Jul 25 2013

Row n has A005811(n) elements. Each row contains a unique (unordered) partition of some integer, and all possible partitions of finite natural numbers eventually occur. The first partition that sums to k occurs at row A227368(k) and the last at row A000225(k).

Other similar tables of unordered partitions: A036036, A036037, A080576, A080577 and A112798.

			Rows are constructed as:
  Row    n in   Runlengths  With one     Partial sums   The row sums
   n    binary  collected   subtracted   of which give  to, i.e. is
                from lsb-   from all     terms on       a partition of
                to msb-end  except 1st   that row       of A227183(n)
   1       "1"        [1]        [1]     1;             1
   2      "10"      [1,1]      [1,0]     1, 1;          2
   3      "11"        [2]        [2]     2;             2
   4     "100"      [2,1]      [2,0]     2, 2;          4
   5     "101"    [1,1,1]    [1,0,0]     1, 1, 1;       3
   6     "110"      [1,2]      [1,1]     1, 2;          3
   7     "111"        [3]        [3]     3;             3
   8    "1000"      [3,1]      [3,0]     3, 3;          6
   9    "1001"    [1,2,1]    [1,1,0]     1, 2, 2;       5
  10    "1010"  [1,1,1,1]  [1,0,0,0]     1, 1, 1, 1;    4
  11    "1011"    [2,1,1]    [2,0,0]     2, 2, 2;       6
  12    "1100"      [2,2]      [2,1]     2, 3;          5
  13    "1101"    [1,1,2]    [1,0,1]     1, 1, 2;       4
  14    "1110"      [1,3]      [1,2]     1, 3;          4
  15    "1111"        [4]        [4]     4;             4
  16   "10000"      [4,1]      [4,0]     4, 4;          8

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

Row sums: A227183, row products: A227184, the initial (smallest) term of each row: A136480, the last (largest) term: A227185.

Cf. also A227189, A227738, A227736.

Table[Function[b, Accumulate@ Prepend[If[Length@ b > 1, Rest[b] - 1, {}], First@ b]]@ Map[Length, Split@ Reverse@ IntegerDigits[n, 2]], {n, 34}] // Flatten (* Michael De Vlieger, May 09 2017 *)

(define (A227739 n) (A227189bi (A227737 n) (A227740 n))) ;; The Scheme-code for A227189bi has been given in A227189.

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

A227189 Square array A(n>=0,k>=0) where A(n,k) gives the (k+1)-th part of the unordered partition which has been encoded in the binary expansion of n, as explained in A227183. The array is scanned antidiagonally as A(0,0), A(0,1), A(1,0), A(0,2), A(1,1), etc.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jul 06 2013

Discarding the trailing zero terms, on each row n there is a unique partition of integer A227183(n). All possible partitions of finite natural numbers eventually occur. The first partition that sums to n occurs at row A227368(n).

Irregular table A227739 lists only the nonzero terms.

			The top-left corner of the array:
row #  row starts as
    0  0, 0, 0, 0, 0, ...
    1  1, 0, 0, 0, 0, ...
    2  1, 1, 0, 0, 0, ...
    3  2, 0, 0, 0, 0, ...
    4  2, 2, 0, 0, 0, ...
    5  1, 1, 1, 0, 0, ...
    6  1, 2, 0, 0, 0, ...
    7  3, 0, 0, 0, 0, ...
    8  3, 3, 0, 0, 0, ...
    9  1, 2, 2, 0, 0, ...
   10  1, 1, 1, 1, 0, ...
   11  2, 2, 2, 0, 0, ...
   12  2, 3, 0, 0, 0, ...
   13  1, 1, 2, 0, 0, ...
   14  1, 3, 0, 0, 0, ...
   15  4, 0, 0, 0, 0, ...
   16  4, 4, 0, 0, 0, ...
   17  1, 3, 3, 0, 0, ...
etc.
8 has binary expansion "1000", whose runlengths are [3,1] (the length of the run in the least significant end comes first) which maps to nonordered partition {3+3} as explained in A227183, thus row 8 begins as 3, 3, 0, 0, ...
17 has binary expansion "10001", whose runlengths are [1,3,1] which maps to nonordered partition {1,3,3}, thus row 17 begins as 1, 3, 3, ...

Antti Karttunen, The first 141 antidiagonals of the table, flattened
Index entries for sequences related to partitions

Only nonzero terms: A227739. Row sums: A227183. The product of nonzero terms on row n>0 is A227184(n). Number of nonzero terms on each row: A005811. The leftmost column, after n>0: A136480. The rightmost nonzero term: A227185.

Cf. A227368 and also arrays A227186 and A227188.

(define (A227189 n) (A227189bi (A002262 n) (A025581 n)))
(define (A227189bi n k) (cond ((< (A005811 n) (+ 1 k)) 0) ((zero? k) (A136480 n)) (else (+ (- (A136480 n) 1) (A227189bi (A163575 n) (- k 1))))))

A227369 Positions where A227183 obtains new distinct values for the first time.

Original entry on oeis.org

0, 1, 2, 4, 5, 8, 9, 16, 17, 23, 32, 39, 40, 71, 72, 80, 87, 144, 151, 160, 167, 288, 295, 320, 327, 351, 576, 607, 640, 671, 672, 1183, 1184, 1311, 1312, 1344, 1375, 2368, 2399, 2624, 2655, 2688, 2719, 4736, 4767, 5248, 5279, 5376, 5407, 5503, 9472, 9599, 10496

Offset: 0

Antti Karttunen, Jul 08 2013

nonn

Sequence A227368 sorted into ascending order.

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

Cf. A227183, A227368, A227370.

a(n) = A227370(A227368(n)). [See comments and conjectures at A227370]

A227752 a(n) is the number of occurrences of n in A226062.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jul 26 2013

nonn

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

A227753 gives the positions of zeros.

In the following formula [] stands for Iverson brackets. Essentially we are just naively counting the integers which A226062 maps to n. A000225 is the guaranteed upper limit for the runlength codes for the partitions of size n:
a(n) = Sum_{i=0..A000225(A227183(n))} [A226062(i)==n].
a(n) = Sum_{i=A227368(A227183(n))..A000225(A227183(n))} [A226062(i)==n]. [This is slightly faster if somebody invents a clever formula for the lower limit A227368.]

A227762 Numbers in whose minimally runlength-encoded unordered partition all parts are equal; positions of zeros in A227761.

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 8, 9, 10, 12, 15, 16, 20, 24, 25, 28, 30, 35, 36, 42, 48, 49, 54, 56, 63, 64, 72, 80, 81, 88, 90, 99, 100, 110, 120, 121, 130, 132

Offset: 1

Antti Karttunen, Jul 26 2013

After 3 no more primes. First missing composites are: 14, 18, 21, 22, 26, 27, 32, 33, 34, 38, 39, 40, ...

			The first row in A227739 (please see its Example section) that sums to 6 occurs as its row 8 (= A227368(6)). The corresponding partition {3+3} contains only equal parts, thus 6 is a member of this sequence. The first row in A227739 that sums to 5 occurs as its row 9 (= A227368(5)). The corresponding partition {1+2+2} contains more than just one kind of summands, thus 5 do not occur in this sequence.

Cf. A227761, A227739, A227368.

cp's OEIS Frontend

A227370 Permutation which maps between A227368 and A227369.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme

Formula

A227761 a(n) is the maximal difference between successive parts in the minimally runlength-encoded unordered partition of n (A227368(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme

Formula

A000267 Integer part of square root of 4n+1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A227183 a(n) is the sum of parts of the unique unordered partition encoded in the run lengths of the binary expansion of n; row sums of A227739 for n >= 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A227739 Irregular table where row n lists in nondecreasing order the parts of unordered partition encoded in the runlengths of binary expansion of n; nonzero terms of A227189.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Scheme

Formula

A227189 Square array A(n>=0,k>=0) where A(n,k) gives the (k+1)-th part of the unordered partition which has been encoded in the binary expansion of n, as explained in A227183. The array is scanned antidiagonally as A(0,0), A(0,1), A(1,0), A(0,2), A(1,1), etc.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Scheme

A227369 Positions where A227183 obtains new distinct values for the first time.

Views

Author

Keywords

Comments

Links

Crossrefs