A005667 -id:A005667 - cp's OEIS frontend

A005670 Mrs. Perkins's quilt: smallest coprime dissection of n X n square.

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

Offset: 1

N. J. A. Sloane

The problem is to dissect an n X n square into smaller integer squares, the GCD of whose sides is 1, using the smallest number of squares. The GCD condition excludes dissecting a 6 X 6 into four 3 X 3 squares.
The name "Mrs Perkins's Quilt" comes from a problem in one of Dudeney's books, wherein he gives the answer for n = 13. I gave the answers for low n and an upper bound of order n^(1/3) for general n, which Trustrum improved to order log(n). There's an obvious logarithmic lower bound. - J. H. Conway, Oct 11 2003
All entries shown are known to be correct - see Wynn, 2013. - N. J. A. Sloane, Nov 29 2013

			Illustrating a(7) = 9: a dissection of a 7 X 7 square into 9 pieces, courtesy of _Ed Pegg Jr_:
.___.___.___.___.___.___.___
|...........|.......|.......|
|...........|.......|.......|
|...........|.......|.......|
|...........|___.___|___.___|
|...........|...|...|.......|
|___.___.___|___|___|.......|
|...............|...|.......|
|...............|___|___.___|
|...............|...........|
|...............|...........|
|...............|...........|
|...............|...........|
|...............|...........|
|___.___.___.___|___.___.___|
The Duijvestijn code for this is {{3,2,2},{1,1,2},{4,1},{3}}
Solutions for n = 1..10: 1 {{1}}
2 {{1, 1}, {1, 1}}
3 {{2, 1}, {1}, {1, 1, 1}}
4 {{2, 2}, {2, 1, 1}, {1, 1}}
5 {{3, 2}, {1, 1}, {2, 1, 2}, {1}}
6 {{3, 3}, {3, 2, 1}, {1}, {1, 1, 1}}
7 {{4, 3}, {1, 2}, {3, 1, 1}, {2, 2}}
8 {{4, 4}, {4, 2, 2}, {2, 1, 1}, {1, 1}}
9 {{5, 4}, {1, 1, 2}, {4, 2, 1}, {3}, {2}}
10 {{5, 5}, {5, 3, 2}, {1, 1}, {2, 1, 2}, {1}}

H. T. Croft, K. J. Falconer and R. K. Guy, Unsolved Problems in Geometry, C3.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Ed Wynn, Table of n, a(n) for n = 1..120
J. H. Conway, Mrs. Perkins's quilt, Proc. Camb. Phil. Soc., 60 (1964), 363-368.
A. J. W. Duijvestijn, Table I
A. J. W. Duijvestijn, Table II
R. K. Guy, Letter to N. J. A. Sloane, 1987
Ed Pegg, Jr., Mrs Perkins's Quilts (best known values to 40000)
G. B. Trustrum, Mrs Perkins's quilt, Proc. Cambridge Philos. Soc., 61 1965 7-11.
Eric Weisstein's World of Mathematics, Mrs. Perkins's Quilt
Ed Wynn, Exhaustive generation of 'Mrs Perkins's quilt' square dissections for low orders, arXiv:1308.5420 [math.CO], 2013-2014.
Ed Wynn, Exhaustive generation of 'Mrs. Perkins's quilt' square dissections for low orders, Discrete Math. 334 (2014), 38--47. MR3240464

Cf. A005842, A089046, A089047.

b-file from Wynn 2013, added by N. J. A. Sloane, Nov 29 2013

A041008 Numerators of continued fraction convergents to sqrt(7).

Original entry on oeis.org

2, 3, 5, 8, 37, 45, 82, 127, 590, 717, 1307, 2024, 9403, 11427, 20830, 32257, 149858, 182115, 331973, 514088, 2388325, 2902413, 5290738, 8193151, 38063342, 46256493, 84319835, 130576328, 606625147, 737201475, 1343826622, 2081028097, 9667939010, 11748967107, 21416906117

Offset: 0

N. J. A. Sloane

Vincenzo Librandi, Table of n, a(n) for n = 0..200
C. Elsner, Series of Error Terms for Rational Approximations of Irrational Numbers, J. Int. Seq. 14 (2011) # 11.1.4.
C. Elsner, M. Stein, On Error Sum Functions Formed by Convergents of Real Numbers, J. Int. Seq. 14 (2011) # 11.8.6.
Index entries for linear recurrences with constant coefficients, signature (0,0,0,16,0,0,0,-1).

Cf. A010465, A041009 (denominators), A266698 (quadrisection), A001081 (quadrisection).

