cp's OEIS Frontend

A274230 Number of holes in a sheet of paper when you fold it n times and cut off the four corners.

%I A274230 #151 Feb 16 2024 10:22:29
%S A274230 0,0,1,3,9,21,49,105,225,465,961,1953,3969,8001,16129,32385,65025,
%T A274230 130305,261121,522753,1046529,2094081,4190209,8382465,16769025,
%U A274230 33542145,67092481,134193153,268402689,536821761,1073676289,2147385345
%N A274230 Number of holes in a sheet of paper when you fold it n times and cut off the four corners.
%C A274230 The folds are always made so the longer side becomes the shorter side.
%C A274230 We could have counted not only the holes but also all the notches: 4, 6, 9, 15, 25, 45, 81, 153, 289, ... which has the formula a(n) = (2^ceiling(n/2) + 1) * (2^floor(n/2) + 1) and appears to match the sequence A183978. - _Philippe Gibone_, Jul 06 2016
%C A274230 The same sequence (0,0,1,3,9,21,49,...) turns up when you start with an isosceles right triangular piece of paper and repeatedly fold it in half, snipping corners as you go. Is there an easy way to see why the two questions have the same answer? - _James Propp_, Jul 05 2016
%C A274230 Reply from _Tom Karzes_, Jul 05 2016: (Start)
%C A274230 This case seems a little more complicated than the rectangular case, since with the triangle you alternate between horizontal/vertical folds vs. diagonal folds, and the resulting fold pattern is more complex, but I think the basic argument is essentially the same.
%C A274230 Note that with the triangle, the first hole doesn't appear until after you've made 3 folds, so if you start counting at zero folds, you have three leading zeros in the sequence: 0,0,0,1,3,9,21,... (End)
%C A274230 Also the number of subsets of {1,2,...,n} that contain both even and odd numbers. For example, a(3)=3 and the 3 subsets are {1,2}, {2,3}, {1,2,3}; a(4)=9 and the 9 subsets are {1,2}, {1,4}, {2,3}, {3,4}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}, {1,2,3,4}. (See comments in A052551 for the number of subsets of {1,2,...,n} that contain only odd and even numbers.) - _Enrique Navarrete_, Mar 26 2018
%C A274230 Also the number of integer compositions of n + 1 with an odd part other than the first or last. The complementary compositions are counted by A052955(n>0) = A027383(n) + 1. - _Gus Wiseman_, Feb 05 2022
%C A274230 Also the number of unit squares in the (n+1)-st iteration in the version of the dragon curve where the rotation directions alternate, so that any clockwise rotation is followed by a counterclockwise rotation, and vice versa (see image link below). - _Talmon Silver_, May 09 2023
%H A274230 Paolo P. Lava, <a href="/A274230/b274230.txt">Table of n, a(n) for n = 0..1000</a>
%H A274230 Philippe Gibone, <a href="/A274230/a274230.pdf">Illustration of a(0)-a(4) (idealized)</a>.
%H A274230 Talmon Silver, <a href="/A274230/a274230.png">Illustration of alternating dragon</a>.
%H A274230 N. J. A. Sloane, <a href="/A274230/a274230.jpg">Illustration for a(4) = 9 (scan of an actual cut-up piece of paper)</a>
%H A274230 N. J. A. Sloane, <a href="/A274230/a274230_1.jpg">Illustration for a(5) = 21 (scan of an actual cut-up piece of paper)</a>
%H A274230 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (3,0,-6,4).
%F A274230 u(0) = 0; v(0) = 0; u(n+1) = v(n); v(n+1) = 2u(n) + 1; a(n) = u(n)*v(n).
%F A274230 a(n) = (2^ceiling(n/2) - 1)*(2^floor(n/2) - 1).
%F A274230 Proof from _Tom Karzes_, Jul 05 2016: (Start)
%F A274230 Let r be the number of times you fold along one axis and s be the number of times you fold along the other axis. So r is ceiling(n/2) and s is floor(n/2), where n is the total number of folds.
%F A274230 When unfolded, the resulting paper has been divided into a grid of (2^r) by (2^s) rectangles. The interior grid lines will have diamond-shaped holes where they intersect (assuming diagonal cuts).
%F A274230 There are (2^r-1) internal grid lines along one axis and (2^s-1) along the other. The total number of internal grid line intersections is therefore (2^r-1)*(2^s-1), or (2^ceiling(n/2)-1)*(2^floor(n/2)-1) as claimed. (End)
%F A274230 From _Colin Barker_, Jun 22 2016, revised by _N. J. A. Sloane_, Jul 05 2016: (Start)
%F A274230 It follows that:
%F A274230 a(n) = (2^(n/2)-1)^2 for n even, a(n) = 2^n+1-3*2^((n-1)/2) for n odd.
%F A274230 a(n) = 3*a(n-1)-6*a(n-3)+4*a(n-4) for n>3.
%F A274230 G.f.: x^2 / ((1-x)*(1-2*x)*(1-2*x^2)).
%F A274230 a(n) = (1+2^n-2^((n-3)/2)*(3-3*(-1)^n+2*sqrt(2)+2*(-1)^n*sqrt(2))). (End)
%F A274230 a(n) = A000225(n) - 2*A052955(n-2) for n > 1. - _Yuchun Ji_, Nov 19 2018
%F A274230 a(n) = A079667(2^(n-1)) for n >= 1. - _J. M. Bergot_, Jan 18 2021
%F A274230 a(n) = 2^(n-1) - A052955(n) = 2^(n-1) - A027383(n) - 1. - _Gus Wiseman_, Jan 29 2022
%F A274230 E.g.f.: cosh(x) + cosh(2*x) - 2*cosh(sqrt(2)*x) + sinh(x) + sinh(2*x) - 3*sinh(sqrt(2)*x)/sqrt(2). - _Stefano Spezia_, Apr 06 2022
%p A274230 A274230:=n->(1+2^n-2^((n-3)/2)*(3-3*(-1)^n+2*sqrt(2)+2*(-1)^n*sqrt(2))): seq(A274230(n), n=0..50); # _Wesley Ivan Hurt_, Jul 07 2016
%t A274230 Table[(2^Ceiling@ # - 1) (2^Floor@ # - 1) &[n/2], {n, 0, 31}] (* _Michael De Vlieger_, Jun 30 2016 *)
%o A274230 (Magma) [(2^Ceiling(n/2)-1)*(2^Floor(n/2)-1 ): n in [0..35]]; // _Vincenzo Librandi_, Jul 02 2016
%o A274230 (PARI) a(n)=2^n+1-(n%2+2)<<(n\2) \\ _Charles R Greathouse IV_, Jul 05 2016
%Y A274230 Cf. A000225, A079667, A183978.
%Y A274230 See A274626, A274627 for the three- and higher-dimensional analogs.
%Y A274230 This is the main diagonal of A274635.
%Y A274230 Counting fold lines instead of holes gives A027383.
%Y A274230 Bisections are A060867 (even) and A134057 (odd).
%Y A274230 Cf. A000712, A001405, A008549, A011782, A026010, A052955, A097613, A126869, A138364, A232580, A351003.
%K A274230 nonn,nice,easy
%O A274230 0,4
%A A274230 _Philippe Gibone_, Jun 15 2016