editing

approved

editing

a(n) is the second smallest multiple of n different from a(1), ..., a(n-1).

{a(n)/n} is unbounded. Proof: Suppose that {a(n)/n} has an upper bound T, where T is a positive integer. Denote p_1 < ... < p_t by all primes not larger than n, and b by floor(log_2(t)).

Proof by Shen Xingyu

proposed

editing

approved

editing

Proof: Suppose that n >= 3.

Let b(n) be the number of ways to choose points on a 2 X n lattice such that the points do not touch each other.

Let c(n) be the number of ways to choose points on a 2 X n lattice eliminating the upper left corner such that the points do not touch each other.

Let d(n) be the number of ways to choose points on a 2 X n lattice eliminating the upper left and lower right corners such that the points do not touch each other.

Put the numbers on the 2 X n lattice:

1 2 ... n

n+1 n+2 ... 2*n

For a(n), the selected points from T do not touch each other, amounting to b(n) ways. We should only eliminate the case that n and n+1 are both chosen. So 1, n-1, n+2, 2*n must not be chosen, and the remaining lattice corresponds to d(n-1). Hence a(n) = b(n) - d(n-1). (1)

For b(n), if 1 and n+1 are not chosen, the remaining lattice corresponds to b(n-1); if 1 is chosen, 2 and n+1 must not be chosen, and the remaining lattice corresponds to c(n-1). Hence b(n) = b(n-1) + 2*c(n-1). (2)

For c(n), if n+1 is not chosen, the remaining lattice corresponds to b(n-1); if n+1 is chosen, n+2 must not be chosen, and the remaining lattice corresponds to c(n-1). Hence c(n) = b(n-1) + c(n-1). (3)

For d(n), if n+1 is not chosen, the remaining lattice corresponds to c(n-1); if n+1 is chosen, n+2 must not be chosen. If 2 is not chosen, the remaining lattice corresponds to c(n-2); if 2 is chosen, 3 must not be chosen, and the remaining lattice corresponds to d(n-2). Hence d(n) = c(n-1) + c(n-2) + d(n-2). (4)

From (2) - (3), b(n) - c(n) = c(n-1). (5)

From (2), c(n-1) = (b(n) - b(n-1))/2. (6)

Substitute (6) into (5), b(n) = 2*b(n-1) + b(n-2). (7)

Since b(0) = 1, b(1) = 3, b(n) = A001333(n+1).

Substitute (5) into (3), c(n) = 2*c(n-1) + c(n-2). (8)

Since c(0) = 1, c(1) = 2, c(n) = A000129(n+1).

Substitute (5) into (4), d(n) = b(n-1) + d(n-2). (9)

Substitute (7) into (9), d(n) = d(n-2) + (b(n) - b(n-2))/2.

So d(n) - b(n)/2 = d(n-2) - b(n-2)/2.

If n is even, d(n) - b(n)/2 = d(2) - b(2)/2 = 1/2;

If n is odd, d(n) - b(n)/2 = d(1) - b(1)/2 = -1/2.

Hence d(n) = b(n)/2 + (-1)^n/2. (10)

From (7), b(n) = ((1-sqrt(2))^(n+1) + (1+sqrt(2))^(n+1))/2. (11)

Substitute (11) into (10) and (1), a(n) = 1/4*((3+sqrt(2))*(1+sqrt(2))^n+(3-sqrt(2))*(1-sqrt(2))^n-2*(-1)^n), d(n) = ((1+sqrt(2))^n + (1-sqrt(2))^n - 2*(-1)^n)/4.

Therefore, d(n) = d(n-1) + 3*d(n-2) + d(n-3) with d(0) = 1, d(1) = 1, d(2) = 4, so d(n) = A097076(n+1), a(n) = a(n-1) + 3*a(n-2) + a(n-3) with a(0) = 1, a(1) = 3, a(2) = 6.

proposed

editing