Analog for other sqrt(m): A001333 (m=2), A002531 (m=3), A001077 (m=5), A041006 (m=6), A041010 (m=8), A005667 (m=10), A041014 (m=11), A041016 (m=12), ..., A042934 (m=999), A042936 (m=1000).

Table[Numerator[FromContinuedFraction[ContinuedFraction[Sqrt[7],n]]],{n,1,50}] (* Vladimir Joseph Stephan Orlovsky, Mar 16 2011 *)
Numerator[Convergents[Sqrt[7], 30]] (* Vincenzo Librandi, Oct 28 2013 *)
LinearRecurrence[{0,0,0,16,0,0,0,-1},{2,3,5,8,37,45,82,127},40] (* Harvey P. Dale, Jul 23 2021 *)

A041008=contfracpnqn(c=contfrac(sqrt(7)),#c)[1,][^-1] \\ Discard possibly incorrect last element. NB: a(n)=A041008[n+1]! For more terms use:
A041008(n)={n<#A041008|| A041008=extend(A041008, [4, 16; 8, -1], n\.8); A041008[n+1]}
extend(A,c,N)={for(n=#A+1, #A=Vec(A, N), A[n]=[A[n-i]|i<-c[,1]]*c[,2]); A} \\ (End)

G.f.: (2 + 3*x + 5*x^2 + 8*x^3 + 5*x^4 - 3*x^5 + 2*x^6 - x^7)/(1 - 16*x^4 + x^8).

A041014 Numerators of continued fraction convergents to sqrt(11).

Original entry on oeis.org

3, 10, 63, 199, 1257, 3970, 25077, 79201, 500283, 1580050, 9980583, 31521799, 199111377, 628855930, 3972246957, 12545596801, 79245827763, 250283080090, 1580944308303, 4993116004999, 31539640338297

Offset: 0

N. J. A. Sloane

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Index entries for linear recurrences with constant coefficients, signature (0,20,0,-1).

Cf. A010468, A041015 (denominators).

Analog for other sqrt(m): A001333 (m=2), A002531 (m=3), A001077 (m=5), A041006 (m=6), A041008 (m=7), A041010 (m=8), A005667 (m=10), A041016 (m=12), ..., A042936 (m=1000).

Table[Numerator[FromContinuedFraction[ContinuedFraction[Sqrt[11],n]]],{n,1,50}] (* Vladimir Joseph Stephan Orlovsky, Mar 16 2011 *)
Numerator[Convergents[Sqrt[11], 30]] (* Vincenzo Librandi, Oct 28 2013 *)

A041014=contfracpnqn(c=contfrac(sqrt(11)), #c)[1,][^-1] \\ Discard last element which may be incorrect. Use e.g. \p999 to get more terms, or extend as follows:
{A041014_upto(N,A=Vec(A041014,N))=for(n=#A041014+1,N, A[n]=20*A[n-2]-A[n-4]); A041014=A} \\ M. F. Hasler, Nov 01 2019

G.f.: (3 + 10*x + 3*x^2 - x^3)/(1 - 20*x^2 + x^4).

A042936 Numerators of continued fraction convergents to sqrt(1000).

Original entry on oeis.org

31, 32, 63, 95, 158, 253, 1676, 3605, 8886, 136895, 282676, 702247, 4496158, 5198405, 9694563, 14892968, 24587531, 39480499, 2472378469, 2511858968, 4984237437, 7496096405, 12480333842, 19976430247, 132338915324, 284654260895, 701647437114, 10809365817605, 22320379072324

Offset: 0

N. J. A. Sloane

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Index entries for linear recurrences with constant coefficients, signature (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 78960998, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1).

Cf. A042937 (denominators).

Analog for sqrt(m): A001333 (m=2), A002531 (m=3), A001077 (m=5), A041006 (m=6), A041008 (m=7), A041010 (m=8), A005667 (m=10), A041014 (m=11), ..., A042934 (m=999).

Numerator[Convergents[Sqrt[1000], 30]] (* Harvey P. Dale, Oct 29 2013 *)

A42936=contfracpnqn(c=contfrac(sqrt(1000)), #c)[1,][^-1] \\ Discards possibly incorrect last term. NB: a(n)=A42936[n+1]. Could be extended using: {A42936=concat(A42936, 78960998*A42936[-18..-1]-A42936[-36..-19])}
\\ But terms with arbitrarily large indices can be computed using:
A042936(n)={[A42936[n%18+i]|i<-[1, 19]]*([0, -1; 1, 78960998]^(n\18))[,1]} \\ Faster but longer with n=divrem(n,18). (End)

A041010 Numerators of continued fraction convergents to sqrt(8).

Original entry on oeis.org

2, 3, 14, 17, 82, 99, 478, 577, 2786, 3363, 16238, 19601, 94642, 114243, 551614, 665857, 3215042, 3880899, 18738638, 22619537, 109216786, 131836323, 636562078, 768398401, 3710155682, 4478554083, 21624372014, 26102926097, 126036076402, 152139002499

Offset: 0

N. J. A. Sloane

Vincenzo Librandi, Table of n, a(n) for n = 0..199 [1 removed by _Georg Fischer_, Jul 01 2019]
Index entries for linear recurrences with constant coefficients, signature (0,6,0,-1).

Cf. A040005 (continued fraction), A041011 (denominators), A010466 (decimals).

Analog for other sqrt(m): A001333 (m=2), A002531 (m=3), A001077 (m=5), A041006 (m=6), A041008 (m=7), A005667 (m=10), A041014 (m=11), A041016 (m=12), ..., A042934 (m=999), A042936 (m=1000).

Table[Numerator[FromContinuedFraction[ContinuedFraction[Sqrt[8],n]]],{n,1,50}] (* Vladimir Joseph Stephan Orlovsky, Mar 16 2011*)
CoefficientList[Series[(2 + 3*x + 2*x^2 - x^3)/(1 - 6*x^2 + x^4), {x, 0, 30}], x]  (* Vincenzo Librandi, Oct 28 2013 *)
a0[n_] := -((3-2*Sqrt[2])^n*(1+Sqrt[2]))+(-1+Sqrt[2])*(3+2*Sqrt[2])^n // Simplify
a1[n_] := ((3-2*Sqrt[2])^n+(3+2*Sqrt[2])^n)/2 // Simplify
Flatten[MapIndexed[{a0[#], a1[#]} &,Range[20]]] (* Gerry Martens, Jul 11 2015 *)

A041010=contfracpnqn(c=contfrac(sqrt(8)),#c)[1,][^-1] \\ Discard possibly incorrect last element. NB: a(n)=A041010[n+1]! For more terms use:
A041010(n)={n<#A041010|| A041010=extend(A041010, [-1,0,6,0]~, n\.8); A041010[n+1]}
extend(A,c,N)={for(n=#A+1,#A=Vec(A,N), A[n]=A[n-#c..n-1]*c);A} \\ (End)

a(n) = 6*a(n-2) - a(n-4).
a(2n) = a(2n-1) + a(2n-2), a(2n+1) = 4*a(2n) + a(2n-1).
a(2n) = A001333(2n), a(2n+1) = 2*A001333(2n+1).
G.f.: (2+3*x+2*x^2-x^3)/(1-6*x^2+x^4).
a(n) = A001333(n+1)*A000034(n+1). - R. J. Mathar, Jul 08 2009
From Gerry Martens, Jul 11 2015: (Start)
Interspersion of 2 sequences [a0(n),a1(n)] for n>0:
a0(n) = -((3-2*sqrt(2))^n*(1+sqrt(2))) + (-1+sqrt(2))*(3+2*sqrt(2))^n.
a1(n) = ((3-2*sqrt(2))^n + (3+2*sqrt(2))^n)/2. (End)

Entry improved by Michael Somos
Initial term 1 removed and b-file, program and formulas adapted by Georg Fischer, Jul 01 2019
Cross-references added by M. F. Hasler, Nov 02 2019

A042934 Numerators of continued fraction convergents to sqrt(999).

Original entry on oeis.org

31, 32, 63, 95, 158, 885, 5468, 6353, 37233, 80819, 441328, 522147, 3574210, 18393197, 21967407, 40360604, 62328011, 102688615, 6429022141, 6531710756, 12960732897, 19492443653, 32453176550

Offset: 0

N. J. A. Sloane

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Index entries for linear recurrences with constant coefficients, signature (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 205377230, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1).

Cf. A042935 (denominators).

Analog for other sqrt(m): A001333 (m=2), A002531 (m=3), A001077 (m=5), A041006 (m=6), A041008 (m=7), A041010 (m=8), A005667 (m=10), A041014 (m=11), ..., A042936 (m=1000).

Numerator[Convergents[Sqrt[999], 30]] (* Vincenzo Librandi, Dec 10 2013 *)

A42934=contfracpnqn(c=contfrac(sqrt(999)), #c)[1,][^-1] \\ Discard possibly incorrect last element. NB: a(n) = A42934[n+1]! For more terms, use:
A042934(n)={n<#A42934 || A42934_upto(n+10); A42934[n+1]}
{A42934_upto(N,A=Vec(A42934,N))=for(n=#A42934+1,N, A[n]=205377230*A[n-18]-A[n-36]); A42934=A} \\ M. F. Hasler, Nov 01 2019

a(n) = 205377230*a(n-18) - a(n-36). - Wesley Ivan Hurt, May 28 2021

A084132 a(n) = 4a(n-1) + 6a(n-2), a(0)=1, a(1)=2.

Original entry on oeis.org

1, 2, 14, 68, 356, 1832, 9464, 48848, 252176, 1301792, 6720224, 34691648, 179087936, 924501632, 4772534144, 24637146368, 127183790336, 656558039552, 3389334900224, 17496687838208, 90322760754176, 466271170045952

Offset: 0

Paul Barry, May 16 2003

Binomial transform of A002535.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (4,6).

Cf. A002535, A005667, A201730.

[n le 2 select 2^(n-1) else 4*Self(n-1) +6*Self(n-2): n in [1..40]]; // G. C. Greubel, Oct 13 2022

LinearRecurrence[{4,6}, {1,2}, 40] (* G. C. Greubel, Oct 13 2022 *)

[lucas_number2(n,4,-6)/2 for n in range(0, 22)] # Zerinvary Lajos, May 14 2009

A084132=BinaryRecurrenceSequence(4,6,1,2)
[A084132(n) for n in range(41)] # G. C. Greubel, Oct 13 2022

a(n) = (2+sqrt(10))^n/2 + (2-sqrt(10))^n/2.
G.f.: (1-2*x)/(1-4*x-6*x^2).
E.g.f.: exp(2*x)*cosh(sqrt(10)*x).
a(n) = Sum_{k=0..n} A201730(n,k)*9^k. - Philippe Deléham, Dec 06 2011
G.f.: G(0)/2, where G(k) = 1 + 1/(1 - x*(5*k-2)/(x*(5*k+3) - 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 03 2013
a(n) = 2*i^n*6^((n-2)/2)*( 3*ChebyshevU(n, 2/(i*sqrt(6))) + i*sqrt(6)*ChebyshevU(n -1, 2/(i*sqrt(6))) ). - G. C. Greubel, Oct 13 2022

A084134 a(n) = 8a(n-1) - 6a(n-2), a(0) = 1, a(1) = 4.

Original entry on oeis.org

1, 4, 26, 184, 1316, 9424, 67496, 483424, 3462416, 24798784, 177615776, 1272133504, 9111373376, 65258185984, 467397247616, 3347628865024, 23976647434496, 171727406285824, 1229959365679616, 8809310487721984

Offset: 0

Paul Barry, May 16 2003

Binomial transform of A005667.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (8,-6).

Cf. A005667, A084135.

[n le 2 select 4^(n-1) else 8*Self(n-1) -6*Self(n-2): n in [1..40]]; // G. C. Greubel, Oct 13 2022

LinearRecurrence[{8,-6},{1,4},30] (* Harvey P. Dale, Nov 30 2011 *)

A084134=BinaryRecurrenceSequence(8,-6,1,4)
[A084134(n) for n in range(41)] # G. C. Greubel, Oct 13 2022

a(n) = (4+sqrt(10))^n/2 + (4-sqrt(10))^n/2.
G.f.: (1-4*x)/(1 - 8*x + 6*x^2).
E.g.f.: exp(4*x)*cosh(sqrt(10)*x).

A129557 Numbers k > 0 such that k^2 is a centered pentagonal number (A005891).

Original entry on oeis.org

1, 4, 34, 151, 1291, 5734, 49024, 217741, 1861621, 8268424, 70692574, 313982371, 2684456191, 11923061674, 101938642684, 452762361241, 3870983965801, 17193046665484, 146995452057754, 652883010927151, 5581956194228851, 24792361368566254

Offset: 1

Alexander Adamchuk, Apr 20 2007

Corresponding numbers m such that centered pentagonal number A005891(m) = (5*m^2 + 5*m + 2)/2 is a perfect square are listed in A129556 = {0, 2, 21, 95, 816, 3626, 31005, ...}.

Also positive integers x in the solutions to 2*x^2 - 5*y^2 + 5*y - 2 = 0, the corresponding values of y being A254332. - Colin Barker, Jan 28 2015

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Centered Pentagonal Number.
Index entries for linear recurrences with constant coefficients, signature (0,38,0,-1).

Cf. A005891 (centered pentagonal numbers).
Cf. A129556 (k such that A005891(k) is a perfect square).
Cf. A000290, A005667, A254332, A254333.

Do[ f=(5n^2+5n+2)/2; If[ IntegerQ[ Sqrt[f] ], Print[ Sqrt[f] ] ], {n,1,40000} ]
CoefficientList[Series[(1-x)*(1+5*x+x^2)/((1+6*x-x^2)*(1-6*x-x^2)),{x,0,30}],x] (* Vincenzo Librandi, Apr 11 2012 *)

A129557()={ for(n=1,1000000000, f=(5*n^2+5*n+2)/2 ; if(issquare(f), print1(sqrtint(f), ", ") ; ); ) ; } \\ R. J. Mathar, Oct 11 2007

Vec(x*(1-x)*(1+5*x+x^2)/((1+6*x-x^2)*(1-6*x-x^2)) + O(x^100)) \\ Colin Barker, Jan 28 2015

a(n) = sqrt( (5*A129556(n)^2 + 5*A129556(n) + 2)/2 ).
For n >= 5, a(n) = 38*a(n-2) - a(n-4). - Max Alekseyev, May 08 2009
G.f.: x*(1-x)*(1 + 5*x + x^2)/((1 + 6*x - x^2)*(1 - 6*x - x^2)). - Colin Barker, Apr 11 2012
From Andrea Pinos, Oct 07 2022: (Start)
The ratios of successive terms converge to two different limits:
  lower: D = lim_{n->oo} a(2n)/a(2n-1) = (7 + 2*sqrt(10))/3;
  upper: E = lim_{n->oo} a(2n+1)/a(2n) = (13 + 4*sqrt(10))/3.
So lim_{n->oo} a(n+2)/a(n) = D*E = 19 + 6*sqrt(10).
a(n) = (A005667(n) - (-1)^n*A005667(n-1))/4. (End)

More terms from R. J. Mathar, Oct 11 2007

More terms from Max Alekseyev, May 08 2009

A005674 a(n) = 2^(n-1) + 2^[ n/2 ] + 2^[ (n-1)/2 ] - F(n+3).

Original entry on oeis.org

0, 0, 0, 0, 1, 3, 10, 25, 63, 144, 327, 711, 1534, 3237, 6787, 14056, 28971, 59283, 120894, 245457, 497167, 1004256, 2025199, 4077007, 8198334, 16467597, 33052491, 66293208

Offset: 0

N. J. A. Sloane

a(n) is the number of compositions of n where mixing of even and odd summands occurs. That is, at least one even summand is bracketed by two odd summands, or vice versa. - Gregory L. Simay, Jul 27 2016

			a(6) = a(2*3) = 2^5 - f(9) + 3*2^2 = 32 - 34 + 12 = 10. The 10 compositions are (1,4,1), (3,2,1), (1,2,3), (2,1,2,1), (1,2,1,2), (2,1,1,2), (1,2,2,1), (1,2,1,1,1), (1,1,2,1,1), (1,1,1,2,1).

R. K. Guy, personal communication.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. K. Guy, Letter to N. J. A. Sloane, 1987
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992

Cf. A079289, A027558 divided by 2.

A005674:=-z**4/(2*z-1)/(z**2+z-1)/(-1+2*z**2); # [Conjectured by Simon Plouffe in his 1992 dissertation.]

From Gregory L. Simay, Jul 27 2016: (Start)
If n=2k, then a(n) = 2^(n-1) - 2*A079289(n) + 2^(n/2 - 1) + F(n).
If n=2k-1, then a(n) = 2^(n-1) - 2*A079289(n) + F(n). (End)

cp's OEIS Frontend

A005670 Mrs. Perkins's quilt: smallest coprime dissection of n X n square.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A041008 Numerators of continued fraction convergents to sqrt(7).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A041014 Numerators of continued fraction convergents to sqrt(11).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A042936 Numerators of continued fraction convergents to sqrt(1000).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A041010 Numerators of continued fraction convergents to sqrt(8).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A042934 Numerators of continued fraction convergents to sqrt(999).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A084132 a(n) = 4*a(n-1) + 6*a(n-2), a(0)=1, a(1)=2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

SageMath

Formula

A084134 a(n) = 8*a(n-1) - 6*a(n-2), a(0) = 1, a(1) = 4.

Views

Author

Keywords

Comments

Links

A084132 a(n) = 4a(n-1) + 6a(n-2), a(0)=1, a(1)=2.

A084134 a(n) = 8a(n-1) - 6a(n-2), a(0) = 1, a(1) = 4.