editing
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