Frank Ruskey - cp's OEIS frontend

A227145 Numbers satisfying an infinite nested recurrence relation.

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

Offset: 1

Frank Ruskey, Jul 04 2013

nonn

Conjecture: a(F_n) = F_{n-2} for n>1, where F_n is the n-th Fibonacci number.

Conjecture: a(n) ~ n*(3-sqrt(5))/2. -Jeffrey Shallit, Oct 12 2022

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Marcel Celaya and Frank Ruskey, Morphic words and nested recurrence relations, arxiv 1307.0153 (Jun 29 2013), [math.CO] (see page 11).

Cf. A060144.

a:= proc(n) option remember; local i, r, s;
      if n<2 then 0 else r, s:= n, 1;
         for i while s>0 do r, s:= r-s, (a@@i)(n-i) od: r
      fi
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Jul 04 2013

a[n_] := a[n]= Which[n <= 1, 0,True, n - 1 -Sum[Nest[a, n - i, i], {i,1,n}]]; Table[a[i], {i, 0, 30}] (* José María Grau Ribas, Jul 10 2013 *)

a(n) = n - 1 - a(n-1) - a(a(n-2)) - a(a(a(n-3))) - a(a(a(a(n-4)))) - ... with a(n) = 0 if n <= 1.

A217196 Integers expressible in at least two ways as a^3 + b^4, where a,b > 0.

Original entry on oeis.org

4097, 10729, 15641, 175625, 195193, 408536, 531442, 535537, 549017, 831209, 852984, 883664, 1778625, 3185784, 4258089, 5555233, 8876304, 11338448, 11402289, 12721424, 13844736, 16777217, 16781312, 17182440, 17308657, 19169848, 19703736, 22667633, 26248698

Offset: 1

Frank Ruskey, Sep 27 2012

nonn

Numbers are listed in increasing order, no duplicates allowed (i.e., if the number is so expressible in 3 or more ways).

a(n) >> n^(12/7) by a counting argument. Can this be improved? Is there a corresponding upper bound? - Charles R Greathouse IV, Sep 27 2012

			a(1) = 4097 = 1^3 + 8^4 = 16^3 + 1^4 is the smallest such number.

Frank Ruskey, Table of n, a(n) for n = 1..5000

A192103 Number of distinct (unordered) pairs of partitions of a 10-element set that have Rand distance n.

Original entry on oeis.org

186300, 887220, 3060360, 9883440, 26969040, 67288830, 141778440, 256463820, 399874640, 547907454, 670419540, 742419510, 744780330, 701747010, 607809750, 520591950, 377521875, 312082260, 198307620, 158606532, 87210930, 63688410, 33243120, 25703205, 11343906, 6764940, 3272500, 2003805, 1532340, 757080, 211410, 212625, 198345, 138600, 82512, 21080, 16200, 15750, 14910, 13545, 7245, 3270, 630, 45, 1

Offset: 1

Frank Ruskey and Yuji Yamauchi (eugene.uti(AT)gmail.com), Aug 08 2011

The Rand distance of a pair of set partitions is the number of unordered pairs {x; y} such that there is a block in one partition containing both x and y, but x and y are in different blocks in the other partition.

F. Ruskey and J. Woodcock, The Rand and block distances of pairs of set partitions, Combinatorial algorithms, 287-299, Lecture Notes in Comput. Sci., 7056, Springer, Heidelberg, 2011.

Cf. A192100 for set sizes 2..7. A192098 and A192102 for set sizes 8 and 9.

A192105 Number of distinct (unordered) pairs of partitions of a 12-element set that have Rand distance n.

Original entry on oeis.org

7654350, 40209840, 156637140, 576841320, 1851589872, 5544758076, 14686598520, 35723706480, 75818872580, 144536922420, 242305860072, 370664737190, 506699655660, 643405035240, 746030515164, 812426918688, 833352979140, 795923308950, 741556189440, 644098507272, 547387431756, 444670121610, 349922192400, 268690544925, 197063378424, 147497181678, 99290917440, 73672276095, 45746253960, 32550841950, 19313040780

Offset: 1

Frank Ruskey and Yuji Yamauchi (eugene.uti(AT)gmail.com), Aug 08 2011

