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

%I #118 Sep 20 2024 12:37:58

%S 2,6,9,8,10,18,14,24,36,30,22,48,26,42,45,32,34,72,38,40,63,66,46,120,

%T 50,78,54,56,58,90,62,96,99,102,70,144,74,114,117,160,82,126,86,88,

%U 180,138,94,240,98,150,153,104,106,162,110,168,171,174,118,300,122

%N a(1) = 2; a(n) is the second smallest multiple of n different from a(1), ..., a(n-1).

%C a(n) <= n^2 for n >= 3.

%C a(n) >= 2*n; For prime n, a(n) = 2*n.

%C {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)).

%C 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)

%C Denote b(n) by the smallest multiple of n different from a(1), ..., a(n-1). Define f(n) as below: (Start)

%C If b(n) does not appear in {a(n)}, define f(n) = b(n);

%C 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, ...

%C 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)

%C 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)

%C On the other hand, for positive integer m, consider the number of positive integers n such that f(n) = m.

%C 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.

%C 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.

%C By analogy, there are at most T + T^2 + ... + T^T < T^(T+1) positive integers n such that f(n) = m.

%C 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)}.

%C 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).

%C 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.

%e 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.

%o (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));

%K nonn,easy

%O 1,1

%A _Yifan Xie_, Jul 30 2024