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

Offset: 1

Author

Vladimir Shevelev, Aug 06 2015

Keywords

• nonn

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

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.

Examples

			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.
		

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.

Crossrefs

Cf. A260803, A260804.

Formula

a(n) <= floor(log_2(prime(n))).

Extensions

More terms from David A. Corneth, Aug 16 2015

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.