OFFSET
1,1
COMMENTS
a(n) <= n^2 for n >= 3.
a(n) >= 2*n; For prime n, a(n) = 2*n.
{a(n)/n} is unbounded. Proof (by Shen Xingyu): 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)).
For any N, consider S_N = {Product_{k=1..t}p_k^i_k | 0 <= i_k <= N, k=1..t}. For any n in S_N, since a(n)/n < T, a(n) is in S_(N+b). (1)
Denote b(n) by the smallest multiple of n different from a(1), ..., a(n-1). Define f(n) as below: (Start)
If b(n) does not appear in {a(n)}, define f(n) = b(n);
If b(n) = a(n_1), n_1 > n. If b(n_1) does not appear in (a(n)), define f(n) = b(n_1); If b(n_1) = a(n_2), n_2 > n_1, ...
Since b(n) = a(n_1) > b(n_1) = a(n_2) > b(n_2), n < n_1 < n_2, b(n)/n > b(n_1)/n_1 > b(n_2)/n_2. Note that b(n)/n < a(n)/n <= T, so there is an i (1 <= i < T) such that b(n_i) does not appear in {a(n)} for the first time, define f(n) = b(n_i). (End)
If n is in S_N, since b(n)/n < T, b(n) is in S_(N+b). If b(n) = a(n_1), a(n_1) is in S_(N+b), therefore n_1 is in S_(N+b). Since b(n_1)/n_1 < T, b(n_1) is in S_(N+2b). By analogy, f(n) is always in S_(N+T*b), and f(n) does not appear in {a(n)}. (2)
On the other hand, for positive integer m, consider the number of positive integers n such that f(n) = m.
If b(n) = m, since b(n)/n < T, n is in {m, m/2, ..., m/(T-1)}, therefore n has no more than T choices.
If b(n_1) = m, similarly, n_1 has no more than T choices. Since a(n_1)/n = b(n)/n < T, for each n_1, n is in {a(n_1), a(n_1)/2, ..., a(n_1)/(T-1)}, having no more than T choices, therefore n has no more than T^2 choices.
By analogy, there are at most T + T^2 + ... + T^T < T^(T+1) positive integers n such that f(n) = m.
From (2), we know that there are at least card(S_N)/T^(T+1) elements in S_(N+T*b) that does not appear in {a(n)}.
From (1), there are at least card(S_N) elements that appear in {a(n)}, so card(S_(N+T*b)) >= (1+1/T^(T+1))*card(S_N).
But when N tends to infinity, card(S_(N+T*b))/card(S_N) = (N+T*b+1)^T/(N+1)^T which tends to 1, which is a contradiction.
EXAMPLE
For n = 9, the only multiples of 9 in a(1), ..., a(8) are 9 and 18, so the smallest such that has not appeared are 27 and 36, thus a(9) = 36.
PROG
(PARI) a=vector(101); used=matrix(500, 500); a[1]=2; for(n=1, 100, fordiv(a[n], d, used[d, a[n]/d]=1); cnt=1; while(used[n+1, cnt]==1, cnt++); cnt++; while(used[n+1, cnt]==1, cnt++); a[n+1]=cnt*(n+1));
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Yifan Xie, Jul 30 2024
STATUS
approved