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
David A. Corneth, Table of n, a(n) for n = 1..10000
David A. Corneth, The tuples of (x_1,...,x_k) that give a(n)
Vladimir Shevelev, Representation of positive integers by the form x1...xk+x1+...+xk, arXiv:1508.03970 [math.NT], 2015.
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
Vladimir Shevelev, Aug 06 2015
EXTENSIONS
More terms from David A. Corneth, Aug 16 2015
STATUS
approved