The Rand distance of a pair of set partitions is the number of unordered pairs {x; y} such that there is a block in one partition containing both x and y, but x and y are in different blocks in the other partition.

F. Ruskey and J. Woodcock, The Rand and block distances of pairs of set partitions, Combinatorial algorithms, 287-299, Lecture Notes in Comput. Sci., 7056, Springer, Heidelberg, 2011.

Cf. A192100 for set sizes 2..7. A192098 and A192102-A192104 for set sizes 8..11.

A192104 Number of distinct (unordered) pairs of partitions of an 11-element set that have Rand distance n.

Original entry on oeis.org

1163085, 5835060, 21482340, 74471760, 222185304, 612903720, 1469224350, 3164268690, 5762811670, 9538994388, 13513772745, 18112131840, 20675910420, 23653643310, 22677991578, 22923998460, 19287053775, 17554312490, 13495597225, 11143736604, 8029798920, 6035010960, 4254456690, 2872892550, 1924619235, 1215058680, 789847190

Offset: 1

Frank Ruskey and Yuji Yamauchi (eugene.uti(AT)gmail.com), Aug 08 2011

The Rand distance of a pair of set partitions is the number of unordered pairs {x; y} such that there is a block in one partition containing both x and y, but x and y are in different blocks in the other partition.

F. Ruskey and J. Woodcock, The Rand and block distances of pairs of set partitions, Combinatorial algorithms, 287-299, Lecture Notes in Comput. Sci., 7056, Springer, Heidelberg, 2011.

Cf. A192100 for set sizes 2..7. A192098, A192102 and A192103 for set sizes 8..10.

A192102 Number of distinct (unordered) pairs of partitions of a 9-element set that have Rand distance n.

Original entry on oeis.org

31572, 141624, 452508, 1341648, 3266172, 7234374, 12259368, 18992502, 23324140, 28129626, 26605908, 26190612, 21568932, 17119818, 13040280, 8948079, 6244308, 3679032, 2431044, 1250109, 640908, 315828, 197568, 57288, 46116, 30366, 25732, 7695, 4104, 2226, 3780, 2205, 1344, 378, 36, 1

Offset: 1

Frank Ruskey and Yuji Yamauchi (eugene.uti(AT)gmail.com), Aug 08 2011

The Rand distance of a pair of set partitions is the number of unordered pairs {x; y} such that there is a block in one partition containing both x and y, but x and y are in different blocks in the other partition.

F. Ruskey and J. Woodcock, The Rand and block distances of pairs of set partitions, Combinatorial algorithms, 287-299, Lecture Notes in Comput. Sci., 7056, Springer, Heidelberg, 2011.

Cf. A192100 for set sizes 2..7. A192098 for set size 8.

A192098 Number of distinct (unordered) pairs of partitions of an 8-element set that have Rand distance n.

Original entry on oeis.org

5684, 23772, 69272, 183960, 391356, 696178, 941088, 1182888, 1150520, 1165416, 815640, 780570, 413840, 369180, 178080, 115780, 43512, 20734, 6860, 7098, 3508, 574, 840, 665, 476, 210, 28, 1

Offset: 1

Frank Ruskey and Yuji Yamauchi (eugene.uti(AT)gmail.com), Jul 21 2011

The Rand distance of a pair of set partitions is the number of unordered pairs {x; y} such that there is a block in one partition containing both x and y, but x and y are in different blocks in the other partition.

F. Ruskey and J. Woodcock, The Rand and block distances of pairs of set partitions, Combinatorial algorithms, 287-299, Lecture Notes in Comput. Sci., 7056, Springer, Heidelberg, 2011.

Cf. A192100 for set sizes 2..7.

A192097 Number of tatami tilings of an n X n square region with n monomers and floor(n * (n - 1) / 4) horizontal dimers.

Original entry on oeis.org

1, 1, 2, 4, 8, 8, 16, 28, 40, 80, 144, 252, 456, 840

Offset: 0

Frank Ruskey and Yuji Yamauchi (eugene.uti(AT)gmail.com), Jul 15 2011

A tatami tiling consists of dimers (1 X 2) and monomers (1 X 1) where no four meet at a point.
There are at most n * (n - 1) / 2 horizontal dimers in any tiling of an n X n square with n monomers.
If there are floor(n * (n - 1) / 4) horizontal dimers, the numbers of horizontal dimers and vertical dimers differ by at most one.

