A045690 -id:A045690 - cp's OEIS frontend

A342517 Number of strict integer partitions of n with strictly increasing first quotients.

1, 1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 8, 8, 10, 11, 13, 14, 16, 16, 19, 21, 23, 27, 29, 31, 34, 36, 40, 43, 47, 49, 53, 56, 59, 66, 71, 75, 81, 86, 89, 97, 104, 110, 119, 123, 132, 143, 148, 156, 168, 177, 184, 198, 209, 218, 232, 246, 257, 269, 282, 294

Offset: 0

Gus Wiseman, Mar 20 2021

nonn

Also the number of reversed strict partitions of n with strictly increasing first quotients.

The first quotients of a sequence are defined as if the sequence were an increasing divisor chain, so for example the first quotients of (6,3,1) are (1/2,1/3).

			The partition (14,8,5,3,2) has first quotients (4/7,5/8,3/5,2/3) so is not counted under a(32), even though the differences (-6,-3,-2,-1) are strictly increasing.
The a(1) = 1 through a(13) = 10 partitions (A..D = 10..13):
  1   2   3    4    5    6    7    8     9     A     B     C     D
          21   31   32   42   43   53    54    64    65    75    76
                    41   51   52   62    63    73    74    84    85
                              61   71    72    82    83    93    94
                                   521   81    91    92    A2    A3
                                         621   532   A1    B1    B2
                                               721   632   732   C1
                                                     821   921   643
                                                                 832
                                                                 A21

Eric Weisstein's World of Mathematics, Logarithmically Concave Sequence.
Gus Wiseman, Sequences counting and ranking integer partitions by the differences of their successive parts.
Gus Wiseman, Sequences counting and ranking partitions and compositions by their differences and quotients.

