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

2, 6, 9, 8, 10, 18, 14, 24, 36, 30, 22, 48, 26, 42, 45, 32, 34, 72, 38, 40, 63, 66, 46, 120, 50, 78, 54, 56, 58, 90, 62, 96, 99, 102, 70, 144, 74, 114, 117, 160, 82, 126, 86, 88, 180, 138, 94, 240, 98, 150, 153, 104, 106, 162, 110, 168, 171, 174, 118, 300, 122

Offset: 1

Author

Yifan Xie, Jul 30 2024

Keywords

• nonn
• easy

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.

Examples

			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.
		

Links

• Yifan Xie, Table of n, a(n) for n = 1..1000

Programs

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));