A260965 - OEIS

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.

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

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