A. Erickson, F. Ruskey, M. Schurch and J. Woodcock, Monomer-Dimer Tatami Tilings of Rectangular Regions, Electronic Journal of Combinatorics, 18(1) (2011) P109, 24 pages.

Cf. A192095.

A192101 Least number requiring n terms to express it as a sum of signed terms of the form 2^k-1.

Original entry on oeis.org

1, 2, 5, 20, 83, 594, 2641, 10856, 43623, 305766, 1354341, 5548644, 22325859, 89434722, 357870241, 1431612752, 5726580047

Offset: 1

Frank Ruskey, Jul 29 2011

a(n) = min{ i : A192099(i) = n }

Conjecture: a(n) = (4^n)/3 + O(1).

			The smallest value of i for which A192099(i) = 5 is 83 = 31+15+7-3+1, and so a(5) = 83.

Isoperimetric sequences for infinite complete binary trees and their relation to meta-Fibonacci sequences and signed almost binary partitions, talk at CANADAM, 2009.

Cf. A192099.

A192099 Least number of parts in a partition of n into signed terms of the form 2^k-1.

Original entry on oeis.org

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

Offset: 1

Frank Ruskey and Yuji Yamauchi (eugene.uti(AT)gmail.com), Jul 28 2011

nonn

Another interpretation: Let T be the infinite binary tree with all leaves at the same level. Then a(n) is the least number of edges in any cut (X,Y) where |X| = n.

			a(43) = 3 since 43 = 31+15-3 and there is no way to write 43 using fewer terms of the form 2^k-1.
The smallest value of n for which a(n) = 5 is 83 = 31+15+7-3+1.

G. C. Greubel, Table of n, a(n) for n = 1..10000
Frank Ruskey, Sunil Chandran, and Anita Das, Isoperimetric sequences for infinite complete binary trees and their relation to meta-Fibonacci sequences and signed almost binary partitions, talk at CANADAM, 2009.

a[n_]:= If[n < 2, Boole[n == 1], With[{m = IntegerLength[ n, 2] - 1}, a[n] = 1 + Min[ a[n - (2^m - 1)], a[(2^(m + 1) - 1) - n]]]] (* Michael Somos, Jul 28 2011 *)

a(n)={ local(d); if ( n<=1, return(n) ); d = #binary(n)-1; return(1 + min( a(n-(2^d-1)), a((2^(d+1)-1)-n)) ); }

Let d(n) = floor(log(n)/log(2)). Then a(n) = 1 + min{ a(n-(2^d(n)-1)), a((2^(d(n)+1)-1)-n) } with a(0)=0 and a(1)=1.

cp's OEIS Frontend

User: Frank Ruskey

A227145 Numbers satisfying an infinite nested recurrence relation.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A217196 Integers expressible in at least two ways as a^3 + b^4, where a,b > 0.

Views

Author

Keywords

Comments

Examples

Links

A192103 Number of distinct (unordered) pairs of partitions of a 10-element set that have Rand distance n.

Views

Author

Keywords

Comments

Links

Crossrefs

A192105 Number of distinct (unordered) pairs of partitions of a 12-element set that have Rand distance n.

Views

Author

Keywords

Comments

Links

Crossrefs

A192104 Number of distinct (unordered) pairs of partitions of an 11-element set that have Rand distance n.

Views

Author

Keywords

Comments

Links

Crossrefs

A192102 Number of distinct (unordered) pairs of partitions of a 9-element set that have Rand distance n.

Views

Author

Keywords

Comments

Links

Crossrefs

A192098 Number of distinct (unordered) pairs of partitions of an 8-element set that have Rand distance n.

Views

Author

Keywords

Comments

Links

Crossrefs

A192097 Number of tatami tilings of an n X n square region with n monomers and floor(n * (n - 1) / 4) horizontal dimers.

Views

Author

Keywords

Comments

Links

Crossrefs

A192101 Least number requiring n terms to express it as a sum of signed terms of the form 2^k-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A192099 Least number of parts in a partition of n into signed terms of the form 2^k-1.

Views

Author

Keywords

Comments

Examples

Links

Programs

Mathematica

PARI