cp's OEIS Frontend

Also, first differences of toothpick numbers A153000.

Also, first differences of toothpicks numbers A152998. [From Omar E. Pol, Jan 02 2009]

Limiting behavior of the rows of the triangle in A139251 when the first column of that triangle is omitted.

First differences of A159795. - Omar E. Pol, Jul 24 2009

It appears that a(n) is also the number of new grid points that are covered at n-th stage of A139250 version "Tree", assuming the toothpicks have length 4, 3, and 2 (see also A159795 and A153006). - Omar E. Pol, Oct 25 2011

Excluding the initial 1 and 2, this sequence also gives the records in A147646. - Nathaniel Johnston, Apr 10 2011

A toothpick is a copy of the closed interval [-1,1]. (In the paper, we take it to be a copy of the unit interval [-1/2, 1/2].)

We start at stage 0 with no toothpicks.

At stage 1 we place a toothpick in the vertical direction, anywhere in the plane.

In general, given a configuration of toothpicks in the plane, at the next stage we add as many toothpicks as possible, subject to certain conditions:

- Each new toothpick must lie in the horizontal or vertical directions.

- Two toothpicks may never cross.

- Each new toothpick must have its midpoint touching the endpoint of exactly one existing toothpick.

The sequence gives the number of toothpicks after n stages. A139251 (the first differences) gives the number added at the n-th stage.

Call the endpoint of a toothpick "exposed" if it does not touch any other toothpick. The growth rule may be expressed as follows: at each stage, new toothpicks are placed so their midpoints touch every exposed endpoint.

This is equivalent to a two-dimensional cellular automaton. The animations show the fractal-like behavior.

After 2^k - 1 steps, there are 2^k exposed endpoints, all located on two lines perpendicular to the initial toothpick. At the next step, 2^k toothpicks are placed on these lines, leaving only 4 exposed endpoints, located at the corners of a square with side length 2^(k-1) times the length of a toothpick. - M. F. Hasler, Apr 14 2009 and others. For proof, see the Applegate-Pol-Sloane paper.

If the third condition in the definition is changed to "- Each new toothpick must have at exactly one of its endpoints touching the midpoint of an existing toothpick" then the same sequence is obtained. The configurations of toothpicks are of course different from those in the present sequence. But if we start with the configurations of the present sequence, rotate each toothpick a quarter-turn, and then rotate the whole configuration a quarter-turn, we obtain the other configuration.

If the third condition in the definition is changed to "- Each new toothpick must have at least one of its endpoints touching the midpoint of an existing toothpick" then the sequence n^2 - n + 1 is obtained, because there are no holes left in the grid.

A "toothpick" of length 2 can be regarded as a polyedge with 2 components, both on the same line. At stage n, the toothpick structure is a polyedge with 2*a(n) components.

Conjecture: Consider the rectangles in the sieve (including the squares). The area of each rectangle (A = b*c) and the edges (b and c) are powers of 2, but at least one of the edges (b or c) is <= 2.

In the toothpick structure, if n >> 1, we can see some patterns that look like "canals" and "diffraction patterns". For example, see the Applegate link "A139250: the movie version", then enter n=1008 and click "Update". See also "T-square (fractal)" in the Links section. - Omar E. Pol, May 19 2009, Oct 01 2011

From Benoit Jubin, May 20 2009: The web page "Gallery" of Chris Moore (see link) has some nice pictures that are somewhat similar to the pictures of the present sequence. What sequences do they correspond to?

For a connection to Sierpiński triangle and Gould's sequence A001316, see the leftist toothpick triangle A151566.

Eric Rowland comments on Mar 15 2010 that this toothpick structure can be represented as a 5-state CA on the square grid. On Mar 18 2010, David Applegate showed that three states are enough. See links.

Equals row sums of triangle A160570 starting with offset 1; equivalent to convolving A160552: (1, 1, 3, 1, 3, 5, 7, ...) with (1, 2, 2, 2, ...). Equals A160762: (1, 0, 2, -2, 2, 2, 2, -6, ...) convolved with 2*n - 1: (1, 3, 5, 7, ...). Starting with offset 1 equals A151548: [1, 3, 5, 7, 5, 11, 17, 15, ...] convolved with A078008 signed (A151575): [1, 0, 2, -2, 6, -10, 22, -42, 86, -170, 342, ...]. - Gary W. Adamson, May 19 2009, May 25 2009

For a three-dimensional version of the toothpick structure, see A160160. - Omar E. Pol, Dec 06 2009

From Omar E. Pol, May 20 2010: (Start)

Observation about the arrangement of rectangles:

It appears there is a nice pattern formed by distinct modular substructures: a central cross surrounded by asymmetrical crosses (or "hidden crosses") of distinct sizes and also by "nuclei" of crosses.

Conjectures: after 2^k stages, for k >= 2, and for m = 1 to k - 1, there are 4^(m-1) substructures of size s = k - m, where every substructure has 4*s rectangles. The total number of substructures is equal to (4^(k-1)-1)/3 = A002450(k-1). For example: If k = 5 (after 32 stages) we can see that:

a) There is a central cross, of size 4, with 16 rectangles.

b) There are four hidden crosses, of size 3, where every cross has 12 rectangles.

c) There are 16 hidden crosses, of size 2, where every cross has 8 rectangles.

d) There are 64 nuclei of crosses, of size 1, where every nucleus has 4 rectangles.

Hence the total number of substructures after 32 stages is equal to 85. Note that in every arm of every substructure, in the potential growth direction, the length of the rectangles are the powers of 2. (See illustrations in the links. See also A160124.) (End)

It appears that the number of grid points that are covered after n-th stage of the toothpick structure, assuming the toothpicks have length 2*k, is equal to (2*k-2)*a(n) + A147614(n), k > 0. See the formulas of A160420 and A160422. - Omar E. Pol, Nov 13 2010

Version "Gullwing": on the semi-infinite square grid, at stage 1, we place a horizontal "gull" with its vertices at [(-1, 2), (0, 1), (1, 2)]. At stage 2, we place two vertical gulls. At stage 3, we place four horizontal gulls. a(n) is also the number of gulls after n-th stage. For more information about the growth of gulls see A187220. - Omar E. Pol, Mar 10 2011

From Omar E. Pol, Mar 12 2011: (Start)

Version "I-toothpick": we define an "I-toothpick" to consist of two connected toothpicks, as a bar of length 2. An I-toothpick with length 2 is formed by two toothpicks with length 1. The midpoint of an I-toothpick is touched by its two toothpicks. a(n) is also the number of I-toothpicks after n-th stage in the I-toothpick structure. The I-toothpick structure is essentially the original toothpick structure in which every toothpick is replaced by an I-toothpick. Note that in the physical model of the original toothpick structure the midpoint of a wooden toothpick of the new generation is superimposed on the endpoint of a wooden toothpick of the old generation. However, in the physical model of the I-toothpick structure the wooden toothpicks are not overlapping because all wooden toothpicks are connected by their endpoints. For the number of toothpicks in the I-toothpick structure see A160164 which also gives the number of gullwing in a gullwing structure because the gullwing structure of A160164 is equivalent to the I-toothpick structure. It also appears that the gullwing sequence A187220 is a supersequence of the original toothpick sequence A139250 (this sequence).

For the connection with the Ulam-Warburton cellular automaton see the Applegate-Pol-Sloane paper and see also A160164 and A187220.

(End)

A version in which the toothpicks are connected by their endpoints: on the semi-infinite square grid, at stage 1, we place a vertical toothpick of length 1 from (0, 0). At stage 2, we place two horizontal toothpicks from (0,1), and so on. The arrangement looks like half of the I-toothpick structure. a(n) is also the number of toothpicks after the n-th. - Omar E. Pol, Mar 13 2011

Version "Quarter-circle" (or Q-toothpick): a(n) is also the number of Q-toothpicks after the n-th stage in a Q-toothpick structure in the first quadrant. We start from (0,1) with the first Q-toothpick centered at (1, 1). The structure is asymmetric. For a similar structure but starting from (0, 0) see A187212. See A187210 and A187220 for more information. - Omar E. Pol, Mar 22 2011

Version "Tree": It appears that a(n) is also the number of toothpicks after the n-th stage in a toothpick structure constructed following a special rule: the toothpicks of the new generation have length 4 when they are placed on the infinite square grid (note that every toothpick has four components of length 1), but after every stage, one (or two) of the four components of every toothpick of the new generation is removed, if such component contains an endpoint of the toothpick and if such endpoint is touching the midpoint or the endpoint of another toothpick. The truncated endpoints of the toothpicks remain exposed forever. Note that there are three sizes of toothpicks in the structure: toothpicks of lengths 4, 3 and 2. A159795 gives the total number of components in the structure after the n-th stage. A153006 (the corner sequence of the original version) gives 1/4 of the total of components in the structure after the n-th stage. - Omar E. Pol, Oct 24 2011

From Omar E. Pol, Sep 16 2012: (Start)

It appears that a(n)/A147614(n) converges to 3/4.

It appears that a(n)/A160124(n) converges to 3/2.

It appears that a(n)/A139252(n) converges to 3.

Also:

It appears that A147614(n)/A160124(n) converges to 2.

It appears that A160124(n)/A139252(n) converges to 2.

It appears that A147614(n)/A139252(n) converges to 4.

(End)

It appears that a(n) is also the total number of ON cells after n-th stage in a quadrant of the structure of the cellular automaton described in A169707 plus the total number of ON cells after n+1 stages in a quadrant of the mentioned structure, without its central cell. See the illustration of the NW-NE-SE-SW version in A169707. See also the connection between A160164 and A169707. - Omar E. Pol, Jul 26 2015

On the infinite Cairo pentagonal tiling consider the symmetric figure formed by two non-adjacent pentagons connected by a line segment joining two trivalent nodes. At stage 1 we start with one of these figures turned ON. The rule for the next stages is that the concave part of the figures of the new generation must be adjacent to the complementary convex part of the figures of the old generation. a(n) gives the number of figures that are ON in the structure after n-th stage. A160164(n) gives the number of ON cells in the structure after n-th stage. - Omar E. Pol, Mar 29 2018

From Omar E. Pol, Mar 06 2019: (Start)

The "word" of this sequence is "ab". For further information about the word of cellular automata see A296612.

Version "triangular grid": a(n) is also the total number of toothpicks of length 2 after n-th stage in the toothpick structure on the infinite triangular grid, if we use only two of the three axes. Otherwise, if we use the three axes, so we have the sequence A296510 which has word "abc".

The normal toothpick structure can be considered a superstructure of the Ulam-Warburton celular automaton since A147562(n) equals here the total number of "hidden crosses" after 4*n stages, including the central cross (beginning to count the crosses when their "nuclei" are totally formed with 4 quadrilaterals). Note that every quadrilateral in the structure belongs to a "hidden cross".

Also, the number of "hidden crosses" after n stages equals the total number of "flowers with six petals" after n-th stage in the structure of A323650, which appears to be a "missing link" between this sequence and A147562.

Note that the location of the "nuclei of the hidden crosses" is very similar (essentially the same) to the location of the "flowers with six petals" in the structure of A323650 and to the location of the "ON" cells in the version "one-step bishop" of the Ulam-Warburton cellular automaton of A147562. (End)

From Omar E. Pol, Nov 27 2020: (Start)

The simplest substructures are the arms of the hidden crosses. Each closed region (square or rectangle) of the structure belongs to one of these arms. The narrow arms have regions of area 1, 2, 4, 8, ... The broad arms have regions of area 2, 4, 8, 16 , ... Note that after 2^k stages, with k >= 3, the narrow arms of the main hidden crosses in each quadrant frame the size of the toothpick structure after 2^(k-1) stages.

Another kind of substructure could be called "bar chart" or "bar graph". This substructure is formed by the rectangles and squares of width 2 that are adjacent to any of the four sides of the toothpick structure after 2^k stages, with k >= 2. The height of these successive regions gives the first 2^(k-1) - 1 terms from A006519. For example: if k = 5 the respective heights after 32 stages are [1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1]. The area of these successive regions gives the first 2^(k-1) - 1 terms of A171977. For example: if k = 5 the respective areas are [2, 4, 2, 8, 2, 4, 2, 16, 2, 4, 2, 8, 2, 4, 2].

For a connection to Mersenne primes (A000668) and perfect numbers (A000396) see A153006.

For a representation of the Wagstaff primes (A000979) using the toothpick structure see A194810.

For a connection to stained glass windows and a hidden curve see A336532. (End)

It appears that the graph of a(n) bears a striking resemblance to the cumulative distribution function F(x) for X the random variable taking values in [0,1], where the binary expansion of X is given by a sequence of independent coin tosses with probability 3/4 of being 1 at each bit. It appears that F(n/2^k)*(2^(2k+1)+1)/3 approaches a(n) for k large. - James Coe, Jan 10 2022

a(n) is also the number of different lines determined by pair of vertices in an n-dimensional hypercube. The number of these lines modulo being parallel is in A003462. - Ola Veshta (olaveshta(AT)my-deja.com), Feb 15 2001

Let G_n be the elementary Abelian group G_n = (C_2)^n for n >= 1: A006516 is the number of times the number -1 appears in the character table of G_n and A007582 is the number of times the number 1. Together the two sequences cover all the values in the table, i.e., A006516(n) + A007582(n) = 2^(2n). - Ahmed Fares (ahmedfares(AT)my-deja.com), Jun 01 2001

a(n) is the number of n-letter words formed using four distinct letters, one of which appears an odd number of times. - Lekraj Beedassy, Jul 22 2003 [See, e.g., the Balakrishnan reference, problems 2.67 and 2.68, p. 69. - Wolfdieter Lang, Jul 16 2017]

Number of 0's making up the central triangle in a Pascal's triangle mod 2 gasket. - Lekraj Beedassy, May 14 2004

m-th triangular number, where m is the n-th Mersenne number, i.e., a(n)=A000217(A000225(n)). - Lekraj Beedassy, May 25 2004

Number of walks of length 2n+1 between two nodes at distance 3 in the cycle graph C_8. - Herbert Kociemba, Jul 02 2004

The sequence of fractions a(n+1)/(n+1) is the 3rd binomial transform of (1, 0, 1/3, 0, 1/5, 0, 1/7, ...). - Paul Barry, Aug 05 2005

Number of monic irreducible polynomials of degree 2 in GF(2^n)[x]. - Max Alekseyev, Jan 23 2006

(A007582(n))^2 + a(n)^2 = A007582(2n). E.g., A007582(3) = 36, a(3) = 28; A007582(6) = 2080. 36^2 + 28^2 = 2080. - Gary W. Adamson, Jun 17 2006

The sequence 6*a(n), n>=1, gives the number of edges of the Hanoi graph H_4^{n} with 4 pegs and n>=1 discs. - Daniele Parisse, Jul 28 2006

8*a(n) is the total border length of the 4*n masks used when making an order n regular DNA chip, using the bidimensional Gray code suggested by Pevzner in the book "Computational Molecular Biology." - Bruno Petazzoni (bruno(AT)enix.org), Apr 05 2007

If we start with 1 in binary and at each step we prepend 1 and append 0, we construct this sequence: 1 110 11100 1111000 etc.; see A109241(n-1). - Artur Jasinski, Nov 26 2007

Let P(A) be the power set of an n-element set A. Then a(n) = the number of pairs of elements {x,y} of P(A) for which x does not equal y. - Ross La Haye, Jan 02 2008

Wieder calls these "conjoint usual 2-combinations." The set of "conjoint strict k-combinations" is the subset of conjoint usual k-combinations where the empty set and the set itself are excluded from possible selection. These numbers C(2^n - 2,k), which for k = 2 (i.e., {x,y} of the power set of a set) give {1, 0, 1, 15, 91, 435, 1891, 7875, 32131, 129795, 521731, ...}. - Ross La Haye, Jan 15 2008

If n is a member of A000043 then a(n) is also a perfect number (A000396). - Omar E. Pol, Aug 30 2008

a(n) is also the number whose binary representation is A109241(n-1), for n>0. - Omar E. Pol, Aug 31 2008

From Daniel Forgues, Nov 10 2009: (Start)

If we define a spoof-perfect number as:

A spoof-perfect number is a number that would be perfect if some (one or more) of its odd composite factors were wrongly assumed to be prime, i.e., taken as a spoof prime.

And if we define a "strong" spoof-perfect number as:

A "strong" spoof-perfect number is a spoof-perfect number where sigma(n) does not reveal the compositeness of the odd composite factors of n which are wrongly assumed to be prime, i.e., taken as a spoof prime.

The odd composite factors of n which are wrongly assumed to be prime then have to be obtained additively in sigma(n) and not multiplicatively.

Then:

If 2^n-1 is odd composite but taken as a spoof prime then 2^(n-1)*(2^n - 1) is an even spoof perfect number (and moreover "strong" spoof-perfect).

For example:

a(8) = 2^(8-1)*(2^8 - 1) = 128*255 = 32640 (where 255 (with factors 3*5*17) is taken as a spoof prime);

sigma(a(8)) = (2^8 - 1)*(255 + 1) = 255*256 = 2*(128*255) = 2*32640 = 2n is spoof-perfect (and also "strong" spoof-perfect since 255 is obtained additively);

a(11) = 2^(11-1)*(2^11 - 1) = 1024*2047 = 2096128 (where 2047 (with factors 23*89) is taken as a spoof prime);

sigma(a(11)) = (2^11 - 1)*(2047 + 1) = 2047*2048 = 2*(1024*2047) = 2*2096128 = 2n is spoof-perfect (and also "strong" spoof-perfect since 2047 is obtained additively).

I did a Google search and didn't find anything about the distinction between "strong" versus "weak" spoof-perfect numbers. Maybe some other terminology is used.

An example of an even "weak" spoof-perfect number would be:

n = 90 = 2*5*9 (where 9 (with factors 3^2) is taken as a spoof prime);

sigma(n) = (1+2)*(1+5)*(1+9) = 3*(2*3)*(2*5) = 2*(2*5*(3^2)) = 2*90 = 2n is spoof-perfect (but is not "strong" spoof-perfect since 9 is obtained multiplicatively as 3^2 and is thus revealed composite).

Euler proved:

If 2^k - 1 is a prime number, then 2^(k-1)*(2^k - 1) is a perfect number and every even perfect number has this form.

The following seems to be true (is there a proof?):

If 2^k - 1 is an odd composite number taken as a spoof prime, then 2^(k-1)*(2^k - 1) is a "strong" spoof-perfect number and every even "strong" spoof-perfect number has this form?

There is only one known odd spoof-perfect number (found by Rene Descartes) but it is a "weak" spoof-perfect number (cf. 'Descartes numbers' and 'Unsolved problems in number theory' links below). (End)

a(n+1) = A173787(2*n+1,n); cf. A020522, A059153. - Reinhard Zumkeller, Feb 28 2010

Also, row sums of triangle A139251. - Omar E. Pol, May 25 2010

Starting with "1" = (1, 1, 2, 4, 8, ...) convolved with A002450: (1, 5, 21, 85, 341, ...); and (1, 3, 7, 15, 31, ...) convolved with A002001: (1, 3, 12, 48, 192, ...). - Gary W. Adamson, Oct 26 2010

a(n) is also the number of toothpicks in the corner toothpick structure of A153006 after 2^n - 1 stages. - Omar E. Pol, Nov 20 2010

The number of n-dimensional odd theta functions of half-integral characteristic. (Gunning, p.22) - Michael Somos, Jan 03 2014

a(n) = A000217((2^n)-1) = 2^(2n-1) - 2^(n-1) is the nearest triangular number below 2^(2n-1); cf. A007582, A233327. - Antti Karttunen, Feb 26 2014

a(n) is the sum of all the remainders when all the odd numbers < 2^n are divided by each of the powers 2,4,8,...,2^n. - J. M. Bergot, May 07 2014

Let b(m,k) = number of ways to form a sequence of m selections, without replacement, from a circular array of m labeled cells, such that the first selection of a cell whose adjacent cells have already been selected (a "first connect") occurs on the k-th selection. b(m,k) is defined for m >=3, and for 3 <= k <= m. Then b(m,k)/2m ignores rotations and reflection. Let m=n+2, then a(n) = b(m,m-1)/2m. Reiterated, a(n) is the (m-1)th column of the triangle b(m,k)/2m, whose initial rows are (1), (1 2), (2 6 4), (6 18 28 8), (24 72 128 120 16), (120 360 672 840 496 32), (720 2160 4128 5760 5312 2016 64); see A249796. Note also that b(m,3)/2m = n!, and b(m,m)/2m = 2^n. Proofs are easy. - Tony Bartoletti, Oct 30 2014

Beginning at a(1) = 1, this sequence is the sum of the first 2^(n-1) numbers of the form 4*k + 1 = A016813(k). For example, a(4) = 120 = 1 + 5 + 9 + 13 + 17 + 21 + 25 + 29. - J. M. Bergot, Dec 07 2014

a(n) is the number of edges in the (2^n - 1)-dimensional simplex. - Dimitri Boscainos, Oct 05 2015

a(n) is the number of linear elements in a complete plane graph in 2^n points. - Dimitri Boscainos, Oct 05 2015

a(n) is the number of linear elements in a complete parallelotope graph in n dimensions. - Dimitri Boscainos, Oct 05 2015

a(n) is the number of lattices L in Z^n such that the quotient group Z^n / L is C_4. - Álvar Ibeas, Nov 26 2015

a(n) gives the quadratic coefficient of the polynomial ((x + 1)^(2^n) + (x - 1)^(2^n))/2, cf. A201461. - Martin Renner, Jan 14 2017

Let f(x)=x+2*sqrt(x) and g(x)=x-2*sqrt(x). Then f(4^n*x)=b(n)*f(x)+a(n)*g(x) and g(4^n*x)=a(n)*f(x)+b(n)*g(x), where b is A007582. - Luc Rousseau, Dec 06 2018

For n>=1, a(n) is the covering radius of the first order Reed-Muller code RM(1,2n). - Christof Beierle, Dec 22 2021

a(n) =

Bisection of A323651. - Omar E. Pol, Mar 04 2019