|
| |
|
|
A260965
|
|
Smallest number r>=3 such that for k>=r the number k - 3 + prime(n) can be represented in the form x_1*...*x_k + x_1 + ... + x_k, where 1 <= x_1 <= ... <= x_k, or a(n)=0 if there is no such r.
|
|
3
|
|
|
|
0, 0, 0, 0, 0, 0, 0, 3, 4, 3, 0, 0, 4, 0, 3, 0, 3, 3, 0, 4, 3, 3, 4, 3, 4, 0, 3, 5, 3, 4, 3, 3, 3, 3, 3, 3, 4, 3, 4, 3, 3, 0, 0, 5, 3, 3, 3, 0, 3, 3, 4, 3, 3, 0, 3, 3, 3, 3, 3, 3, 4, 3, 3, 3, 3, 4, 3, 3, 4, 3, 3, 3, 3, 0, 3, 3, 3, 3, 3, 3, 3, 0, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 3, 3, 3, 3, 4, 3, 3, 3, 3, 4, 3, 3, 4, 3, 3, 3
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,8
|
|
|
COMMENTS
|
Let m>=k-1. The condition 'm - k + 3 is prime' is a necessary condition for the non-representation of m by the form A = x_1*...*x_k + x_1 + ... + x_k, where 1 <= x_1 <= ... <= x_k (see link [Shevelev], Proposition 2). In particular, if m - k + 3 = prime(n), then a sufficient condition for that is a(n) = 0 or a(n) > k.
Conjecture. The sequence contains only a finite number of zero terms.
About the conjecture, for n <= 10000, 23 values a(n) are 0, of which 19 have n <= 100. The highest such n is 450. a(n) is at most five for n <= 10000 and mostly 3 (9747 times). - David A. Corneth, Aug 16 2015
Upper estimate of a(n). A representation of prime(n) + k - 3 for the minimal possible k by the form A we call optimal. Show that in an optimal representation all x_i>=2.
Indeed, let x_1 = ... = x_u = 1 and x_i >= 2 for u+1 <= i <= k, such that prime(n) + k - 3 = x_(u+1)*...*x_k + u + x_(u+1) + ... + x_k be an optimal representation (note that u<k, otherwise A = k+1 which is not k-3 + prime). Set k_1 = k - u; y_j = x_(u+j). Then prime(n) + k_1 - 3 = y_1*...*y_(k_1) + y_1 + ... + y_(k_1). But k_1 < k, which contradicts the optimality of A. QED
So for an optimal representation, prime(n) + k - 3 = A >= 2^k + 2*k and 2^k + k + 3 <= prime(n). Thus a(n) = k_min < log_2(prime(n)) (cf. formula).
a(n)>0 iff either there exists t_2>=1 such that B(t_2) = 2^t_2 + t_2 + 3 = prime(n) or there exist t_2>=0, t_3>=1 such that B(t_2, t_3) = 2^t_2*3^t_3 + t_2 + 2*t_3 + 3 = prime(n) or there exist t_2>=0, t_3>=0, t_4>=1 such that B(t_2, t_3, t_4) = 2^t_2*3^t_3*4^t_4 + t_2 + 2*t_3 + 3*t_4 + 3 = prime(n), etc.
For a proof, distinguish the following cases for x_i >= 2, i=1,...,k, and A = x_1*...*x_k + x_1 + ... + x_k:
(i) all x_i = 2. Here k=t_2 and A = A(t_2) = 2^t_2 + 2*t_2. If this is t_2 - 3 + prime, then prime = 2^t_2+t_2+3 = B(t_2). For example, for t_2=4 we have 23 = prime(9). Thus for k>=4, k - 3 + prime(9) is represented by a considered form A and a(9)=4.
(ii) the first t_2 consecutive x_i = 2 and t_3 consecutive x_i = 3. Note that t_3 >= 1 (otherwise, we have case (i)). Here A = A(t_2, t_3) = (2^t_2)*(3^t_3) + 2*t_2 + 3*t_3. If this is k - 3 + prime(n) = t_2 + t_3 -3 + prime(n), then prime(n) = (2^t_2)*(3^t_3) + t_2 + 2*t_3 + 3 = B(t_2, t_3). For example, for t_2=2, t_3=1 we have 19=prime(8). Thus for k>=2+1=3, k-3+prime(8) is represented by a considered form A and a(8)=2+1=3.
etc. QED
For an algorithm of calculation of a(n), see link [Shevelev], pp. 4-5.
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) <= floor(log_2(prime(n)).
|
|
|
EXAMPLE
|
a(8)=3. Indeed, prime(8) = 19 and for k=3, set x_1 = x_2 = 2, x_3 = 3, and, for k>=4, set x_1 = ... = x_(k-3) = 1, x_(k-2) = x_(k-1) = 2, x_k = 3.
In both cases, x_1*...*x_k + x_1 + ... + x_k = 2*2*3 + (k-3) + 2 + 2 + 3 = k + 19 - 3.
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