The version for differences instead of quotients is A179254.
The version for chains of divisors is A342086 (non-strict: A057567).
The non-strict ordered version is A342493.
The non-strict version is A342498 (ranking: A342524).
The weakly increasing version is A342516.
The strictly decreasing version is A342518.
A000041 counts partitions (strict: A000009).
A001055 counts factorizations (strict: A045778, ordered: A074206).
A003238 counts chains of divisors summing to n - 1 (strict: A122651).
A045690 counts sets with maximum n with all adjacent elements y < 2x.
A167865 counts strict chains of divisors > 1 summing to n.
A342096 counts partitions with all adjacent parts x < 2y (strict: A342097).
A342098 counts (strict) partitions with all adjacent parts x > 2y.
Cf. A000005, A003114, A003242, A005117, A018819, A067824, A238710, A253249, A318991, A318992.

Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&Less@@Divide@@@Reverse/@Partition[#,2,1]&]],{n,0,30}]

A342518 Number of strict integer partitions of n with strictly decreasing first quotients.

Original entry on oeis.org

1, 1, 1, 2, 2, 3, 4, 4, 5, 7, 8, 9, 11, 12, 13, 17, 18, 21, 24, 28, 30, 34, 37, 41, 47, 52, 56, 63, 68, 72, 83, 89, 99, 108, 117, 128, 139, 149, 163, 179, 189, 203, 217, 233, 250, 272, 289, 305, 329, 355, 381, 410, 438, 471, 505, 540, 571, 607, 645, 683, 726

Offset: 0

Gus Wiseman, Mar 20 2021

nonn

Also the number of reversed strict integer partitions of n with strictly decreasing first quotients.

The first quotients of a sequence are defined as if the sequence were an increasing divisor chain, so for example the first quotients of (6,3,1) are (1/2,1/3).

			The strict partition (12,10,6,3,1) has first quotients (5/6,3/5,1/2,1/3) so is counted under a(32), even though the differences (-2,-4,-3,-2) are not strictly decreasing.
The a(1) = 1 through a(13) = 12 partitions (A..D = 10..13):
  1   2   3    4    5    6     7    8     9     A      B     C     D
          21   31   32   42    43   53    54    64     65    75    76
                    41   51    52   62    63    73     74    84    85
                         321   61   71    72    82     83    93    94
                                    431   81    91     92    A2    A3
                                          432   541    A1    B1    B2
                                          531   631    542   543   C1
                                                4321   641   642   652
                                                       731   651   742
                                                             741   751
                                                             831   841
                                                                   5431

Eric Weisstein's World of Mathematics, Logarithmically Concave Sequence.
Gus Wiseman, Sequences counting and ranking integer partitions by the differences of their successive parts.
Gus Wiseman, Sequences counting and ranking partitions and compositions by their differences and quotients.

The version for differences instead of quotients is A320388.
The version for chains of divisors is A342086 (non-strict: A057567).
The non-strict ordered version is A342494.
The non-strict version is A342499 (ranking: A342525).
The strictly increasing version is A342517.
The weakly decreasing version is A342519.
A000041 counts partitions (strict: A000009).
A001055 counts factorizations (strict: A045778, ordered: A074206).
A003238 counts chains of divisors summing to n - 1 (strict: A122651).
A045690 counts sets with maximum n with all adjacent elements y < 2x.
A167865 counts strict chains of divisors > 1 summing to n.
A342096 counts partitions with all adjacent parts x < 2y (strict: A342097).
A342098 counts (strict) partitions with all adjacent parts x > 2y.
Cf. A000005, A003114, A003242, A005117, A018819, A067824, A238710, A253249, A318991, A318992.

Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&Greater@@Divide@@@Reverse/@Partition[#,2,1]&]],{n,0,30}]

A155092 Matrix inverse of A155091.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 3, 3, 2, 1, 1, 6, 6, 4, 2, 1, 1, 11, 11, 7, 4, 2, 1, 1, 22, 22, 14, 8, 4, 2, 1, 1, 42, 42, 27, 15, 8, 4, 2, 1, 1, 84, 84, 54, 30, 16, 8, 4, 2, 1, 1, 165, 165, 106, 59, 31, 16, 8, 4, 2, 1, 1, 330, 330, 212, 118, 62, 32, 16, 8, 4, 2, 1, 1, 654, 654, 420, 234, 123, 63

Offset: 1

Mats Granvik, Jan 20 2009

First column is A002083. Rows sums are A045690.

Eigentriangle of A101688. - Paul Barry, Mar 01 2011

			Table begins:
1,
1,1,
1,1,1,
2,2,1,1,
3,3,2,1,1,
6,6,4,2,1,1,
11,11,7,4,2,1,1,
22,22,14,8,4,2,1,1,
42,42,27,15,8,4,2,1,1,
84,84,54,30,16,8,4,2,1,1,

Cf. A002083, A045690.

A242430 Decimal expansion of the unforgeable pattern-free binary word constant, a constant mentioned in A003000.

Original entry on oeis.org

2, 6, 7, 7, 8, 6, 8, 4, 0, 2, 1, 7, 8, 8, 9, 1, 1, 2, 3, 7, 6, 6, 7, 1, 4, 0, 3, 5, 8, 4, 3, 0, 2, 5, 5, 2, 5, 5, 5, 0, 5, 9, 8, 9, 7, 9, 9, 3, 4, 8, 4, 5, 3, 2, 0, 7, 6, 3, 1, 1, 8, 8, 8, 5, 1, 1, 2, 1, 4, 9, 3, 7, 7, 8, 5, 2, 3, 2, 7, 6, 2, 8, 5, 3, 5, 4, 4, 7, 6, 2, 2, 3, 8, 5, 6, 1, 3, 6, 8, 4

Offset: 0

Jean-François Alcover, May 14 2014

A binary word (a word over a 2-letter alphabet) is said "unforgeable" if it never matches a left or right shift of itself. The limit lower bound of the number of unforgeable words of length n is (0.26778684...)*2^n.

			0.267786840217889112376671403584302552555...

Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, p. 369.
See more references and links in A003000, which is the main entry for this subject.

Cf. A003000, A006156, A007777, A028445, A045690.

digits = 100; k0 = 5; dk = 5; Clear[r]; r[k_] := r[k] = Sum[(-1)^(n-1)*2/(2^(2^(n+1)-1)-1) * Product[2^(2^m-1)/(2^(2^m-1)-1), {m, 2, n}], {n, 1, k}] // N[#, digits+10]&; r[k0]; r[k = k0 + dk]; While[RealDigits[r[k], 10, digits+10] !=  RealDigits[r[k - dk], 10, digits+10], Print["k = ", k]; k = k + dk]; RealDigits[r[k], 10, digits] // First

A105284 a(n)/4^n is the measure of the subset of [0,1] remaining when all intervals of the form [b/2^m - 1/2^(2m+1), b/2^m + 1/2^(2m+1)] have been removed, with b and m positive integers, b<2^m and m<=n.

Original entry on oeis.org

1, 3, 10, 37, 142, 558, 2212, 8811, 35170, 140538, 561868, 2246914, 8986540, 35943948, 143771368, 575076661, 2300289022, 9201120918, 36804413332, 147217512790, 588869770084, 2355478518468, 9421912950136, 37687649553630

Offset: 0

Henry Bottomley, Apr 25 2005

nonn

Removing all such intervals (without an upper limit on n) leaves a nowhere dense subset of [0,1]. However, since each step removes additional points of measure no more than 1/2^(n+1), this nowhere dense subset must make up at least half of [0,1] and so be of positive measure. In fact its measure is 0.535573680435778224753342807..., the limit of a(n)/A000302(n).

			At the start the interval [0,1] has measure 1=1/1. The first step removes the interval [3/8,5/8], leaving a subset with a measure of 3/4. The second step in addition removes the intervals [7/32,9/32] and [23/32,25/32], leaving a subset with a measure of 5/8=10/16. The third step in addition removes the intervals [15/128,17/128], [47/128,3/8), (5/8,81/128] and [111/128,113/128], leaving a subset with a measure of 37/64.

a(n) = 4*a(n-1)-A045690(n) for n>0. a(2n+2)=6*a(2n+1)-8*a(2n); a(4n+3)=6*a(4n+2)-8*a(4n+1)+a(n); a(4n+5)=6*a(4n+4)-8*a(4n+3)+2*a(n).

a(n) = A045690(2n+2). a(2n+1)=4*a(2n)-a(n); a(2n+2)=4*a(2n+1)-2*a(n). - Mamuka Jibladze, Sep 30 2014

A331392 Sum, over all binary strings w of length n, of the length of the shortest border of w.

Original entry on oeis.org

0, 2, 4, 12, 24, 60, 120, 264, 528, 1116, 2232, 4584, 9168, 18616, 37232, 75056, 150112, 301556, 603112, 1209064, 2418128, 4842504, 9685008, 19383408, 38766816, 77562648, 155125296, 310312528, 620625056, 1241382832, 2482765664, 4965813280, 9931626560

Offset: 1

Jeffrey Shallit, Jan 15 2020

nonn

A nonempty word w is a border of a string x if w is both a prefix and suffix of x, and w does not equal x.

			For n = 3, the words are 000,001,010,011 and their binary complements.  The shortest border of 000 and 010 is 0, and the other words have no border.  So a(3) = 4.

Cf. A045690, A091065, A331393.

From Rémy Sigrist, Jan 16 2020: (Start)
Apparently, for any k > 0:
- a(2*k+1) = 2*a(k),
- a(2*k) = 2*a(2*k-1) + 2*k*A045690(k).
(End)

More terms from Rémy Sigrist, Jan 15 2020

A361942 For any number n >= 0 with binary expansion (b_1, ..., b_w), a(n) is the least p > 0 such that b_i = b_{p+i} for i = 1..w-p.

Original entry on oeis.org

1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 2, 3, 4, 3, 4, 1, 5, 4, 3, 4, 5, 2, 3, 4, 5, 4, 5, 3, 5, 4, 5, 1, 6, 5, 4, 5, 3, 5, 4, 5, 6, 5, 2, 5, 6, 3, 4, 5, 6, 5, 6, 4, 6, 5, 3, 4, 6, 5, 6, 4, 6, 5, 6, 1, 7, 6, 5, 6, 4, 6, 5, 6, 7, 3, 5, 6, 4, 6, 5, 6, 7, 6, 5, 6, 7, 2, 5

Offset: 0

Rémy Sigrist, Mar 31 2023

Leading zeros in binary expansions of positive integers are ignored.
This sequence is a variant of A302291 related to fractional powers of words.
For any k > 0, the value k appears A045690(k) times in a(2^(k-1)), ..., a(2^k-1).

			The first terms, alongside the binary expansion of n split into chunks of length a(n), are:
  n   a(n)  bin(n)
  --  ----  ------
   0     1  0
   1     1  1
   2     2  10
   3     1  1|1
   4     3  100
   5     2  10|1
   6     3  110
   7     1  1|1|1
   8     4  1000
   9     3  100|1
  10     2  10|10
  11     3  101|1
  12     4  1100
  13     3  110|1
  14     4  1110
  15     1  1|1|1|1

Jean-Paul Allouche and Jeffrey Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 23.

Index entries for sequences related to binary expansion of n

Cf. A045690, A070939, A091065, A302291.

a(n) = { my (b = if (n, binary(n), [0])); for (p = 1, oo, if (b[1..#b-p] == b[1+p..#b], return (p););); }

a(n) <= A302291(n).
a(n) <= A070939(n) with equality iff n belongs to A091065.
a(2^k-1) = 1 for any k >= 0.
a(2^k) = k+1 for any k >= 0.

A107284 a(n)/4^n is the measure of the subset of [0,1] remaining when all intervals of the form [b/2^m - 1/2^(2m), b/2^m + 1/2^(2m)] have been removed, with b and m positive integers, b < 2^m and m <= n.

Original entry on oeis.org

1, 2, 6, 20, 74, 284, 1116, 4424, 17622, 70340, 281076, 1123736, 4493828, 17973080, 71887896, 287542736, 1150153322, 4600578044, 18402241836, 73608826664, 294435025580, 1177739540168, 4710957036936, 18843825900272, 75375299107260

Offset: 0

Henry Bottomley, May 19 2005

nonn

Removing all such intervals (without an upper limit on n) leaves a nowhere dense subset of [0,1]. It is of positive measure, namely 0.2677868402178891123766714035843..., the limit of a(n)/4^n. This is the same as the limit of A003000(n)/2^n and of A045690(n)/2^n and half the limit of A105284(n)/4^n.

It can be shown that this sequence also counts the pairs of binary sequences with Conway number 0. These Conway numbers arise in the analysis of Penney's game and measure to what degree two sequences overlap; see the Nishiyama paper in the links for further details. - Reed Phillips, Jun 09 2020

			At the start the interval [0,1] has measure 1 = 1/1. The first step removes the interval [1/4,3/4], leaving a subset with measure of 1/2 = 2/4. The second step in addition removes the intervals [3/16,1/4) and (3/4,13/16], leaving a subset with measure of 3/8 = 6/16. The third step in addition removes the intervals [7/64,9/64] and [55/64,57/64], leaving a subset with measure of 5/16 = 20/64.

Yutaka Nishiyama, Pattern Matching Probabilities and Paradoxes as a New Variation on Penney's Coin Game, International Journal of Pure and Applied Mathematics, Volume 59 No. 3 2010, 357-366.

Cf. A003000, A045690, A105284.

a(n) = 4*a(n-1) - A003000(n) = 2*A105284(n-1).
a(2*n+1) = 6*a(2*n) - 8*a(2*n-1).
a(4*n) = 6*a(4*n-1) - 8*a(4*n-2) - a(n).
a(4*n+2) = 6*a(4*n+1) - 8*a(4*n) - 2*a(n).

cp's OEIS Frontend

A342517 Number of strict integer partitions of n with strictly increasing first quotients.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A342518 Number of strict integer partitions of n with strictly decreasing first quotients.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A155092 Matrix inverse of A155091.

Views

Author

Keywords

Comments

Examples

Crossrefs

A242430 Decimal expansion of the unforgeable pattern-free binary word constant, a constant mentioned in A003000.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Mathematica

A105284 a(n)/4^n is the measure of the subset of [0,1] remaining when all intervals of the form [b/2^m - 1/2^(2m+1), b/2^m + 1/2^(2m+1)] have been removed, with b and m positive integers, b<2^m and m<=n.

Views

Author

Keywords

Comments

Examples

Formula

A331392 Sum, over all binary strings w of length n, of the length of the shortest border of w.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A361942 For any number n >= 0 with binary expansion (b_1, ..., b_w), a(n) is the least p > 0 such that b_i = b_{p+i} for i = 1..w-p.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

A107284 a(n)/4^n is the measure of the subset of [0,1] remaining when all intervals of the form [b/2^m - 1/2^(2m), b/2^m + 1/2^(2m)] have been removed, with b and m positive integers, b < 2^m and m <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula