cp's OEIS Frontend

Row sums => A000041. Diagonals are sums of Gaussian polynomials (which then sum to powers of two). The number of entries on each row is conjectured to conform to: 0 1 1 1 2 2 3 3 4 5 5 6 7 7 8 9 10 10 11 12 13 13 14 15 16 17 17 ... a sequence which stutters after values 0,1,2,4,6,9,12,16,...A002620.

Regarding the first element of the sequence as T(1,0), it appears that this is the number of partitions of n with k elements not in the first hook; i.e., with n - (max part size) - (number of parts) + 1 = k. If this is correct, we have T(n,0) = n and for k > 0, T(n,k) = sum_{j >= max(0,2k-n+2)} j * T(k,j). This is equivalent to T(n,k) = T(n-1,k) + sum_{j >= max(0,2k-n+2)} T(k,j) and thus to T(n,k) = 2* T(n-1,k) - T(n-2,k) + T(k,2k-n+2) [taking T(n,k) = 0 if k < 0]. It also implies the correctness of the conjecture about the row lengths. - Franklin T. Adams-Watters, May 27 2008

For each of the A000041(n) partitions of n, one can assign a weight to the partition which counts the permutations of that partition, given by the multinomial coefficient derived from the frequency representation of the parts.

An equivalent representation is given by writing down all compositions of n.

The entries count those partitions multiplied by their weights (=compositions) of n where the sum of the largest addend plus number of parts equals k+1. Only nonzero counts are entered into the sequence.

Each entry can also be interpreted as counting a subset of numbers in A055932, because there is a 1-to-1 correspondence between their prime signature and ordered partitions.

Each diagonal of T(n,k) can be decomposed into p(n) sequences. For example,

A086602 = 2 12 39 95 195 ... is the sum of

A000330 = 1 5 14 30 55 ... plus

A001296 = 1 7 25 65 140 ...

The main diagonal and subdiagonals in order of appearance are A000124, A000330, A086602, A089574, A107600, A107601, A109125, ...

Conjectures: a(2^n)=a(2^(n+1)+1)=A033638(n); a(2^n-1)=a(3*2^n-1)=1.

The Gi1 and Gi2 triangle sums, see A180662 for their definitions, of Sierpinski's triangle A047999 equal this sequence. The Gi1 and Gi2 sums can also be interpreted as (i + 4*j = n) and (4*i + j = n) sums, see the Northshield reference. Some A112970(2^n-p) sequences, 0<=p<=32, lead to known sequences, see the crossrefs. - Johannes W. Meijer, Jun 05 2011

Original definition: "Quotients of the polynomial remainder theorem for Diophantine equations among permutations."

The set built from the first terms of this sequence {0, 1, 10, 12, 21, 22, ....} contains the general solutions for a class of Diophantine linear equations among permutations, if one takes into account the unlimited number of distinct bases where these may be read.

From M. F. Hasler, Jan 12 2013, edited by R. J. Cano, May 08 2017: (Start)

Let P be the sequence of permutations of (0,...,m-1) interpreted as decimal numbers, P(n) = Sum_{i=1..m} 10^(m-i)*s(i) where s=(s(1),...,s(m)) is the n-th permutation (in lexicographical order), n <= m!. Then the difference P(n)-P(1) is independent of the choice of m, and divisible by 9. (Since 10 == 1 (mod 9), the numbers P(n) are all congruent (mod 9) to the sum s(1)+...+s(m).) This yields well-defined terms a(n)=(P(n)-P(1))/9.

For n>10!, P(n) will no longer be the concatenation of the "digits" (some of which will exceed 9). The pattern present in the decimal representation of the first terms will also be lost since there will be digits as large as d+1.

Note that the same a(n) is obtained independently of the chosen base b, provided that (i) 10 and 9 in the above are replaced with b and b-1, (ii) the result is (and can be) written in base b. (This implies the restriction to terms which can be written using the digits 0-9 to which the OEIS is limited.) See EXAMPLES for an illustration. (End)

We have P(n)-P(1)=a(n)*g(n), with g(n) = 9 = 10-1. Considering this and P(n) as polynomials in x=10, one can see an analogy with the polynomial remainder theorem. [Given as "formula" by R. J. Cano, rephrased by M. F. Hasler, Jan 12 2013]

Contribution by R. J. Cano, Feb 09 2013, (Start)

The maximum of the first m! terms of this sequence is given in base R by the explicit formula (please see A211869): max(m,R)=Sum_{k=1..m} k*(m-k)*R^(m-k-1);

If the first m! terms of this sequence were computed reading the permutations in base A033638(m), dividing their differences by A033638(m)-1, the resulting quotients would be written in the same way (with the same digits) in every base > A033638(m).

(End)

From R. J. Cano, Apr 29 2016, (Start)

Although in the sequence name it reads: "permutation of (0,...,m-1)", the most general statement that could replace it is: "permutation of any m-tuple of integers all of them in arithmetic progression", obtaining a multiple of this sequence, lambda*a(n), where lambda is the common difference for the progression. It works in such way because only the differences is what matters here.

Given x>1 and k>=0, if a polynomial G(x) of degree k is divided by x-1 then the remainder will be the sum of all the coefficients in G. Let us consider the case in which those coefficients are the differences among the letters ("digits") of two permutations for the same set of letters (0..x-1): The sum of all those differences must vanish. This explains how the difference between two of such permutations expressed in base x is 0 mod x-1, particularly why differences for pairs of permutations are divisible by 9.

Another way of introducing this sequence takes advantage of the fact that for n>1, n! is even. Consider for n>1 to obtain only the first n! terms. This can be done by subtracting the last permutation from the first, the penultimate permutation from the second, and so on by following the pattern (P(k)-P(n!-k+1))/9 with 1<=k<=n!. Such procedure generates an antisymmetric sequence f(k) from which a(k)=(f(k)+f(n!))/2. This partially explains why A217626 is symmetric. Also a base-independent treatment is possible using linear algebra: Column vectors and the strictly lower triangular matrix instead of the division by (r-1) where r is the base (and r=10 here for this sequence). This approach leads one to conclude that terms in this sequence are the differences between pairs of vectors made from the first n-1 partial sums of letters ("digits") taken from permutations for n consecutive letters, when components in these vectors are viewed as coefficients for a power series in r=10.

(End)

An easy upper bound is 1 + floor(n^2/4) = A033638(n).

First differences are in A126257.

Here the "neighbors" of a(n) are defined to be the adjacent elements to a(n) in the same row, column or diagonals, that are present in the spiral when a(n) is the new element of the sequence in progress.

For the same idea but for a right triangle see A278317; for an isosceles triangle see A275015; for a square array see A278290; and for a hexagonal spiral see A047931.

Moves triangular numbers (A000217) to squares (A000290), i.e., A056537(A000217(i)) = A000290(i) for i >= 1.

As a square array, this is the dispersion of the complement of the squares; see A082152. - Clark Kimberling, Apr 05 2003

Rows can be extended to negative k with T(n, -k) = T(n, k). Sums of such extended rows give A002894.

T(n, k) is the number of words of length 2n equal to z^k in the Heisenberg group, presented as , where z=[x,y]. In particular, T(n, 0) = A307468(n).

The board is numbered following a square spiral starting with 0 at the origin (where the king is at n = 0) and delimited by a wall that must be crossed on each move:

.

16 15 14 13 12 | .

,-----------. | .

17 | 4 3 2 |11 | .

| ,--- | | .

18 | 5 | 0 1 |10 | .

| '-------' | .

19 | 6 7 8 9 | .

`---------------' .

20 21 22 23 24 25

.

A line drawn from the center of the starting square to the center of the ending square must pass through a wall on each move. A move that would just touch a wall without passing through the wall (e.g., 0 to 2) is not permissible. Equivalently, the king can't move from a square labeled k to a square labeled k +- 1 or k +- 2, i.e., |a(n)-a(n+1)| > 2 for all n.

This sequence is a permutation of the nonnegative integers, see A383186 for the inverse permutation. The king's walk indeed fills the 2D grid with an initial segment S0 of 24 moves, followed by rings R(r), r >= 1, which consist of three shells S1(r), S2(r) and S3(r), each of which corresponds to a tour around the center. Each ring R(r) starts with the move number n = 48 r^2 - 16 r + 1 = (25, 147, 365, ...) to the square at position P(r) = (2-3r, 3r-3) = ((-1,0), (-4,3), (-7,6), ...), and contains a perfectly well defined sequence of 96 r + 26 grid points following a precise sequence of pattern given in full detail on the wiki page provided in the links section.

First differences are 0, 2, or 4. - Charles R Greathouse IV, Aug 25 2011

From Juan Barajas Martin, Aug 27 2011 - Sep 03 2011, Sep 26 2001: (Start)

Initial cubic shape polycube edge = e; volume = e^3; minimum surface area = 6e^2.

Target cubic shape polycube edge = e+1; volume = (e+1)^3; minimum surface area = 6(e+1)^2.

The target polycube is achieved by the successive addition of 3 orthogonal layers of unit cubes to the faces of the initial polycube. The number of unit cubes added in each successive layer take values e^2, e*(e+1) and (e+1)^2, with every layer fully completed before starting the following layer.

This is so because the first unit cube added on every layer will add a surface area of 4 to the previous polycube, which is greater than keeping the new unit cube in the current layer, where we ensure that area will increase by 2 at maximum.

Every layer is constructed as an Ulam spiral, starting at the center and until the completion of the layer.

Except for the first cube placed on every layer which will increase the surface area of the previous polycube by 4, we can count 2 surface area increments for the unit cubes placed at the positions given by the function of the Quarter-squares + 1 sequence (i.e., A033638 = A002620 + 1, which set the locations of right angle turns in Ulam square spiral).

All other positions in the Ulam spiral will increase no area to the previous polycube.

An infinite sequence of polycubes with minimal surface area is approached between pairs of successive polycubes with cubic shape and edge values (e) and (e+1), having respectively polycube volumes e^3 and (e+1)^3 and minimum surface areas 6e^2 and 6(e+1)^2.

(End)